常见排序列表

中文名称 英文名称 平均时间复杂度 最坏时间复杂度 最好时间复杂度 空间复杂度 稳定性
选择排序 Selection n2 n2 n2 1 不稳
冒泡排序 Bubble n2 n2 n 1 稳
插入排序 Insertion n2 n2 n 1 稳
堆排序 heap n log2 n nlog2n n log2 n 1 不稳
希尔排序 Shell n1.3 n2 n 1 不稳
归并排序 Merge n log2 n n log2n n log2 n n 稳
快速排序 Quick n log2 n n2 n log2 n log2 n 不稳
桶排序 Bucket n + k n2 n n + k 稳
计数排序 Counting n + k n + k n + k n + k 稳
基数排序 Radix n * k n * k n * k n + k 稳

排序算法

比较类排序

交换排序

冒泡排序

从第一个数开始，比较相邻的两个数，前一个比后一个大，则交换两个数位置 

  1. // 冒泡排序
  2. public class BubbleSort {
  3.     public static void main(String[] args) {
  4.         int[] a = {6,3,1,4,5,8,7,9,2};
  5.         sort(a);
  6.         print(a);
  7.     }
  9.     static void sort(int[] arr) {
  10.         for (int i = arr.length - 1; i > 0; i--) {
  11.             findMax(arr,i);
  12.         }
  13.     }
  15.     static void findMax(int[] arr, int max) {
  16.         for (int i = 0; i < max; i++) {
  17.             if (arr[i + 1] < arr[i]) {
  18.                 swap(arr, i, i + 1);
  19.             }
  20.         }
  21.     }
  23.     static void swap(int[] arr, int i, int j) {
  24.         int temp = arr[i];
  25.         arr[i] = arr[j];
  26.         arr[j] = temp;
  27.     }
  29.     static void print(int[] arr) {
  30.         for (int i = 0; i < arr.length ; i++) {
  31.             System.out.print( arr[i] + " ");
  32.         }
  33.     }
  34. }

这个算法仍然有优化空间，在数组为[1,2,3,4,5,6,7,8,9]时将时间复杂度降低为O(n)

时间复杂度

  • 消耗时间最多的应该是这两个循环嵌套，则为 O(n²)
  1. static void sort(int[] arr) {
  2.     for (int i = arr.length - 1; i > 0; i--) {
  3.         findMax(arr,i);
  4.     }
  5. }
  7. static void findMax(int[] arr, int max) {
  8.     for (int i = 0; i < max; i++) {
  9.         if (arr[i + 1] < arr[i]) {
  10.             swap(arr, i, i + 1);
  11.         }
  12.     }
  13. }

空间复杂度
O(1)

最坏时间复杂度
O(n²)

最好时间复杂度
O(n)

稳定性
两两进行比较，铁定是稳定的。

快速排序
  1. //快速排序
  2. public class QuickSort {
  3.     public static void main(String[] args) {
  4.         int[] arr = {2,5,7,8,9,11,34,6,3,64,4,23,54,1,10};
  5.         sort(arr);
  6.     }
  8.     static void sort(int[] arr) {
  9.         int random = new Random().nextInt(arr.length);
  10.         System.out.println("随机数：" + random);
  12.         for (int i = 0; i < arr.length; i++) {
  13.             if (arr[i] < arr[random]) {
  15.             }
  16.         }
  17.     }
  19.     static void print(int[] arr) {
  20.         for (int i = 0; i < arr.length; i++) {
  21.             System.out.print(arr[i] + " ");
  22.         }
  23.     }
  24. }

插入排序

简单插入排序

