十大经典排序算法

时间、空间复杂度比较

排序算法 平均时间复杂度 最差时间复杂度 空间复杂度 数据对象稳定性
冒泡排序 O(n2) O(n2) O(1) 稳定
选择排序 O(n2) O(n2) O(1) 数组不稳定、链表稳定
插入排序 O(n2) O(n2) O(1) 稳定
快速排序 O(n*log2n) O(n2) O(log2n) 不稳定
堆排序 O(n*log2n) O(n*log2n) O(1) 不稳定
归并排序 O(n*log2n) O(n*log2n) O(n) 稳定
希尔排序 O(n*log2n) O(n2) O(1) 不稳定
计数排序 O(n+m) O(n+m) O(n+m) 稳定
桶排序 O(n) O(n) O(m) 稳定
基数排序 O(k*n) O(n2)
稳定

冒泡排序

算法思想：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

排序算法 - 图1
动图演示

代码：

  1. void bubbleSort(int a[], int n)
  2. {
  3.   for(int i =0 ; i< n-1; ++i)
  4.   {
  5.     for(int j = 0; j < n-i-1; ++j)
  6.     {
  7.       if(a[j] > a[j+1])
  8.       {
  9.         int tmp = a[j] ;  //交换
  10.         a[j] = a[j+1] ;
  11.         a[j+1] = tmp;
  12.       }
  13.     }
  14.   }
  15. }

选择排序(近似比冒泡快一倍)

算法思想：

  1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
  2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
  3. 以此类推，直到所有元素均排序完毕

排序算法 - 图2
选择排序动图演示

代码：

  1. function selectionSort(arr) {
  2.     var len = arr.length;
  3.     var minIndex, temp;
  4.     for (var i = 0; i < len - 1; i++) {
  5.         minIndex = i;
  6.         for (var j = i + 1; j < len; j++) {
  7.             if (arr[j] < arr[minIndex]) {     // 寻找最小的数
  8.                 minIndex = j;                 // 将最小数的索引保存
  9.             }
  10.         }
  11.         temp = arr[i];
  12.         arr[i] = arr[minIndex];
  13.         arr[minIndex] = temp;
  14.     }
  15.     return arr;
  16. }
  1. import java.util.Arrays;
  3. public class Sort {
  5.   // 选择排序
  6.   public static void selectSort(int[] array) {
  7.     // 遍历N次，每次选择数组剩余元素中最大的元素
  8.     for (int i = 0; i < array.length; i++) {
  9.       // 暂时把第一个元素当做最大元素，并且记录最大元素的索引
  10.       int maxIndex = 0;
  11.       int max = array[0];
  12.       // 注意 j 从 索引1 开始，到 array.length - i 截止
  13.       for (int j = 1; j < array.length - i; j++) {
  14.         // 如果元素大于当前最大值，则替换 max，maxIndex
  15.         if (array[j] > max) {
  16.           max = array[j];
  17.           maxIndex = j;
  18.         }
  19.       }
  21.       // 交换最大值元素 和 数组末尾元素
  22.       int temp = array[maxIndex];
  23.       array[maxIndex] = array[array.length - i - 1];
  24.       array[array.length - i - 1] = temp;
  25.     }
  26.   }
  27.   public static void main(String[] args) {
  28.     int[] array = {9, 2, 4, 7, 5, 3};
  29.     // Arrays.toString 可以方便打印数组内容
  30.     System.out.println(Arrays.toString(array));
  31.     selectSort(array);
  32.     System.out.println(Arrays.toString(array));
  33.   }
  34. }

插入排序

算法思想：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

排序算法 - 图3
插入排序动图演示

代码：

  1. void print(int a[], int n ,int i){
  2.   cout<<i <<":";
  3.   for(int j= 0; j<8; j++){
  4.     cout<<a[j] <<" ";
  5.   }
  6.   cout<<endl;
  7. }
  8. void InsertSort(int a[], int n)
  9. {
  10.   for(int i= 1; i<n; i++){
  11.     if(a[i] < a[i-1]){   //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
  12.       int j= i-1;
  13.       int x = a[i];     //复制为哨兵，即存储待排序元素
  14.       a[i] = a[i-1];           //先后移一个元素
  15.       while(x < a[j]){   //查找在有序表的插入位置
  16.         a[j+1] = a[j];
  17.         j--;     //元素后移
  18.       }
  19.       a[j+1] = x;     //插入到正确位置
  20.     }
  21.     print(a,n,i);      //打印每趟排序的结果
  22.   }
  23. }
  24. int main(){
  25.   int a[15] = {2，3,4,5,15，19，16，27，36，38，44，46，47，48，50};
  26.   InsertSort(a,15);
  27.   print(a,15,15);
  28. }
  1. import java.util.Arrays;
  3. public class Sort {
  5.   // 插入排序
  6.   public static void insertSort(int[] array) {
  7.    for (int i=0;i<array.length-1;i++ ){
  8.      int temp = array[i+1];
  9.      for (int j =i;j>=0 ;j-- ){
  10.        if (array[j]>temp){
  11.          int re = array[j];
  12.          array[j] = temp;
  13.          array[j+1] = re;
  14.        } 
  15.      } 
  16.    } 
  17.   }
  20.   public static void main(String[] args) {
  21.     int[] array = {9, 2, 4, 7, 5, 3};
  22.     // Arrays.toString 可以方便打印数组内容
  23.     System.out.println(Arrays.toString(array));
  24.     insertSort(array);
  25.     System.out.println(Arrays.toString(array));
  26.   }
  27. }

