【算法】八大排序算法---MapleYe

注：

1）本文的所有图解均来自百度图片搜索，侵删 2）代码使用java编写 3）本文主要用于记录我对排序算法的理解，若有错误，望指出

1、冒泡排序思路

1）每次循环中，比较相邻的两个数，大的往下沉，那么一轮循环后，最大的数就放在最后了 2）由于上一次循环，已经把最大的数沉到最后了，因此下一次循环的需要比较的元素个数就减1 3）直至需要比较的元素个数为0

图解

冒泡排序

代码实现 public static void bubleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 每次循环次数n，每次都比上一次少排一次 for (int e = arr.length - 1; e > 0; e--) { for (int i = 0; i < e; i++) { if (arr[i] > arr[i + 1]) { int tmp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = tmp; } } } }2、直接选择排序思路

对于n次循环，每一次循环都把最小的数，交换到最前面的位置

图解

直接选择排序

代码实现 public static void selectionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for(int i = 0; i < arr.length - 1; i++) { // 默认认为第一个数为最小的index int minIndex = i; for(int j = i + 1; j < arr.length; j++) { if (arr[minIndex] > arr[j]) { // 比较更新最新的index minIndex = j; } } // 不相同就交换 if (minIndex != i) { int tmp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = tmp; } } }3、直接插入排序思路

从0开始，逐步从0~arr.length的区域插入一个数，使得原来的数组有序

图解

直接插入排序

代码实现 public static void insertSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for(int i = 1; i < arr.length; i++) { // 每次子循环中，j代表当前有序数组中，最大的index // 因此插入一个数，都要与最大的index，比较交换，直至这个数放在了正确的位置 for(int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { int tmp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = tmp; } } }4、希尔排序

希尔排序也是一种插入排序，是改进后插入排序，也称为缩小增量排序

思路

1） 对数组，按一定的增量gap分组 2）分别对分组进行直接插入排序 3）直至增量gap减少至0，整个排序完成

图解

希尔排序

代码实现 public static void shellSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int gap = arr.length / 2; gap > 0; gap /= 2) { // 开始对每个分组进行直接插入排序 for(int i = gap; i < arr.length; i++) { int j = i; // 从gap元素开始，逐个对其所在组进行直接插入排序 while(j - gap >= 0 && arr[j] < arr[j - gap]) { int tmp = arr[j - gap]; arr[j - gap] = arr[j]; arr[j] = tmp; j -= gap; } } } }5、桶排序-计数排序，基数排序计数排序思路

1）例如：在0~99的范围内，我们划分了100个桶，并且对桶进行编号 2）在遍历过程中，把每个数放在对应的桶里，那么一次遍历后，每个桶就各自装有其范围的数了，因此时间复杂度只要O(N) 3）最后遍历桶，“倒出”里面装有的数字

图解

计数排序

代码实现 /// 只考虑>0的情况 public static void bucketSort(int arr[]) { int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { max = Math.max(max, arr[i]); } // 准备桶，确保桶可以装完所有数据 // 这样bucket[num]就代表num出现的次数 int[] bucket = new int[max + 1]; for(int i = 0; i < arr.length; i++) { bucket[arr[i]]++; } int i = 0; // 把桶里面的数据一次倒出来 for (int j = 0; j < bucket.length; j++) { while (bucket[j] > 0) { arr[i++] = j; bucket[j]--; } } }基数排序思路

1）将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。 2）然后，从最低位开始，依次进行一次排序。 3）这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

图解

基数排序

代码实现 public static void sort(int[] arr) { if (arr == null || arr.length < 2) { return; } // 求最大数，获得数组中最大的位数 int max = Integer.MIN_VALUE; for(int i = 0; i < arr.length; i++) { max = Math.max(arr[i], max); } int maxbits = 0; while(max != 0) { max /= 10; maxbits++; } radixSort1(arr, maxbits); } public static void radixSort1(int[] arr, int maxbits) { int max = 1; int n = 1; while(n != maxbits) { max *= 10; n++; } n = 1; // 一个二维数组[i][j]，i表示位数，j是其对应的个数 int[][] bucket = new int[10][arr.length]; // 用于保存每个位数的在bucket数组中的个数 int[] count = new int[10]; while(n <= max) { for(int i = 0; i < arr.length; i++) { // 取得n位的位数，例如n=1，取个位数，n=2，取十位数 int digit = (arr[i] / n) % 10; // 放进对应的桶里 bucket[digit][count[digit]] = arr[i]; // 该位数的计数+1 count[digit]++; } int k = 0; for(int i = 0; i < bucket.length; i++) { // 表示这个桶里有数据 if(count[i] != 0) { // 全部倒出来 for(int j = 0; j < count[i]; j++) { arr[k++] = bucket[i][j]; } } // 归零 count[i] = 0; } n *= 10; } }桶排序的扩展

相邻最大差值问题，详文见 https://www.jianshu.com/p/e507609ba606

6、堆排序

堆排序需要了解堆的概念，构建堆，调整堆等概念，因此独立写了一份blog。地址如下： https://www.jianshu.com/p/6513de30c887

7、快速排序

同样地，我也单独写了一篇blog，文中还提到了快排的优化。地址如下： https://www.jianshu.com/p/9494a3ba1555

8、归并算法

也是单独写了一篇blog，文中提到了归并排序的两个延伸算法问题。地址如下： https://www.jianshu.com/p/bf854d8160e9

总结

最后对时间复杂度，空间复杂度，稳定性作一个总结

---来自腾讯云社区的---MapleYe