从后往前，将小的插到大的前面，将后面的整体后移。

  1. // 插入排序
  2. public class InsertionSort {
  3.     public static void main(String[] args) {
  4.         int[] a = {6,3,1,4,5,8,7,9,2};
  5.         sort(a);
  6.         print(a);
  7.     }
  9.     static void sort(int[] arr) {
  10.         // 选择第i个数字
  11.         for (int i = 1; i < arr.length; i++) {
  12.             compare(arr,i);
  13.         }
  14.     }
  16.     static void compare (int[] arr, int point) {
  17.         // 将指定数字插到比自己大的数字前面去
  18.         for (int i = point; i > 0 && arr[i] < arr[i-1]; i--) {
  19.             swap(arr,i,i-1);
  20.         }
  21.     }
  23.     static void compare2 (int[] arr, int point) {
  24.         int temp = arr[point];
  25.         for (int i = point; i > 0; i--) {
  26.             if (arr[i] < arr[i-1]) {
  27.                 arr[i - 1] = arr[i];
  28.             }
  29.         }
  30.         arr[point]=temp;
  31.     }
  34.     static void swap(int[] arr, int i, int j) {
  35.         int temp = arr[i];
  36.         arr[i] = arr[j];
  37.         arr[j] = temp;
  38.     }
  40.     static void print(int[] arr) {
  41.         for (int i = 0; i < arr.length ; i++) {
  42.             System.out.print( arr[i] + " ");
  43.         }
  44.     }
  45. }

时间复杂度
O(n²)

空间复杂度
O(n)

最坏时间复杂度
O(n²)

最好时间复杂度
O(n)

稳定性
稳定

  • 冒泡
    • 基本不用,太慢
  • 选择:
    • 基本不用,不稳
  • 插入排序:
    • 样本小且基本有序的时候效率比较高

希尔排序

改进的插入排序，选择固定的数字，依次减少，每次以该数字为间隔进行排序

  1. // 希尔排序
  2. public class ShellSort {
  3.     public static void main(String[] args) {
  4.         int[] arr = {2,5,7,8,9,11,34,6,3,64,4,23,54,1,10};
  5.         sort(arr);
  6.         print(arr);
  7.     }
  9.     public static void sort(int[] arr) {
  10.         int h = 1;
  11.         while (h <= arr.length / 3) {
  12.             h = 3*h +1;
  13.         }
  14.         for (int gap = h; gap > 0; gap = (gap-1)/3) {
  16.             for (int i = gap; i < arr.length; i++) {
  17.                 for (int j = i; j > gap - 1; j -= gap) {
  18.                     if (arr[j - gap] > arr[j]) {
  19.                         swap(arr, j - gap, j);
  20.                     }
  21.                 }
  22.             }
  23.         }
  24.     }
  26.     static void swap(int[] arr, int i, int j) {
  27.         int temp = arr[i];
  28.         arr[i] = arr[j];
  29.         arr[j] = temp;
  30.     }
  32.     static void print(int[] arr) {
  33.         for (int num : arr) {
  34.             System.out.print(num + " ");
  35.         }
  36.     }
  37. }

选择排序

从第一个开始和后面的依次比较，将每次最小的放到前面，使数组从小到大排列

