【原】你对排序算法了解多少

贪挽懒月 2022-06-20 发布于广东

展开全文

说起排序算法，可能大家会脱口而出：冒泡排序，选择排序。没错，这是我们最熟悉的两种排序算法，其实，排序算法远不止这些。而且，你之前写的冒泡、选择排序真的是最优的吗？

一、排序算法的分类

总的来说分为两大类，内部排序 和外部排序。

1、内部排序：

就是将需要排序的数据都加载到内存中，然后进行排序。内部排序又分为以下几类：

插入排序：包括直接插入排序和希尔排序；
选择排序：包括简单选择排序和堆排序；
交换排序：包括冒泡排序和快速排序；
归并排序
基数排序：桶排序的扩展

2、外部排序：

内部排序有个问题，假如现在要排序的数据有10亿个，服务器内存加载不了那么多的数据，那就得用外部排序了。外部排序就是先加载一部分，排完了再加载另外一部分，然后再合并。

二、常见的时间复杂度

时间复杂度从低到高依次有：

常数阶：O(1)
对数阶：O(logn)
线性阶：O(n)
线性对数阶：O(nlogn)
平方阶：O(n^2)
立方阶：O(n^3)
k次方阶：O(n^k)
指数阶：O(2^n)

接下来，就先看看大家最熟悉的冒泡排序和选择排序。为了避免篇幅过长，其他六种排序中的每一种都会用一篇单独的文章来介绍。

三、冒泡排序

时间复杂度为O(n^2)。

1、排序思想：

从前往后遍历待排序的序列，依次比较相邻元素的值，如果逆序，就交换位置。

2、案例：

假如现有一个待排序列：3, 9, -1, 10, 20，现要用冒泡排序算法将其从小到大排列，过程如下：

(1). 第一趟：

比较3和9，发现3比9小且3在前面，所以不改变位置，结果是3, 9, -1, 10, 20，同时两个指针都后移一位；
比较9和-1，交换它们的位置，结果是3, -1, 9, 10, 20，同时两个指针都后移一位；
比较9和10，不发生交换，结果是3, -1, 9, 10, 20，同时两个指针都后移一位；
比较10和20，不发生交换，结果是3, -1, 9, 10, 20，同时两个指针都后移一位；

一趟排序结束后，最大的数就排到最后去了。

(2). 第二趟：

经过第一趟，其实最后面那个数就是最大了，第二趟要做的就是在前面的四个数中找到最大的，放在倒数第二个的位置。

比较3和-1，交换位置，结果是-1, 3, 9, 10, 20，同时两个指针都后移一位；
比较3和9，不发生交换，结果是-1, 3, 9, 10, 20，同时两个指针都后移一位；
比较9和10，不发生交换，结果是-1, 3, 9, 10, 20，同时两个指针都后移一位；

经过第二趟，就将第二大的数排到了倒数第二位。

(3). 第三趟：

比较-1和3，不发生交换，结果是-1, 3, 9, 10, 20，同时两个指针都后移一位；
比较3和9，不发生交换，结果是-1, 3, 9, 10, 20，同时两个指针都后移一位；

经过这一趟，就将9排到了倒数第三位。

(4). 第四趟：

比较-1和3，不发生交换，结果是-1, 3, 9, 10, 20，同时两个指针都后移一位；

经过这趟，排序就结束了。

通过这个案例可以发现，总共需要进行元素个数减一次排序，并且每次比较的个数都在减少。而且，上面第二趟交换了3和-1的位置后，其实整个数组就已经是有序的了，后面的步骤都不用执行了。

3、代码实现：

public void sort(int[] arr) {
  // 外层控制控制要排序几趟
  int temp = 0;
  for(int i=0; i<arr.length-1; i++) {
   boolean flag = false; // 如果某一趟中没有一个元素发生交换，说明已经有序了，flag用来标识某一趟中是否发生过交换
   // 比较arr[j]和arr[j+1]的大小，如逆序，则交换。
   for(int j=0; j<arr.length-1-i; j++) {
    if (arr[j] > arr[j+1]) {
     temp = arr[j];
     arr[j] = arr[j+1];
     arr[j+1] = temp;
     flag = true;
    }
   }
   if (!flag) {
    break;
   }
  }
}

四、选择排序

时间复杂度也是O(n^2)，但是经测试，选择排序速度会比冒泡排序更快。

1、排序思想：

第一趟，用arr[0]依次跟其他元素比较，如果比arr[0]更小，那就认为该数最小，记住其下标，让其他元素跟该数比较，若又更小，那些又记住新的更小的那个数的下标……第一趟完成后，就找到了最小的数，并让它与arr[0]交换位置；
第二趟，用arr[1]跟其他元素比较，重复第一趟的步骤……

2、代码实现：

public static void sort(int[] arr) {
  // 外层循环控制第几趟比较
  for(int i=0; i<arr.length-1; i++) {
   int minNum = arr[i]; // 假定当前元素是最小的
   int minNumIndex = i; // 最小值的下标
   for(int j=i+1; j<arr.length; j++) {
    if (arr[j] < minNum) {
     // 如果arr[j]比之前认为的最小值还小，就把它当成新的最小值，并且记住下标
     minNum = arr[j];
     minNumIndex = j;
    }
   }
   // 一轮下来，交换arr[i]和最小值的位置
   // 如果最小值索引minIndex就等于i，那就不用交换
   if (minNumIndex != i) {
    arr[minNumIndex] = arr[i];
    arr[i] = minNum;
   }
  }
}