面试考试可用,十大排序算法

发布于: 2020 年 05 月 07 日
面试考试可用,十大排序算法

微信公众号:一起学习大数据呀

关注可学习更多奇怪的知识!



前言

本文收集整理常见的十大排序算法,配套 Java 代码和视频短视频教程。帮助小伙伴们更快的理解和掌握。



不管你是为了应付考试,还是面试用,本文都可以帮到你,降低学习门槛,作者水平有限,难免遗漏错误,欢迎读者们留言指正。



1、冒泡排序

基本思想

每次比较两个相邻的元素,若顺序(从小到大或从大到小)“错误”就交换位置。



视频讲解

冒泡排序



代码实现

public static void bubbleSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。
boolean flag = true;
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) { //前面的数字大于后面的数字就交换
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false;
}
}
if (flag) { //没有数据交换,数组已经有序,退出排序
break;
}
}
}



2、选择排序



基本思想

每一趟从待排序的记录中选出最大(小)的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕。



视频讲解



选择排序 (空降06:33)



代码实现

//1 找到数组最大的数字,并且返回下标
public static int findMaxPos(int[] arr , int n){
int max = arr[0];
int pos = 0;
for (int i = 0; i < n; i++){
if (max < arr[i]){
max = arr[i];
pos = i;
}
}
return pos;
}
//2 让最大值与最后一个元素交换
public static void selectionSort(int[] arr, int n){
while(n > 1) { // 3 不断循环 1 和 2 步骤
int pos = findMaxPos(arr, n);
int temp = 0;
temp = arr[n - 1];
arr[n - 1] = arr[pos];
arr[pos] = temp;
n-- ;
}
}



3、插入排序



基本思想



将数组分为“已排序区间”和“未排序区间”。核心思想是提取“未排序区间”中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复该过程,直到排序区间中元素为空。



视频讲解



插入排序 空降(12:27)



代码实现

//1 选择已排序区间的后一个元宵插入
public void insert(int[] arr, int n){
int key = arr[n];
int i = n;
while (arr[i - 1] > key){ //若前面的元素 > 后面元素
arr[i] = arr[i -1]; // 前面元素抄写到后面元素位置
i--;
if (i == 0){//防止数组越界
break;
}
}
arr[i] = key; // 把要插入的元素归位
}
// 2 多趟插入
public void insertSort(int[] arr, int n){
if (n <= 1){
return ;
}
for (int i = 1; i < n; i++){ // 从第二个元素开始,第一个看成有序区域就好
insert(arr, i);
}
}



4、快速排序



基本思想

在数组中找到一个基准数,一般来说选第一个,然后加两个哨兵, i 和 j ,一个头一个尾.

i 从左到右扫描遇到大于 基准数 的数字停下, j 从右到左扫描,遇到小于 基准数 的停下.

然后 i 坐标的数与 j 坐标的数交换.



视频讲解

快速排序



代码实现

static void qucikSort(int left, int right) {
if (left > right){
return;
}
int i = left;
int j = right;
int povit = arr[left]; // 基准数
int temp;
while (i != j) {
while (arr[j] >= povit && i < j) {
j--;
}
while (arr[i] <= povit && i < j) {
i++;
}
if (i < j) {
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
//基准数归位
arr[left] = arr[i];
arr[i] = povit;
//递归
qucikSort(left, i - 1);
qucikSort(i + 1, right);
return;
}



快排的优化方案

1) 基准数优化

随机取基准数

三位数取中: 选取数组开头,中间和结尾的元素,通过比较,选择中间的值作为快排的基准。

2) 序列长度达到一定大小时,使用插入排序

3) 尾递归优化

4) 聚集元素



5、希尔排序



基本思想

