• 十大排序算法比较

    前言

    在竞赛中，可以使用 C++ STL 的 sort 函数来直接进行排序（小学阶段足够了），但作为最基本的算法问题之一，各种排序算法中包含了许多二分、分治等重要的算法思想，也是掌握很多其他算法的重要基础。因此，如果想在算法上更加深入地往下学习，那么几种非常重要的排序算法，比如快速排序、归并排序、计数排序等，还是要能够同时掌握其算法思想和代码实现的。下面给出各种经典排序算法的比较：

    0、排序算法概述

    0.1 算法分类

    十种常见排序算法可以分为两大类：

    • 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(n\log n)O(nlogn) ，因此也称为非线性时间比较类排序。
    • 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

    正在上传…重新上传取消

    0.2 算法复杂度

    正在上传…重新上传取消

    0.3 相关概念

    • 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
    • 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
    • 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
    • 空间复杂度：是指算法在计算机

    内执行时所需存储空间的度量，它也是数据规模n的函数。

    1、冒泡排序（Bubble Sort）

    冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。

    1.1 算法描述

    • 比较相邻的元素。如果第一个比第二个大，就交换他们两个。

    • 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

    • 针对所有的元素重复以上的步骤，除了最后一个。

    • 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

    1.2 动图演示

    转存失败重新上传取消

    1.3 什么时候最快

    当输入的数据已经是正序时（都已经是正序了，我还要你冒泡排序有何用啊）。

    1.4 什么时候最慢

    当输入的数据是反序时（写一个 for 循环反序输出数据不就行了，干嘛要用你冒泡排序呢，我是闲的吗）。

    1.5 代码实现

    1. // 冒泡排序 
    2. void bubble_sort(int a[],int n) {
    3.     for(int i=0; i
    4.     {
    5.         for(int j=0; j
    6.         {
    7.             if(a[j]>a[j+1])
    8.                 swap(a[j], a[j+1]);  //交换数据
    9.         }
    10.     }
    11. }
    12. /*
    13. 语法说明：
    14.     1、数组作为参数传递给函数，传递的其实是数组的地址指针，通常还需要再传递一个参数来表示数组的大小。这里也可以使用 `int* a`，和使用 `int a[]` 没有区别，两种方法都可以实现数组的传递，后面不再做说明；
    15.     2、 size_t类型：一种无符号(unsigned)的整型数，并且是平台无关的，表示0-MAXINT的范围，常用在数组的下标中，因为一般来说在进行下标访问时，下标都是正的。竞赛中，为了方便，常使用 int 来访问数组下标，但要注意不能越界。
    16. */

    Copy

    2、选择排序（Selection Sort）

    选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

    注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

    2.1 算法描述

    n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

    • 初始状态：无序区为R[1..n]，有序区为空；
    • 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
    • n-1趟结束，数组有序化了。

    2.2 动图演示

    正在上传…重新上传取消　　

    2.3 代码实现

    1. //选择排序
    2. void select_sort(int a[],int n){
    3.     int k;
    4.     for(int i=0;i-1;i++)
    5.     {
    6.         temp=i;      //利用一个中间变量 k 来记录需要交换元素的位置
    7.         for(int j=i+1;j
    8.         {
    9.             if(a[k]>a[j])   //选出待排数据中的最小值
    10.                 k=j;  
    11.         }
    12.         swap(a[i], a[k]); //交换函数
    13.     }
    14. }

    Copy

    正常在使用选择排序时，也可以跳过找最小（大）元素的过程，在内层循环每发现后一个元素比当前元素小（大）时，就交换，这样代码更简洁，时间复杂度不变，代码如下：

    1. //选择排序
    2. void selection_sort(int a[],int n)
    3. {
    4.     for(int i=0; i-1; ++i)
    5.     {
    6.         for(int j=i+1; j
    7.             if(h[j] < h[i])
    8.                 swap(h[i], h[j]);
    9.     }
    10. }

    Copy

    2.4 算法分析

    表现最稳定的排序算法之一，因为无论什么数据进去都是 O(n^2)O(n2) 的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。选择排序可能也是平时排序一般人想到的最多的排序方法了吧。

    3、插入排序（Insertion Sort）

    插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

    3.1 算法描述

    一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

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

    3.2 动图演示

    转存失败重新上传取消

    3.2 代码实现

    1. //插入排序
    2. void insert_sort(int a[],int n) {
    3.     int i,j;
    4.     //外层循环标识并决定待比较的数值
    5.     for(i=1; i//循环从第2个元素开始
    6.         if(a[i]-1]) {
    7.             int temp=a[i];
    8.             //待比较数值确定其最终位置
    9.             for(j=i-1; j>=0 && a[j]>temp; j--) {
    10.                 a[j+1]=a[j];
    11.             }
    12.             a[j+1]=temp; //此处就是a[j+1]=temp;
    13.         }
    14.     }
    15. }

    Copy

    3.4 算法分析

    插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1)O(1) 的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

    4、希尔排序（Shell Sort）

    1959年Shell发明，第一个突破 O(n^2)O(n2) 的排序算法，是简单插入排序的改进版，但希尔排序是非稳定排序算法。。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

    希尔排序是基于插入排序的以下两点性质而提出改进方法的：

    • 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
    • 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

    希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

    4.1 算法描述

    先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

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

    4.2 动图演示

    正在上传…重新上传取消

    4.3 代码实现

    1. //希尔排序
    2. void shell_sort(int arr[], int n) {
    3.     int i, j, gap;
    4.     for (gap = n / 2; gap > 0; gap /= 2) {
    5.         for (i = 0; i < gap; i++) {
    6.             for (j = i + gap; j < n; j += gap) {
    7.                 for (int k = j; k > i && arr[k] < arr[k-gap]; k -= gap) {
    8.                     swap(arr[k-gap], arr[k]);
    9.                 }
    10.             }
    11.         }
    12.     }
    13. }

    Copy

    4.4 算法分析

    希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。　

    5、归并排序（Merge Sort）

    归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

    5.1 算法描述

    • 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
    • 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
    • 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
    • 重复步骤 3 直到某一指针达到序列尾；
    • 将另一序列剩下的所有元素直接复制到合并序列尾。

    5.2 动图演示

    正在上传…重新上传取消

    5.3 代码实现

    1. const int N = 1e6+5;
    2. int n, a[N], tmp[N];
    3.  
    4. void merge_sort(int q[], int l, int r)
    5. {
    6.     if (l >= r) return;
    7.  
    8.     // 分（递归）
    9.     int mid = l + r >> 1;         // 将数组平均分成两个部分
    10.     merge_sort(q, l, mid);        // 对左半部分进行分治排序
    11.     merge_sort(q, mid + 1, r);    // 对右半部分进行分治排序
    12.     
    13.     // 治（合并）
    14.     int k = 0, i = l, j = mid + 1;
    15.     while (i <= mid && j <= r)
    16.         if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
    17.         else tmp[k ++ ] = q[j ++ ];
    18.  
    19.     while (i <= mid) tmp[k ++ ] = q[i ++ ];   // 可能的左半部分比右半部分多的
    20.     while (j <= r) tmp[k ++ ] = q[j ++ ];     // 可能的右半部分比左半部分多的
    21.  
    22.     for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
    23. }

    Copy

    5.4 算法分析

    归并排序是一种稳定的排序方法。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(n\log n)O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

    归并排序体现出了一种典型的算法思想——分治，并且采用的是二分。分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

    转存失败重新上传取消

    6、快速排序（Quick Sort）

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(n\log n)O(nlogn) 次比较。在最坏状况下则需要 Ο(n^2)O(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(n\log n)O(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。

    快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。

    快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

    快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了。虽然 Worst Case 的时间复杂度达到了 O(n^2)O(n2) ，但是人家就是优秀，在大多数情况下都比平均时间复杂度为 O(n \log n)O(nlogn) 的排序算法表现要更好，因为它隐含的常数因子很小，比复杂度稳定等于 O(n \log n)O(nlogn)的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

    6.1 算法描述

    快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

    • 从数列中挑出一个元素，称为 “基准”（pivot）；
    • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
    • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

    6.2 动图演示

    转存失败重新上传取消

    6.3 代码实现

    1. void quick_sort(int q[], int l, int r)
    2. {
    3.     if (l >= r) return;
    4.  
    5.     int i = l - 1, j = r + 1, x = q[l + r >> 1];
    6.     while (i < j)
    7.     {
    8.         do i ++ ; while (q[i] < x);
    9.         do j -- ; while (q[j] > x);
    10.         if (i < j) swap(q[i], q[j]);
    11.     }
    12.     quick_sort(q, l, j), quick_sort(q, j + 1, r);
    13. }

    Copy

    7、堆排序（Heap Sort）

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

    7.1 算法描述

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

    7.2 图演示

    转存失败重新上传取消

    7.3 代码实现

    1. void Max_Heapify(int* A, int i,int size){
    2.         int l = 2*i;
    3.         int r = 2*i + 1;
    4.         int large = i;
    5.         if(l <= size && A[l] > A[i])
    6.                 large = l;
    7.         else
    8.                 large = i;
    9.         if(r <= size && A[r] > A[large])
    10.                 large = r;
    11.         if(large != i){
    12.         int t = A[large];
    13.         A[large] = A[i];
    14.         A[i] = t;
    15.         Max_Heapify(A, large, size);
    16.         }
    17. }
    18.  
    19. void Build_Max_Heap(int* A, int size){
    20.         for(int i=size/2;i>0;i--)
    21.                 Max_Heapify(A,i,size);
    22. }
    23.   
    24. void Heap_Sort(int* A, int len){
    25.         Build_Max_Heap(A, len);
    26.         while(len-1){
    27.                 int t = A[1];
    28.                 A[1] = A[i];
    29.                 A[i] = t;
    30.                 len--;
    31.                 Max_Heapify(A,1,len);
    32.         }
    33. }

    Copy

    8、计数排序（Counting Sort）

    计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

    8.1 算法描述

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

    8.2 动图演示

    转存失败重新上传取消

    8.3 代码实现

    1. void count_sort(int* a, int n)
    2. {
    3.  
    4.     //确定数列最大值
    5.     int max = a[0];
    6.     int min = a[0];
    7.     for (int i = 1; i < n; ++i)
    8.     {
    9.         if (a[i] > max)
    10.             max = a[i];
    11.         if (a[i] < min)
    12.             min = a[i];
    13.     }
    14.     int d = max - min;
    15.     // 确定统计数组长度并进行初始化
    16.     int* counta = new int[d + 1];
    17.     memset(counta, 0, sizeof(int) * (d+1));
    18.     // 遍历数组，统计每个数出现的次数
    19.     for (int i = 0; i < n; ++i)
    20.             ++counta[a[i] - min];
    21.     int len = 0;
    22.     for(int i = 0;  i <= d; i++)
    23.     {
    24.         while(counta[i]--)
    25.             a[len++] = min+i;
    26.     }
    27.     delete counta;
    28. }

    Copy

    8.4 算法分析

    计数排序是一个稳定的排序算法。当输入的元素是 n 个 0到 k 之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。当k不是很大并且序列比较集中时，计数排序是一个很有效的排序算法。

    但是计数排序的局限性也很明显，当数组最大和最小值差距过大时，并不适合用计数排序。会造成空间浪费，时间复杂度也会随之升高。当数组元素不是整数时，如小数， 也不适合用计数排序。

    9、桶排序（Bucket Sort）

    桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

    1. 在额外空间充足的情况下，尽量增大桶的数量
    2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

    同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

    当输入的数据可以均匀的分配到每一个桶中时，桶排序运行最快，时间复杂度为 O(n)O(n) 。当输入的数据被分配到了同一个桶中，桶排序运行最快，时间复杂度为取决于桶中元素的排序算法的时间复杂度。

    9.1 算法描述

    • 设置一个定量的数组当作空桶；
    • 遍历输入数据，并且把数据一个一个放到对应的桶里去；
    • 对每个不是空的桶进行排序；
    • 从不是空的桶里把排好序的数据拼接起来。

    9.2 动图演示

    正在上传…重新上传取消

    9.3 代码实现

    1. #include
    2. #include
    3. #include
    4. using namespace std;
    5. const int BUCKET_NUM = 10;
    6.  
    7. struct ListNode{
    8.     explicit ListNode(int i=0):mData(i),mNext(NULL){}
    9.     ListNode* mNext;
    10.     int mData;
    11. };
    12.  
    13. ListNode* insert(ListNode* head,int val){
    14.     ListNode dummyNode;
    15.     ListNode *newNode = new ListNode(val);
    16.     ListNode *pre,*curr;
    17.     dummyNode.mNext = head;
    18.     pre = &dummyNode;
    19.     curr = head;
    20.     while(NULL!=curr && curr->mData<=val){
    21.             pre = curr;
    22.             curr = curr->mNext;
    23.     }
    24.     newNode->mNext = curr;
    25.     pre->mNext = newNode;
    26.     return dummyNode.mNext;
    27. }
    28.  
    29.  
    30. ListNode* Merge(ListNode *head1,ListNode *head2){
    31.     ListNode dummyNode;
    32.     ListNode *dummy = &dummyNode;
    33.     while(NULL!=head1 && NULL!=head2){
    34.             if(head1->mData <= head2->mData){
    35.                     dummy->mNext = head1;
    36.                     head1 = head1->mNext;
    37.             }else{
    38.                     dummy->mNext = head2;
    39.                     head2 = head2->mNext;
    40.             }
    41.             dummy = dummy->mNext;
    42.     }
    43.     if(NULL!=head1) dummy->mNext = head1;
    44.     if(NULL!=head2) dummy->mNext = head2;
    45.  
    46.     return dummyNode.mNext;
    47. }
    48.  
    49. void BucketSort(int n,int arr[]){
    50.     vector buckets(BUCKET_NUM,(ListNode*)(0));
    51.     for(int i=0;i
    52.             int index = arr[i]/BUCKET_NUM;
    53.             ListNode *head = buckets.at(index);
    54.             buckets.at(index) = insert(head,arr[i]);
    55.     }
    56.     ListNode *head = buckets.at(0);
    57.     for(int i=1;i
    58.             head = Merge(head,buckets.at(i));
    59.     }
    60.     for(int i=0;i
    61.             arr[i] = head->mData;
    62.             head = head->mNext;
    63.     }
    64. }

    Copy

    9.4 算法分析

    桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。

    10、基数排序（Radix Sort）

    基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

    其基本思想是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

    基数排序 vs 计数排序 vs 桶排序

    这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

    • 基数排序：根据键值的每位数字来分配桶；
    • 计数排序：每个桶只存储单一键值；
    • 桶排序：每个桶存储一定范围的数值；

    10.1 算法描述

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

    10.2 动图演示

    正在上传…重新上传取消

    10.3 代码实现

    1. public class RadixSort {
    2.     // 获取x这个数的d位数上的数字
    3.     // 比如获取123的1位数，结果返回3
    4.     public int getDigit(int x, int d) {
    5.         int a[] = {1, 1, 10, 100}; // 本实例中的最大数是百位数，所以只要到100就可以了
    6.         return ((x / a[d]) % 10);
    7.     }
    8.  
    9.   public void radixSort(int[] list, int begin, int end, int digit) {
    10.       final int radix = 10; // 基数
    11.       int i = 0, j = 0;
    12.       int[] count = new int[radix]; // 存放各个桶的数据统计个数
    13.       int[] bucket = new int[end - begin + 1];
    14.       // 按照从低位到高位的顺序执行排序过程
    15.       for (int d = 1; d <= digit; d++) {
    16.           // 置空各个桶的数据统计
    17.           for (i = 0; i < radix; i++) {
    18.               count[i] = 0;
    19.           }
    20.           // 统计各个桶将要装入的数据个数
    21.           for (i = begin; i <= end; i++) {
    22.               j = getDigit(list[i], d);
    23.               count[j]++;
    24.           }
    25.           // count[i]表示第i个桶的右边界索引
    26.           for (i = 1; i < radix; i++) {
    27.               count[i] = count[i] + count[i - 1];
    28.           }
    29.           // 将数据依次装入桶中
    30.           // 这里要从右向左扫描，保证排序稳定性
    31.           for (i = end; i >= begin; i--) {
    32.               j = getDigit(list[i], d);
    33.               // 求出关键码的第k位的数字， 例如：576的第3位是5
    34.               bucket[count[j] - 1] = list[i];
    35.               // 放入对应的桶中，count[j]-1是第j个桶的右边界索引
    36.               count[j]--; // 对应桶的装入数据索引减一
    37.           }
    38.           // 将已分配好的桶中数据再倒出来，此时已是对应当前位数有序的表
    39.           for (i = begin, j = 0; i <= end; i++, j++) {
    40.               list[i] = bucket[j];
    41.           }
    42.       }
    43.   }
    44.  
    45.   public int[] sort(int[] list) {
    46.       radixSort(list, 0, list.length - 1, 3);
    47.       return list;
    48.   }
    49.  
    50.   // 打印完整序列
    51.   public void printAll(int[] list) {
    52.       for (int value : list) {
    53.           System.out.print(value + "\t");
    54.       }
    55.       System.out.println();
    56.   }
    57.  
    58.   public static void main(String[] args) {
    59.       int[] array = {50, 123, 543, 187, 49, 30, 0, 2, 11, 100};
    60.       RadixSort radix = new RadixSort();
    61.       System.out.print("排序前:\t\t");
    62.       radix.printAll(array);
    63.       radix.sort(array);
    64.       System.out.print("排序后:\t\t");
    65.       radix.printAll(array);
    66.   }
    67. }

    Copy

    10.4 算法分析

    基数排序基于分别排序，分别收集，所以是稳定的。但基数排序的性能比桶排序要略差，每一次关键字的桶分配都需要O(n)的时间复杂度，而且分配之后得到新的关键字序列又需要O(n)的时间复杂度。假如待排数据可以分为d个关键字，则基数排序的时间复杂度将是O(d*2n) ，当然d要远远小于n，因此基本上还是线性级别的。

    基数排序的空间复杂度为O(n+k)，其中k为桶的数量。一般来说n>>k，因此额外空间需要大概n个左右。

    参考文献

  • 相关阅读:
    Java数据结构————队列
    LintCode 87: Remove Node in Binary Search Tree BST操作经典题
    【毕业季·进击的技术er】这三年来的风风雨雨，喜怒哀乐，坎坎坷坷，朝朝暮暮……都是那么美好，那么令人难以忘记。
    linux安装MySQL8.0，密码修改权限配置等常规操作详解
    Python中关闭文件很重要
    sed实现修改最后一次匹配
    MySQL分库分表
    Flask 项目结构
    埃及分数 ← IDA*
    协程与任务
  • 原文地址：https://blog.csdn.net/WANGHAOXIN364/article/details/126038723