插入排序进阶——二分插入排序

插入排序核心逻辑是查找应该插入的临时元素的位置，类似在一个有序的数组中查询，找到元素应该插入的位置。
排序算法 - 图4
对于有序列表，循环遍历不是最优解，更好的办法是二分查找。

二分插入法

  1. // 查找应该插入的索引位置
  2. public static int searchIndex(int[] array, int left, int right, int aim) {
  3.     // 循环查找节点位置
  4.     while (left < right) {
  5.         int middle = (left + right) / 2;
  6.         int value = array[middle];
  7.         if (value < aim) {
  8.             left = middle + 1;
  9.         } else {
  10.             right = middle - 1;
  11.         }
  12.     }
  13.     // #1. 如果最终元素仍然大于目标元素，则将索引位置往左边移动一个
  14.     if(array[left] > aim){
  15.         return left -1;
  16.     }
  17.     // 否则就是当前位置
  18.     return left;
  19. }

排序算法 - 图5

  1. // 插入排序
  2. public static void insertSort(int[] array) {
  3.     // 从倒数第二位开始，遍历到底0位，遍历 N-1 次
  4.     for (int i = array.length - 2; i >= 0; i--) {
  5.         // 存储当前抽离的元素
  6.         int temp = array[i];
  7.         int index = searchIndex(array, i + 1, array.length - 1, temp);
  9.         // #1. 根据插入的索引位置，进行数组的移动和插入
  10.         int j = i + 1;
  11.         while (j <= index) {
  12.             array[j - 1] = array[j];
  13.             j++;
  14.         }
  15.         array[j - 1] = temp;
  16.     }
  17. }

快速排序

算法思想：

  1. 选取第一个数为基准
  2. 将比基准小的数交换到前面，比基准大的数交换到后面
  3. 对左右区间重复第二步，直到各区间只有一个数

排序算法 - 图6
快速排序动图演示

代码：

  1. void QuickSort(vector<int>& v, int low, int high) {
  2.     if (low >= high)        // 结束标志
  3.         return;
  4.     int first = low;        // 低位下标
  5.     int last = high;        // 高位下标
  6.     int key = v[first];        // 设第一个为基准
  7.     while (first < last)
  8.     {
  9.         // 将比第一个小的移到前面
  10.         while (first < last && v[last] >= key)
  11.             last--;
  12.         if (first < last)
  13.             v[first++] = v[last];
  14.         // 将比第一个大的移到后面
  15.         while (first < last && v[first] <= key)
  16.             first++;
  17.         if (first < last)
  18.             v[last--] = v[first];
  19.     }
  20.     //
  21.     v[first] = key;
  22.     // 前半递归
  23.     QuickSort(v, low, first - 1);
  24.     // 后半递归
  25.     QuickSort(v, first + 1, high);
  26. }

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
算法思想：

  1. 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
  2. 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
  3. 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

排序算法 - 图7

代码：

  1. #include <iostream>
  2. #include <algorithm>
  3. using namespace std;
  4. // 堆排序：（最大堆，有序区）。从堆顶把根卸出来放在有序区之前，再恢复堆。
  5. void max_heapify(int arr[], int start, int end) {
  6.     //建立父节点指标和子节点指标
  7.     int dad = start;
  8.     int son = dad * 2 + 1;
  9.     while (son <= end) { //若子节点在范围内才做比较
  10.         if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点指标，选择最大的
  11.             son++;
  12.         if (arr[dad] > arr[son]) //如果父节点大于子节点代表调整完成，直接跳出函数
  13.             return;
  14.         else { //否则交换父子內容再继续子节点与孙节点比較
  15.             swap(arr[dad], arr[son]);
  16.             dad = son;
  17.             son = dad * 2 + 1;
  18.         }
  19.     }
  20. }
  21. void heap_sort(int arr[], int len) {
  22.     //初始化，i从最后一个父节点开始调整
  23.     for (int i = len / 2 - 1; i >= 0; i--)
  24.         max_heapify(arr, i, len - 1);
  25.     //先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完成
  26.     for (int i = len - 1; i > 0; i--) {
  27.         swap(arr[0], arr[i]);
  28.         max_heapify(arr, 0, i - 1);
  29.     }
  30. }
  31. int main() {
  32.     int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
  33.     int len = (int) sizeof(arr) / sizeof(*arr);
  34.     heap_sort(arr, len);
  35.     for (int i = 0; i < len; i++)
  36.         cout << arr[i] << ' ';
  37.     cout << endl;
  38.     return 0;
  39. }

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
算法思想：1.把长度为n的输入序列分成两个长度为n/2的子序列；2. 对这两个子序列分别采用归并排序；3. 将两个排序好的子序列合并成一个最终的排序序列。
排序算法 - 图8
归并排序动图演示

