基础排序算法详解与优化-白红宇

文章图片存储在GitHub，网速不佳的朋友，请看或者来我的技术小站

1. 谈谈基础排序

常见的基础排序有选择排序、冒泡排序和插入排序。众所周知，他们的时间复杂度是 O(n*n)。

但是，现在要重新认识一下基础排序算法，尤其是“插入排序”：在近乎有序的情况下，插入排序的时间复杂度可以降低到 O(n)的程度。

因此，在处理系统日志的任务中，因为日志记录是按照时间排序，但偶尔会有几条是乱序，此时使用插入排序再好不过。而对于高级排序算法，一个常见的优化就是利用插入排序做局部数据排序优化。

2. 算法实现

排序算法被封装在了SortBase.h中的SortBase命名空间中，以实现模板化和防止命名冲突。如下图所示：

2.1 选择排序

假设从小到大排序，那么，刚开始指针指向第一个数据，选择从当前指针所指向数据到最后一个数据间最小的数据，将它放在指针位置。

指针后移一位，重复上述步骤，直到指针移动到最后一个数据。

这种重复保证了每次，指针前面的数据都是从小到大排好顺序的数据。所以，从头到尾扫描一遍，自然排好序了。

代码如下：

template 
    
     void selectionSort(T arr[], int n) {  int minIndex = -1;  for(int i = 0; i < n; i++) {    minIndex = i;    for(int j = i+1; j < n; ++j) {      if(arr[j] < arr[minIndex]) {        minIndex = j;      }    }    swap(arr[i], arr[minIndex]);  }}复制代码

2.2 冒泡排序

假设排序是从小到大排序。

我一直感觉冒泡排序是和选择排序反过来了（如果说错请指正）。因为选择排序是每次选择最小的数据，放到当前指针位置；而冒泡排序是把不停交换相邻数据，直到把最大的数据“冒泡”到应该到的位置。

优化的地方是：记录每次交换的最后位置，在此之后的元素在下一轮扫描中均不考虑。因为交换的最后位置之后的元素已经是从小到大排序好了的。

在实现过程中，因为需要不停交换相邻两个数据，因此，消耗了很多额外时间。

template 
    
     void bubbleSort(T arr[], int n) {  int newn;  do {    newn = 0;    for(int i = 1; i < n; i++) {      if(arr[i-1] > arr[i]) {        swap(arr[i-1], arr[i]);        // 优化        newn = i;      }    }    n = newn; // 不再考虑 newn 后的数据  } while (newn > 0);}复制代码

2.3 插入排序

插入排序容易和上面两个算法搞混。可以类比打扑克牌时候的对扑克牌进行排序：我们会先排序前 1 张、然后是前 2 张、前 3 张 ... 一直到前 n 张。算法实现显然是双重循环，如下所示：

template 
    
     void insertionSort(T arr[], int n) {  for(int i = 1; i < n; i++) {    for(int j = i ; j > 0; j--) {      if(arr[j - 1] > arr[j]) {        swap(arr[j], arr[j - 1]);      } else {        break; // 优化：已经保证之前都是正常排序，直接跳出即可      }    }  }}复制代码

显然，插入排序也能在局部排好序的情况下跳出循环（代码中的优化），以减少算法消耗时间。

然而上述算法其实跑分并比不上选择排序，因为swap(arr[j], arr[j - 1]);这行代码交换了一次，相当于赋值 3 次，在大数据量情况下，比较消耗时间。

优化: 内层循环，每次保存arr[i], 在检测到当前数据大于arr[i]的时候，后移一位当前元素arr[j] = arr[j-1];。当跳出内层循环时，直接将保存的arr[i]赋值给arr[j]即可。

template 
    
     void insertionSort(T arr[], int n) {  for(int i = 1; i < n; i++) {    T e = arr[i];    int j = i ;    for(; j > 0 && arr[j-1] > e; j--) {      arr[j] = arr[j-1];    }    arr[j] = e;  }}复制代码

3. 性能测试

首先利用 SortTestHelper::generateRandomArray函数生成大量无序随机数据，然后进行排序和时间测定。代码如下：

#include 
    
     #include "SortHelper.h"#include "SortBase.h"#include "SortAdvance.h"using namespace std;int main() {  int n = 50000, left = 0, right = n;  int *arr = SortTestHelper::generateRandomArray
     
      (n, left, right);  int *brr = SortTestHelper::copyArray
      
       (arr, n);  int *crr = SortTestHelper::copyArray
       
        (arr, n);  SortTestHelper::testSort
        
         (arr, n, SortBase::selectionSort
         
          , "selection sort"); SortTestHelper::testSort
          
           (brr, n, SortBase::insertionSort
           
            , "insertion sort"); SortTestHelper::testSort
            
             (crr, n, SortBase::bubbleSort
             
              , "bubble sort"); delete[] brr; delete[] arr; delete[] crr; return 0;}复制代码

运行结果如下图所示：

除了大量无序随机数据，类似于系统日志的数据就是基本有序的大量数据。此时，测试代码如下：

#include 
    
     #include "SortHelper.h"#include "SortBase.h"#include "SortAdvance.h"using namespace std;int main() {  int n = 50000, left = 0, right = n;  int *arr = SortTestHelper::generateNearlyOrderedArray
     
      (n, 10);  int *brr = SortTestHelper::copyArray
      
       (arr, n);  int *crr = SortTestHelper::copyArray
       
        (arr, n);  SortTestHelper::testSort
        
         (arr, n, SortBase::selectionSort
         
          , "selection sort"); SortTestHelper::testSort
          
           (brr, n, SortBase::insertionSort
           
            , "insertion sort"); SortTestHelper::testSort
            
             (crr, n, SortBase::bubbleSort
             
              , "bubble sort"); delete[] brr; delete[] arr; delete[] crr; return 0;}复制代码

如图所示，插入排序的只用了 0.002 秒。在这种数据情况下，插入排序的时间复杂度近似 O(N)，绝对快于高级排序的 O(NlogN)。除此之外，还保证了稳定性。

4. 感谢

本篇博客是总结于慕课网的的笔记，liuyubobobo 老师人和讲课都很 nice，欢迎去买他的课程。

5. 更多内容

快速排序和归并排序：

堆与堆排序：