希尔排序是插入排序的一种改进版,通过比较相距一定距离(增量)的元素工作(交换;各趟比较所用的距离随着算法减小而减小,当增量减至1时,整个文件恰被分成一组,算法便终止。



视频讲解

希尔排序



代码实现

public class ShellSort {
public static void main(String[] args) {
int[] arr = {1, 3, 7, 2, 8, 6, 4, 9};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 希尔排序 针对有序序列在插入时采用移动法。
*
* @param arr
*/
static void shellSort(int[] arr) {
//增量 gap,并逐步缩小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//从第 gap 个元素,逐个对其所在组进行直接插入排序操作
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[j];
//j - gap 同组相隔的元素没数组越界;
//arr[j - gap] > temp 前面的元素 > 后面的元素
while (j - gap >= 0 && arr[j - gap] > temp) {
//把前面元素抄写到后面的位置
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
}



6、归并排序



基本思想

该算法采用经典的分治(divide-and-conquer)策略,它将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之。



视频讲解



归并排序



代码实现

public class MergeSort {
public static void main(String[] args) {
int[] a = {6, 8, 10, 9, 4, 5, 2, 7};
int L = 0;
int R = a.length - 1;
mergSort(a, L, R);
System.out.println(Arrays.toString(a));
}
static void mergSort(int[] arr, int L, int R) {
// 递归出口
if (L == R) {
return;
} else {
int M = (L + R) / 2;
mergSort(arr, L, M);
mergSort(arr, M + 1, R);
merge(arr, L, M + 1, R);
}
}
static void merge(int[] arr, int L, int M, int R) {
int left_size = M - L;
int right_size = R - M + 1;
int[] L_arr = new int[left_size];
int[] R_arr = new int[right_size];
// 1 填充左边的数组
for (int i = L; i < M; i++) {
L_arr[i - L] = arr[i];
}
// 2 右边填充数组
for (int i = M; i <= R; i++) {
R_arr[i - M] = arr[i];
}
// 3 合并
int i = 0, j = 0, k = L;
while (i < left_size && j < right_size) {
if (L_arr[i] > R_arr[j]) {
arr[k] = R_arr[j];
k++;
j++;
} else {
arr[k] = L_arr[i];
i++;
k++;
}
}
// 4 若右边数组已空,把剩余左边数组补上
while (i < left_size) {
arr[k] = L_arr[i];
i++;
k++;
}
// 5 若左边数组已空,同上
while (j < right_size) {
arr[k] = R_arr[j];
k++;
j++;
}
}
}



7、堆排序



基本思想

1)将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。

2)将其与末尾元素进行交换,此时末尾就为最大值。

3)将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了。



视频讲解



堆排序



代码实现

public class HeapSort {
public static void main(String[] args) {
int[] arr = {2,5,3,1,10,4};
heapSort(arr,arr.length);
for (int i : arr){
System.out.println(i + " ");
}
}
/***
* 交换函数
* @param arr
* @param i
* @param j
*/
static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/***
* 构建大顶堆 (父节点大于子节点)
* @param tree 数组(树)
* @param n 数组长度
* @param i 父节点
*/
static void heapify(int tree[], int n, int i){
// 递归出口
if (i >= n){
return;
}
//左孩子节点
int c1 = 2*i + 1;
//右孩子节点
int c2 = 2*i + 2;
// 假设 i 为最大值
int max = i;
// c1 < n 保证 c1 不出界
if (c1 < n && tree[c1] > tree[max]){
max = c1;
}
if (c2 < n && tree[c2] > tree[max]){
max = c2;
}
if (max != i){
swap(tree, max, i);
heapify(tree, n, max);
}
}
/***
* 自下而上构建堆
* @param tree 数组
* @param n 数组长度
*/
static void buidHeap(int[] tree, int n){
// 最后一个叶子节点
int last_node = n - 1;
// 对应的父节点
int parent = (last_node - 1)/2;
for (int i = parent; i >= 0 ; i--){
heapify(tree, n, i);
}
}
/***
* 堆排序
* @param tree
* @param n
*/
static void heapSort(int[] tree, int n){
// 1) 建一个堆
buidHeap(tree, n);
// 2) 从最后一个节点出发
for (int i = n - 1; i >= 0; i--){
// 3) 先交换一下根节点和最后一个节点
// i 表示最后一个节点
// 0 表示根节点
swap(tree, i, 0);
heapify(tree, i, 0);
}
}
}



8、计数排序



基本思想

计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。

注意:适合量大且范围小的数据



视频讲解



计数排序



代码实现

public class CountSort {
public static void main(String[] args) {
int[] arr = {2 , 4, 2, 3, 7, 1, 1, 0, 0, 5, 6, 3, 7, 8, 9 };
System.out.println(Arrays.toString(countSort(arr)));
}
/***
* 计数排序
* @param arr
* @return
*/
static int[] countSort(int[] arr) {
//目标数组
int[] result = new int[arr.length];
//计数数组
int[] count = new int[10];
//对原数组记录各元素出现的次数
for (int i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
System.out.println(Arrays.toString(count));
//累加数组 看视频吧,我解释不了
for (int i = 1; i < count.length; i++) {
count[i] = count[i] + count[i - 1];
}
System.out.println(Arrays.toString(count));
//有点像众神归位
for (int i = arr.length - 1; i >= 0; i--) {
result[--count[arr[i]]] = arr[i];
}
return result;
}
}



9、桶排序



基本思想

1)将要排序的数据分到几个有序的桶里,每个桶里的数据再单独进行快速排序。

2)桶内排完序之后,再把每个桶里的数据按照顺序依次取出,组成的序列就是有序的了。