简单选择排序
  1. // 选择排序
  2. public class SelectionSort {
  4.     public static void main(String[] args) {
  5.         int[] arr = {6,3,1,4,5,8,7,9,2};
  6.         sort(arr);
  7.         print(arr);
  8.     }
  10.     static void sort(int[] arr) {
  12.         int[] array = arr;
  14.         for (int i = 0; i < array.length - 1; i++) {
  15.             int minPos = i;
  16.             for (int j = i + 1; j < array.length; j++) {
  17.                 minPos = array[j] < array[minPos] ? j : minPos;
  18.             }
  19.             swap(array,i,minPos);
  20.         }
  21.     }
  23.     static void swap(int[] arr, int i, int j) {
  24.         int temp = arr[i];
  25.         arr[i] = arr[j];
  26.         arr[j] = temp;
  27.     }
  29.     static void print(int[] array) {
  30.         for(int num : array) {
  31.             System.out.print(num + " ");
  32.         }
  33.     }
  34. }
  36. class SelectionSort2 {
  38.     public static void main(String[] args) {
  39.         int[] arr = {6,3,1,4,5,8,7,9,2};
  41.         int minPos = 1, maxPos = arr.length-1;
  43.         for (int i = 0; i < (arr.length)/2; i++){
  45.             for (int j = 0; j < arr.length; j++) {
  46.                 minPos = arr[j] < arr[minPos] ? j : minPos;
  47.             }
  49.             int templ = arr[i];
  50.             arr[i] = arr[minPos];
  51.             arr[minPos] = templ;
  54.             for (int k = arr.length-1; k >= 0; k--) {
  55.                 maxPos = arr[k] > arr[maxPos] ? k : maxPos;
  56.             }
  57.             int tempr = arr[arr.length-1];
  58.             arr[arr.length-1] = arr[maxPos];
  59.             arr[maxPos] = tempr;
  61.             System.out.println("mixPos:" + minPos + "==="+ "maxPos:" + maxPos + "==");
  63.             for (int num : arr) {
  64.                 System.out.print(num + " ");
  65.             }
  66.             System.out.println();
  67.         }
  69.     }
  70. }

时间复杂度 

  1. public class SelectionSort {
  2.     public static void main(String[] args) {
  3.         // 每个都需要进行初始化，不计入算法时间
  4.         int[] array = {6,3,1,4,5,8,7,9,2};
  6.         //      O(1)        O(n)               O(n)
  7.         for (int i = 0; i < array.length - 1; i++) {
  8.             // O(n)
  9.             int minPos = i;
  10.             //         O(n)            O(n²)      O(n²)
  11.             for (int j = i + 1; j < array.length; j++) {
  12.                 minPos = array[j] < array[minPos] ? j : minPos;
  13.                 // (n-1)+(n-2)+……+1 = (n*(n-1))/2 = n²/2 - n/2 + T（常数）（舍去常数，低位项） = O(n²)
  14.             }
  15.             // 不计入算法时间
  16.             System.out.println("minPos：" + minPos);
  18.             // O(n)
  19.             swap(array,i,minPos);
  21.             // 不计入算法时间
  22.             System.out.println("经过第" + i + "次循环，数组内容为：");
  23.             // 不计入算法时间
  24.             print(array);
  25.         }
  26.     }
  27. }

空间复杂度

  • 需要用到的额外空间，临时变量之类的一直需要，而且用完即无，因此不需要考虑，可以考虑有无新数组之类的创建作为排序赋值、反转

消耗的空间也就是 O(1)

最好情况
至少也要O(n²)

最坏情况
最坏也是O(n²)

稳定性
不稳：两个相等的数会经过排序可能造成相对位置发生变化

验证算法一对数器