代码：

  1. void print(int a[], int n){
  2.   for(int j= 0; j<n; j++){
  3.     cout<<a[j] <<"  ";
  4.   }
  5.   cout<<endl;
  6. }
  7. //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
  8. void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
  9. {
  10.   int j,k;
  11.   for(j=m+1,k=i; i<=m && j <=n ; ++k){
  12.     if(r[j] < r[i]) rf[k] = r[j++];
  13.     else rf[k] = r[i++];
  14.   }
  15.   while(i <= m)  rf[k++] = r[i++];
  16.   while(j <= n)  rf[k++] = r[j++];
  17.   print(rf,n+1);
  18. }
  19. void MergeSort(ElemType *r, ElemType *rf, int lenght)
  20. {
  21.   int len = 1;
  22.   ElemType *q = r ;
  23.   ElemType *tmp ;
  24.   while(len < lenght) {
  25.     int s = len;
  26.     len = 2 * s ;
  27.     int i = 0;
  28.     while(i+ len <lenght){
  29.       Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并
  30.       i = i+ len;
  31.     }
  32.     if(i + s < lenght){
  33.       Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并
  34.     }
  35.     tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf
  36.   }
  37. }
  38. int main(){
  39.   int a[10] = {2，3,4，5,15,19,26,27,36,38,44,46,47,48,50};
  40.   int b[10];
  41.   MergeSort(a, b, 15);
  42.   print(b,15);
  43.   cout<<"结果：";
  44.   print(a,10);
  45. }

希尔排序

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序.
算法思想：

  1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  2. 按增量序列个数k，对序列进行k 趟排序；
  3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

排序算法 - 图9
希尔排序动图演示

代码：

  1. void shell_sort(T array[], int length) {
  2.     int h = 1;
  3.     while (h < length / 3) {
  4.         h = 3 * h + 1;
  5.     }
  6.     while (h >= 1) {
  7.         for (int i = h; i < length; i++) {
  8.             for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
  9.                 std::swap(array[j], array[j - h]);
  10.             }
  11.         }
  12.         h = h / 3;
  13.     }
  14. }

计数排序

计数排序统计小于等于该元素值的元素的个数i，于是该元素就放在目标数组的索引i位（i≥0）。

  • 计数排序基于一个假设，待排序数列的所有数均为整数，且出现在（0，k）的区间之内。
  • 如果 k（待排数组的最大值） 过大则会引起较大的空间复杂度，一般是用来排序 0 到 100 之间的数字的最好的算法，但是它不适合按字母顺序排序人名。
  • 计数排序不是比较排序，排序的速度快于任何比较排序算法。

算法思想：

  1. 找出待排序的数组中最大和最小的元素；
  2. 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
  3. 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）；
  4. 向填充目标数组：将每个元素 i 放在新数组的第 C[i] 项，每放一个元素就将 C[i] 减去 1；

排序算法 - 图10
计数排序动图演示

代码：

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. // 计数排序
  6. void CountSort(vector<int>& vecRaw, vector<int>& vecObj)
  7. {
  8.     // 确保待排序容器非空
  9.     if (vecRaw.size() == 0)
  10.         return;
  11.     // 使用 vecRaw 的最大值 + 1 作为计数容器 countVec 的大小
  12.     int vecCountLength = (*max_element(begin(vecRaw), end(vecRaw))) + 1;
  13.     vector<int> vecCount(vecCountLength, 0);
  14.     // 统计每个键值出现的次数
  15.     for (int i = 0; i < vecRaw.size(); i++)
  16.         vecCount[vecRaw[i]]++;
  18.     // 后面的键值出现的位置为前面所有键值出现的次数之和
  19.     for (int i = 1; i < vecCountLength; i++)
  20.         vecCount[i] += vecCount[i - 1];
  21.     // 将键值放到目标位置
  22.     for (int i = vecRaw.size(); i > 0; i--)    // 此处逆序是为了保持相同键值的稳定性
  23.         vecObj[--vecCount[vecRaw[i - 1]]] = vecRaw[i - 1];
  24. }
  25. int main()
  26. {
  27.     vector<int> vecRaw = { 0,5,7,9,6,3,4,5,2,8,6,9,2,1 };
  28.     vector<int> vecObj(vecRaw.size(), 0);
  29.     CountSort(vecRaw, vecObj);
  30.     for (int i = 0; i < vecObj.size(); ++i)
  31.         cout << vecObj[i] << "  ";
  32.     cout << endl;
  33.     return 0;
  34. }

