七种常用排序算法总结
1.冒泡排序（Bubble Sort）：
- 采用双循环的模式，外层循环控制冒泡次数，内层循环控制具体的冒泡操作，当前一个数大于后一个时，进行交换，每次内循环找到一个最大的数，然后放在最后，随着次数增加，内循环的次数依次减少；
- 排序后的数据是稳定的；
- 算法复杂度都是n^2；
- 不占用额外内存
- 具体代码实现：80000个数据排序时间为9100ms左右
package com.zha.wmls.sort; /** * 冒泡排序 * 每一轮找出一个最大的，放在最后面， * 稳定 * 时间复杂度为n^2 */ public class BubbleSort { static Boolean flag = false;//用于优化 public static void main(String[] args) { int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random()*80000000); } long beforTime = System.currentTimeMillis(); sort(arr); long afterTime = System.currentTimeMillis(); System.out.println(afterTime-beforTime); } static void sort(int[] a){ int temp=0; for (int i = 0; i < a.length-1; i++) { for (int j = 0; j < a.length-1-i; j++) { if (a[j]>a[j+1]){ flag = true; //优化效果不明显 temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } if (!flag){ break; //当某次执行时如果没有数据交换，表名已经排好，可以提前退出 }else { flag = false; } } } }
- 采用双循环模式，外层控制选择次数，内层进行具体选择操作。每一次外层循环选择出最小的数据，放在前面，当内循环中的数比此时的最小数小时，记录此时的坐标，然后最小数改为此数，当内循环结束后再进行交换；
- 排序后的数据是不稳定的，eg {5,3,5,2}，当第一次交换后，前面的5和2交换，两个5的相对位置就交换了
- 算法复杂度都是n^2；
- 不占用额外内存；
- 具体代码实现：80000个数据排序时间为2100ms左右
package com.zha.wmls.sort; /** * 选择排序 * 不稳定: 排序过后，相同数据的相对位置发生了变化(排序算法中，相同数据不要交换) * 每一轮只交换一次，并且是通过min判断，自然判断成功的次数相对更少 */ public class SelectionSort { public static void main(String[] args) { int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random()*80000000); } long beforTime = System.currentTimeMillis(); sort(arr); long afterTime = System.currentTimeMillis(); System.out.println(afterTime-beforTime); } static void sort(int[] a){ for (int i = 0; i < a.length-1; i++) { int minIndex = i; int min = a[i]; for (int j = i+1; j < a.length; j++) {//需要比较到最后一个数 // if (a[i]>a[j]) 这样写得到的是最后一个比a[i]小的数 if (min>a[j]){ min = a[j]; //把较小的数赋值给min，再用min继续和后面比较 minIndex = j; } } if(minIndex!=i){ a[minIndex] = a[i]; a[i] = min; } } } }
3.插入排序（Insert Sort）
- 把数据假设成两组数据，一个是有序的，一个是无序的，刚开始有序的表只有一个数，其余n-1个数在无序表里，每次循环从无序表中拿一个数放在有序表的正确位置。每一次排序时有序表中的数据已经排好了，减少了遍历次数；
- 排序后的数据是稳定的；
- 算法复杂度为n^2；
- 不占用额外内存；
- 具体代码实现：80000个数据排序时间为700ms左右
package com.zha.wmls.sort; /** * 插入排序 * 假设两个库，一个为有序，一个为无序，刚开始有序库只有一个，然后无序库里面依次比较， * 稳定 * 时间复杂度为n^2 */ public class InsertSort { static int arrCurrent; static int index; public static void main(String[] args) { int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random()*80000000); } long beforTime = System.currentTimeMillis(); insertSort(arr); long afterTime = System.currentTimeMillis(); System.out.println(afterTime-beforTime); } static void insertSort(int[] arr){ for (int i = 1; i < arr.length; i++) { //记录这个数字，再找到正确位置时再放入 arrCurrent = arr[i]; //防止下标越界 index = i-1; /** * 每一次比较时前面的数据已经是有序的了， */ while (index>=0&&arrCurrent<arr[index]){ //把更大的数放在后面,向不要急着交换位置，继续比较 //如果这里直接交换两个数的位置就变成了冒泡排序 arr[index+1] = arr[index]; index--; } //比较完毕，找到这个数字应该放的位置，放入 arr[++index]=arrCurrent; } } }
4.希尔排序
- 属于插入排序的一种优化，插入排序无序表中可能存在需要插入的数据教小，这种情况会导致数据前移次数过多，希尔排序的核心思想就是通过分组减少前移的次数从而提高效率；
- 排序后是不稳定的；
- 算法复杂度是个谜；
- 不占用额外内存；
- 具体代码实现：80000个数据排序时间为16ms左右
package com.zha.wmls.sort; /** * 插入排序的一种优化 * 稳定 * 时间复杂度是个未解之谜 */ public class ShellSort { public static void main(String[] args) { int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random()*80000000); } long beforTime = System.currentTimeMillis(); shellSort(arr); long afterTime = System.currentTimeMillis(); System.out.println(afterTime-beforTime); } //多用debug观察流程，发现问题 public static void shellSort(int[] arr){ for (int i = arr.length / 2; i > 0; i = i / 2) { for (int j = i; j < arr.length; j++){ int temp = arr[j]; int index = j; //就是插入排序，只不过多执行了几轮，但是每轮的次数明显减少来达到提高速度的目的 while (index - i >= 0 && temp < arr[index-i]){ arr[index] = arr[index-i]; index -= i; } arr[index] = temp; } } } }
5.快速排序
- 属于冒泡排序的一种改进，每一次排序，以中间的数字为基准，使得左边的数都小于这个数，右边的数都大于这个数，然后再递归左边和右边。（每一轮排序后，中间的数字的位置不一定还在中间）；
- 排序后的数据是不稳定的；
- 算法复杂度平均为n log n；
- 不占用额外内存；
- 具体代码实现：80000个数据排序时间为260ms左右
package com.zha.wmls.sort; /** * 快速排序 * 每一轮把中间位置的数字的位置找到 * 时间复杂度为nlogn */ public class QuickSort { public static void main(String[] args) { int[] arr = new int[8000000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random() * 80000000); } long beforTime = System.currentTimeMillis(); quickSort(arr, 0, arr.length - 1); long afterTime = System.currentTimeMillis(); System.out.println(afterTime - beforTime); } public static void quickSort(int[] arr, int left, int right) { //获得需要排序的最左边和最右边的下标 //left和right用来记录需要排序的两个边界，l和r表示移动的光标 int l = left; int r = right; //获得最中间的数据 int midle = arr[(left + right) / 2]; //临时变量，用作数据交换 int temp; /* * 最终得到的效果是以最中间的数据为界限，左边都小于，右边都大于 * 但是这个最中间的数排序结束后不一定在最中间， */ while (true) { //找到左边的大于arr[midle]的数 while (arr[l] < midle) l++; //从最右边开始找到小于arr[midle]的数 while (arr[r] > midle) r--; if (l >= r) { break; } //交换左右的数据 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; /* * 当arr[l]已经到达arr[midle]，而右边没有到达的情况， * 说明此时左边已经全部比arr[midle]小，交换后的数据 * 实际上只有l~r之间没有比较，继续从l++开始和arr[midle] * 比较即可 */ if (midle == arr[r]) { l++;//把l左移一位 } //与上面同理 if (midle == arr[l]) { r--; } } /* * 这里如果写l--,r++的话如果有相同数据会无限循环 */ if (l == r) { l++; r--; } /* * 以middle为界限，左边比较完之后再比较右边 * 类似于二分树杈的思想 */ if (left < r) { quickSort(arr, left, r); } if (l < right) { quickSort(arr, l, right); } } }
6.归并排序（Merger Sort）
- 采用分治的思想，先把数据分到最小，然后两两排序，然后往上合并。实际实现中通过递归实现，每一次递归实际上都是把左边拍完序再排右边，然后再向上整合。
- 排完后的数据是稳定的；
- 算法复杂度都为 n log n；
- 需要占用额外空间，因为需要一个临时数组用来存储临时数据；
- 具体代码实现：80000个数据排序时间为350ms左右
package com.zha.wmls.sort; /** * @ClassName MergerSort * @Desc 归并排序，采用先分后治的思想 * @Author wmls * @Date 2021/6/21 10:29 * @Version 1.0 */ public class MergerSort { public static void main(String[] args) { //测试效率 int[] arr = new int[8000000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random() * 80000000); } int[] temp = new int[arr.length]; long beforTime = System.currentTimeMillis(); mergerSort(arr, 0, arr.length - 1, temp); long afterTime = System.currentTimeMillis(); System.out.println(afterTime - beforTime); // 350ms左右 } /** * 通过边分边治的思想，并不是所有分完之后再治， */ public static void mergerSort(int[] arr, int left, int right, int[] temp) { if (left < right) { int middle = (left + right) / 2; //左边分，直到分到最小 mergerSort(arr, left, middle, temp); //右边分 mergerSort(arr, (middle + 1), right, temp); //当前面两个递归都不成立时执行一次，一共执行right次 sort(arr, left, right, middle, temp); } } /** * @param arr 需要排序的数组 * @param left 左边数组第一位的下标 * @param right 数组最右边的下标，可用于判断右边的数据是否到达最后一个 * @param middle 用于找到右边第一个数的下标和判断左边数据是否到达最后一个 * @param temp 临时数组，用来临时存放排序完成的数 */ //编码格式，多个参数逗号后面必须有空格 private static void sort(int[] arr, int left, int right, int middle, int[] temp) { int l = left; //无论是奇数还是偶数个，均分后都是左边个数≤右边 int r = middle + 1; int t = 0; //排序，当有一边已经没有数据时跳出 while (l <= middle && r <= right) { if (arr[l] < arr[r]) { temp[t] = arr[l]; t++; l++; } else { temp[t] = arr[r]; t++; r++; } } //此时左边下标还没有到最后一个，把左边剩余数据存入temp while (l <= middle) { temp[t] = arr[l]; t++; l++; } //与上面同理，右边下标还没到最后一个，把右边剩余数据存入temp while (r <= right) { temp[t] = arr[r]; t++; r++; } //将排序好的temp数组放回原数组 t = 0; /* * 不能这样写，因为每一次治都会利用temp数组，而temp数组的下标是从零开始， * 而且每一次使用到的temp数组的下标为0~right * arr数组的下标每次都从left到right, */ // while (t < arr.length){ // arr[t] = temp[t]; // t++; // } int tempLeft = left; while (tempLeft <= right) { arr[tempLeft] = temp[t]; t += 1; tempLeft += 1; } } }
7.基数排序
- ~~~~~~~~
- 排完后的数据是稳定的；
- 平均时间复杂度为n+k；
- 需要占用额外空间，需要一个二维数组来存放数据；
- 具体代码实现：80000个数据排序时间为28ms左右
package com.zha.wmls.sort; /** * @ClassName RadixSort * @Desc 基数排序 * @Author wmls * @Date 2021/6/21 15:37 * @Version 1.0 */ public class RadixSort { public static void main(String[] args) { int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random()*80000000); } long beforTime = System.currentTimeMillis(); radixSort(arr); long afterTime = System.currentTimeMillis(); System.out.println(afterTime-beforTime); } /** * 通过一个二维数组，每次把数放在二维数组里，然后再排序 * @param arr */ public static void radixSort(int[] arr){ int max = arr[0]; for (int i = 1; i < arr.length; i++) { if (max < arr[i]){ max = arr[i]; } } //得到数字的长度 int count = (max + "").length(); for (int k = 0, num = 1; k < count; k++, num = num*10){ int[][] bucketArr = new int[10][arr.length]; //用来表示每个桶中存放了几个数据 int[] bucketIndexArr = new int[10]; for (int value : arr) { int n = value / num % 10; //放入到对应的桶中 bucketArr[n][bucketIndexArr[n]++] = value; } //把桶里的数据放回原数组，需要用到双循环 int index = 0; for (int i = 0; i < 10; i++) { //桶中有数据才执行 if (bucketIndexArr[i] != 0){ for (int j = 0; j < bucketIndexArr[i]; j++) { arr[index++] = bucketArr[i][j]; } } //将桶中的数据给到arr中后就清零，下一轮循环继续使用 bucketIndexArr[i] = 0; } } } }
总结
- 从速度上来说，冒泡，选择，属于一个量级，插入属于一个量级，其他排序属于一个量级；随着数据量越来越多，排序速度依次为：希尔，归并，快速，基数，但是基数排序需要一个二维数据的空间，当测试8000万个数据时内存就不够用；
- 从稳定性来说，选择排序是不稳定，希尔，快速排序也是不稳定；
- 具体选择哪种排序方式应该根据实际情况；
版权声明：本文为wmls原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。