如何验算你的算法是否正确?

  1. 肉眼观察
  2. 产生足够多随机样本
  3. 用确定正确的算法计算样本结果

  4. 对比被验证算法的结果 ```java // 选择排序 public class SelectionSort { static void sort(int[] arr) {

    1.  // 每个都需要进行初始化，不计入算法时间
    2.  int[] array = arr;
    3.  /*     int[] array = {6,3,1,4,5,8,7,9,2};*/
    5.  //      O(1)        O(n)               O(n)
    6.  for (int i = 0; i < array.length - 1; i++) {
    7.      // O(n)
    8.      int minPos = i;
    9.      //         O(n)            O(n²)      O(n²)
    10.      for (int j = i + 1; j < array.length; j++) {
    11.          minPos = array[j] < array[minPos] ? j : minPos;
    12.          // (n-1)+(n-2)+……+1 = (n*(n-1))/2 = n²/2 - n/2 + T（常数）（舍去常数，低位项） = O(n²)
    13.      }
    14.      // 不计入算法时间
    15.      System.out.println("minPos：" + minPos);
    17.      // O(n)
    18.      swap(array,i,minPos);
    20.      // 不计入算法时间
    21.      System.out.println("经过第" + i + "次循环，数组内容为：");
    22.      // 不计入算法时间
    23.      print(array);
    24.  }

    }

    static void swap(int[] arr, int i, int j) {

    1.  int temp = arr[i];
    2.  arr[i] = arr[j];
    3.  arr[j] = temp;

    }

    static void print(int array[]) {

    1.  for(int num : array) {
    2.      System.out.print(num + " ");
    3.  }

    } }

// 对数器 class DataChecker { // 创建一个随机数组 static int[] generateRandomArray() { Random r = new Random();

  1.     int[] arr = new int[10];
  3.     for (int i = 0; i < arr.length; i++) {
  4.         arr[i] = r.nextInt(10);
  5.     }
  6.     return arr;
  7. }
  9. static void check() {
  10.     // 拷贝一份，后续做比较
  11.     int[] array = generateRandomArray();
  12.     int[] array2 = new int[array.length];
  13.     System.arraycopy(array,0,array2,0,array.length);
  15.     Arrays.sort(array);
  16.     SelectionSort.sort(array2);
  18.     boolean same = true;
  20.     for (int i = 0; i < array2.length; i++) {
  21.         if (array[i] != array2[i]) {
  22.             same = false;
  23.         }
  24.     }
  26.     System.out.println(same == true ? "right" : "wrong");
  28. }
  30. public static void main(String[] args) {
  31.     check();
  32. }

}

  6. <a name="141c7256"></a>
  7. ##### 堆排序
  9. <a name="95566613"></a>
  10. #### 归并排序
  12. <a name="fddb0f4c"></a>
  13. ##### 二路归并排序
  14. ** 两个已经排好的数组，用两个指针分别依次进行比较，将每次比较小的依次放进新的数组中，若一个数组已经空，则另一个数组直接放入新数组中。  **
  15. ```java
  16. // 归并排序
  17. public class MergeSort {
  18.     public static void main(String[] args) {
  19.         int[] arr = {1,4,5,7,9,2,3,6,8};
  20.         sort(arr,0,arr.length-1);
  21.         print(arr);
  22.     }
  24.     public static void sort(int[] arr, int left, int right) {
  25.         if (left == right) {
  26.             return;
  27.         }
  28.         // 分成两半
  29.         int mid = left + (right-left)/2;
  30.         // 左部排序
  31.         sort(arr,left,mid);
  32.         // 右部排序
  33.         sort(arr,mid+1,right);
  35.         merge(arr,left,mid+1,right);
  36.     }
  38.     static void merge(int[] arr, int leftPrt, int rightPrt, int rightBound) {
  39.         int mid =  rightPrt - 1;
  40.         int[] temp = new int[rightBound - leftPrt + 1];
  42.         int i = leftPrt;
  43.         int j = rightPrt;
  44.         int k = 0;
  46.         while (i <= mid && j <= rightBound) {
  47.             temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
  48.         }
  50.         while (i <= mid) {
  51.             temp[k++] = arr[i++];
  52.         }
  53.         while (j <= rightBound) {
  54.             temp[k++] = arr[j++];
  55.         }
  56.         for (int m = 0; m < temp.length; m++) {
  57.             arr[leftPrt + m] = temp[m];
  58.         }
  59.     }
  61.     static void swap(int[] arr,int i,int j) {
  62.         int temp = arr[i];
  63.         arr[j] = arr[i];
  64.         arr[i] = temp;
  65.     }
  67.     static void  print(int[] arr) {
  68.         for (int num : arr) {
  69.             System.out.print(num + " ");
  70.         }
  71.     }
  72. }

递归：调用自身，但需要留出跳出去的条件，每次调用都会栈分配栈帧，然后栈帧在函数完成后依次消失。

多路归并排序

非比较类排序

计数排序

桶排序

基数排序