桶排序

将值为i的元素放入i号桶，最后依次把桶里的元素倒出来。
算法思想：

  1. 设置一个定量的数组当作空桶子。
  2. 寻访序列，并且把项目一个一个放到对应的桶子去。
  3. 对每个不是空的桶子进行排序。
  4. 从不是空的桶子里把项目再放回原来的序列中。

排序算法 - 图11
桶排序动图演示

代码：

  1. function bucketSort(arr, bucketSize) {
  2.     if (arr.length === 0) {
  3.       return arr;
  4.     }
  6.     var i;
  7.     var minValue = arr[0];
  8.     var maxValue = arr[0];
  9.     for (i = 1; i < arr.length; i++) {
  10.       if (arr[i] < minValue) {
  11.           minValue = arr[i];                // 输入数据的最小值
  12.       } else if (arr[i] > maxValue) {
  13.           maxValue = arr[i];                // 输入数据的最大值
  14.       }
  15.     }
  17.     // 桶的初始化
  18.     var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5
  19.     bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
  20.     var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  21.     var buckets = new Array(bucketCount);
  22.     for (i = 0; i < buckets.length; i++) {
  23.         buckets[i] = [];
  24.     }
  26.     // 利用映射函数将数据分配到各个桶中
  27.     for (i = 0; i < arr.length; i++) {
  28.         buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
  29.     }
  31.     arr.length = 0;
  32.     for (i = 0; i < buckets.length; i++) {
  33.         insertionSort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序
  34.         for (var j = 0; j < buckets[i].length; j++) {
  35.             arr.push(buckets[i][j]);
  36.         }
  37.     }
  39.     return arr;
  40. }

基数排序

一种多关键字的排序算法，可用桶排序实现。
算法思想：

  1. 取得数组中的最大数，并取得位数；
  2. arr为原始数组，从最低位开始取每个位组成radix数组；
  3. 对radix进行计数排序（利用计数排序适用于小范围数的特点）

排序算法 - 图12
基数排序动图演示

代码：

  1. int maxbit(int data[], int n) //辅助函数，求数据的最大位数
  2. {
  3.     int maxData = data[0];        ///< 最大数
  4.     /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
  5.     for (int i = 1; i < n; ++i)
  6.     {
  7.         if (maxData < data[i])
  8.             maxData = data[i];
  9.     }
  10.     int d = 1;
  11.     int p = 10;
  12.     while (maxData >= p)
  13.     {
  14.         //p *= 10; // Maybe overflow
  15.         maxData /= 10;
  16.         ++d;
  17.     }
  18.     return d;
  19. /*    int d = 1; //保存最大的位数
  20.     int p = 10;
  21.     for(int i = 0; i < n; ++i)
  22.     {
  23.         while(data[i] >= p)
  24.         {
  25.             p *= 10;
  26.             ++d;
  27.         }
  28.     }
  29.     return d;*/
  30. }
  31. void radixsort(int data[], int n) //基数排序
  32. {
  33.     int d = maxbit(data, n);
  34.     int *tmp = new int[n];
  35.     int *count = new int[10]; //计数器
  36.     int i, j, k;
  37.     int radix = 1;
  38.     for(i = 1; i <= d; i++) //进行d次排序
  39.     {
  40.         for(j = 0; j < 10; j++)
  41.             count[j] = 0; //每次分配前清空计数器
  42.         for(j = 0; j < n; j++)
  43.         {
  44.             k = (data[j] / radix) % 10; //统计每个桶中的记录数
  45.             count[k]++;
  46.         }
  47.         for(j = 1; j < 10; j++)
  48.             count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
  49.         for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
  50.         {
  51.             k = (data[j] / radix) % 10;
  52.             tmp[count[k] - 1] = data[j];
  53.             count[k]--;
  54.         }
  55.         for(j = 0; j < n; j++) //将临时数组的内容复制到data中
  56.             data[j] = tmp[j];
  57.         radix = radix * 10;
  58.     }
  59.     delete []tmp;
  60.     delete []count;
  61. }
  62. © 2020 GitHub, Inc.

参考资料

  1. https://www.cnblogs.com/onepixel/p/7674659.html(部分动图来源)
  2. 电子工程专辑
  3. 菜鸟教程