视频讲解



桶排序



代码实现

static void bucketSort(int[] arr) {
//找到数组的最大值和最小值,用来计算映射函数
int min = arr[0];
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
//计算出桶的数量
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<Integer>());
}
//将属于同一个桶的元素放入对应的桶
for (int i = 0; i < arr.length; i++) {
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
//对每个桶进行排序
for (int i = 0; i < bucketArr.size(); i++) {
Collections.sort(bucketArr.get(i));
}
System.out.println(bucketArr.toString());
}



10、基数排序



基本思想

桶思想的一种,非比较排序,多关键字排序。

对数据的每一位(个位,十位,百位)进行桶排序或计数排序,对每位排序后结果就是有序的。



视频讲解

基数排序



代码实现

public class RadixSort {
public static void main(String[] args) {
int[] arr = {421, 240, 115, 532, 305, 430, 324};
//1 先求最高位数
int maxDigit = getMaxDigit(arr);
System.out.println(Arrays.toString(radixSort(arr, maxDigit)));
}
/**
* 获取最高位数
*/
private static int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}
private static int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
static int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
static int[] radixSort(int[] arr, int maxDigit) {
int[] result = new int[arr.length];
int[] count = new int[10];
// maxDigit 是数字中最大的位数
for (int i = 0; i < maxDigit; i++) {
//求余数,如个位,十位
int division = (int) Math.pow(10, i);
System.out.println(division);
for (int j = 0; j < arr.length; j++) {
int num = arr[j] / division % 10;
System.out.println(num + " ");
count[num]++;
}
//跟计数排序一样,先做累加数组,再复制(我也有点懵)
for (int m = 1; m < count.length; m++) {
count[m] = count[m] + count[m - 1];
}
for (int n = arr.length - 1; n >= 0; n--) {
int num = arr[n] / division % 10;
result[--count[num]] = arr[n];
}
System.arraycopy(result, 0, arr, 0, arr.length);
Arrays.fill(count, 0);
}
return result;
}
}






参考文献

1: 十大经典排序算法(动图演示)

2: 图解排序算法(四)之归并排序

3:【干货】史上最好的排序和数据结构入门



发布于: 2020 年 05 月 07 日 阅读数: 54
用户头像

菜是原罪 2018.09.17 加入

一个练习两年半的 JAVA 实习生

评论

发布
暂无评论
面试考试可用,十大排序算法