排序算法时间复杂度、空间复杂度、稳定性比较

曾经终败给现在 2022-04-01 14:59 340阅读 0赞

转自：[https://blog.csdn.net/yushiyi6453/article/details/76407640][https_blog.csdn.net_yushiyi6453_article_details_76407640]

# 排序算法分类 #

![这里写图片描述][SouthEast]

排序大的分类可以分为两种：内排序和外排序。

放在内存的称为内排序，需要使用外存的称为外排序。

# 排序算法的时间复杂度和空间复杂度 #

<table> 
 <tbody> 
 <tr> 
 <td style="border-color:#000000 transparent #000000 #000000;vertical-align:top;width:90px;"> 排序算法 </td> 
 <td style="border-color:#000000 transparent #000000 transparent;vertical-align:top;width:90px;"> 平均时间复杂度 </td> 
 <td style="border-color:#000000 transparent #000000 transparent;vertical-align:top;width:90px;"> 最坏时间复杂度 </td> 
 <td style="border-color:#000000 transparent #000000 transparent;vertical-align:top;width:90px;"> 最好时间复杂度 </td> 
 <td style="border-color:#000000 transparent #000000 transparent;vertical-align:top;width:90px;"> 空间复杂度 </td> 
 <td style="border-color:#000000 #000000 #000000 transparent;vertical-align:top;width:89px;"> 稳定性 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 冒泡排序 </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n²) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n²) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(1) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 稳定 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 直接选择排序 </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n²) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n²) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(1) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 不稳定 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 直接插入排序 </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n²) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n²) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(1) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 稳定 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 快速排序 </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(nlogn) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n²) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(nlogn) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(nlogn) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 不稳定 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 堆排序 </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(nlogn) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(nlogn) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(nlogn) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(1) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 不稳定 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 希尔排序 </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(nlogn) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(ns) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(1) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 不稳定 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 归并排序 </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(nlogn) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(nlogn) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(nlogn) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 稳定 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 计数排序 </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n+k) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n+k) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n+k) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(n+k) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 稳定 </td> 
 </tr> 
 <tr> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 基数排序 </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(N*M)&nbsp; </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(N*M) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(N*M) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> O(M) </td> 
 <td style="border-color:#000000 #000000 #000000 #000000;vertical-align:top;width:89px;"> 稳定 </td> 
 </tr> 
 </tbody> 
</table>

**注**：

1 归并排序可以通过手摇算法将空间复杂度降到O(1)，但是时间复杂度会提高。

2 基数排序时间复杂度为O(N\*M)，其中N为数据个数，M为数据位数。

**辅助记忆**

*  时间复杂度记忆-

1.  冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n²)）（一遍找元素O(n)，一遍找位置O(n)）
2.  快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）

*  稳定性记忆-“快希选堆”（快牺牲稳定性）

1.  排序算法的稳定性：排序前后相同元素的相对位置不变，则称排序算法是稳定的；否则排序算法是不稳定的。

# 原理理解 #

## 1 冒泡排序 ##

### 1.1 过程 ###

冒泡排序从小到大排序：一开始交换的区间为0~N-1，将第1个数和第2个数进行比较，前面大于后面，交换两个数，否则不交换。再比较第2个数和第三个数，前面大于后面，交换两个数否则不交换。依次进行，最大的数会放在数组最后的位置。然后将范围变为0~N-2，数组第二大的数会放在数组倒数第二的位置。依次进行整个交换过程，最后范围只剩一个数时数组即为有序。

### 1.2 动图 ###

![20161009190728886][]

### 1.3 核心代码（函数） ###

//array[]为待排序数组，n为数组长度
 void BubbleSort(int array[], int n)
 {
 int i, j, k;
 for(i=0; i<n-1; i++)
 for(j=0; j<n-1-i; j++)
 {
 if(array[j]>array[j+1])
 {
 k=array[j];
 array[j]=array[j+1];
 array[j+1]=k;
 }
 }
 }

## 2 直接选择排序 ##

### 2.1 过程 ###

选择排序从小到大排序：一开始从0~n-1区间上选择一个最小值，将其放在位置0上，然后在1~n-1范围上选取最小值放在位置1上。重复过程直到剩下最后一个元素，数组即为有序。

### 2.2 动图 ###

![20201009100055434.gif][]

### 2.3 核心代码（函数） ###

//array[]为待排序数组，n为数组长度
 void selectSort(int array[], int n)
 {
 int i, j ,min ,k;
 for( i=0; i<n-1; i++)
 {
 min=i; //每趟排序最小值先等于第一个数，遍历剩下的数
 for( j=i+1; j<n; j++) //从i下一个数开始检查
 {
 if(array[min]>array[j])
 {
 min=j;
 }
 }
 if(min!=i)
 {
 k=array[min];
 array[min]=array[i];
 array[i]=k;
 }
 }
 }

## 3 直接插入排序 ##

### 3.1 过程 ###

插入排序从小到大排序：首先位置1上的数和位置0上的数进行比较，如果位置1上的数大于位置0上的数，将位置0上的数向后移一位，将1插入到0位置，否则不处理。位置k上的数和之前的数依次进行比较，如果位置K上的数更大，将之前的数向后移位，最后将位置k上的数插入不满足条件点，反之不处理。

### 3.2 动图 ###

![20161009190855230][]  
![6f1e495521a1b510130e71c4b4a119ae.png][]

### 3.3 核心代码（函数） ###

//array[]为待排序数组，n为数组长度
 void insertSort(int array[], int n)
 {
 int i,j,temp;
 for( i=1;i<n;i++)
 {
 if(array[i]<array[i-1])
 {
 temp=array[i];
 for( j=i;array[j-1]>temp;j--)
 {
 array[j]=array[j-1];
 }
 array[j]=temp;
 }
 }
 }

## 4 快速排序 ##

###  4.1 过程 ###

快速排序从小到大排序：在数组中随机选一个数（默认数组首个元素），数组中小于等于此数的放在左边部分，大于此数的放在右边部分，这个操作确保了这个数是处于正确位置的，再对左边部分数组和右边部分数组递归调用快速排序，重复这个过程。

###  4.2 动图 ###

![20161009191035090][]   
![cb345b3b3dc2ae27314570d8aa9b1830.png][]

###  4.3 核心代码（函数） ###

void quicksort(int a[], int left, int right) {
 int i, j, t, privotkey;
 if (left > right) //（递归过程先写结束条件）
 return;
 
 privotkey = a[left]; //temp中存的就是基准数（枢轴）
 i = left;
 j = right;
 while (i < j) {
 //顺序很重要，要先从右边开始找（最后交换基准时换过去的数要保证比基准小，因为基准选取数组第一个数）
 while (a[j] >= privotkey && i < j) {
 j--;
 }
 a[i] = a[j];
 //再找左边的
 while (a[i] <= privotkey && i < j) {
 i++;
 }
 a[j] = a[i];
 }
 //最终将基准数归位
 a[i] = privotkey;
 
 quicksort(a, left, i - 1);//继续处理左边的，这里是一个递归的过程
 quicksort(a, i + 1, right);//继续处理右边的 ，这里是一个递归的过程
 }

## 5 堆排序 ##

###  5.1 过程 ###

堆排序从小到大排序：首先将数组元素建成大小为n的大顶堆，堆顶（数组第一个元素）是所有元素中的最大值，将堆顶元素和数组最后一个元素进行交换，再将除了最后一个数的n-1个元素   建立成大顶堆，再将最大元素和数组倒数第二个元素进行交换，重复直至堆大小减为1。

* 注：完全二叉树  
 假设二叉树深度为n，除了第n层外，n-1层节点都有两个孩子，第n层节点连续从左到右。如下图  
 ![这里写图片描述][SouthEast 1]
 * 注：大顶堆  
 大顶堆是具有以下性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值。  
 即，根节点是堆中最大的值，按照层序遍历给节点从1开始编号，则节点之间满足如下关系：  
 ![这里写图片描述][SouthEast 2] (1<=i<=n/2)

###  5.2 动图 ###

![20161009191011299][]   
![20150606133355179][]   
![Center][]

###  5.3 核心代码（函数） ###

![这里写图片描述][SouthEast 3]

void heapSort(int array[], int n)
 {
 int i;
 for (i=n/2;i>0;i--)
 {
 HeapAdjust(array,i,n);//从下向上，从右向左调整
 }
 for( i=n;i>1;i--)
 {
 swap(array, 1, i);
 HeapAdjust(array, 1, i-1);//从上到下，从左向右调整
 }
 }
 void HeapAdjust(int array[], int s, int n )
 {
 int i,temp;
 temp = array[s];
 for(i=2*s;i<=n;i*=2)
 {
 if(i<n&&array[i]<array[i+1])
 {
 i++;
 }
 if(temp>=array[i])
 {
 break;
 }
 array[s]=array[i];
 s=i;
 }
 array[s]=temp;
 }
 void swap(int array[], int i, int j)
 {
 int temp;
 
 temp=array[i];
 array[i]=array[j];
 array[j]=temp;
 }

## 6 希尔排序 ##

###  6.1 过程 ###

希尔排序是插入排序改良的算法，希尔排序步长从大到小调整，第一次循环后面元素逐个和前面元素按间隔步长进行比较并交换，直至步长为1，步长选择是关键。

###  6.2 动图 ###

![这里写图片描述][SouthEast 4]   
![8cdd90954fa4e527190a7a7b48e0dfab.png][]

###  6.3 核心程序（函数） ###

//下面是插入排序
 void InsertSort( int array[], int n)
 {
 int i,j,temp;
 for( i=0;i<n;i++ )
 {
 if(array[i]<array[i-1])
 {
 temp=array[i];
 for( j=i-1;array[j]>temp;j--)
 {
 array[j+1]=array[j];
 }
 array[j+1]=temp;
 }
 }
 }
 //在插入排序基础上修改得到希尔排序
 void SheelSort( int array[], int n)
 {
 int i,j,temp;
 int gap=n; //~~~~~~~~~~~~~~~~~~~~~
 do{
 gap=gap/3+1; //~~~~~~~~~~~~~~~~~~
 for( i=gap;i<n;i++ )
 {
 if(array[i]<array[i-gap])
 {
 temp=array[i];
 for( j=i-gap;array[j]>temp;j-=gap)
 {
 array[j+gap]=array[j];
 }
 array[j+gap]=temp;
 }
 }
 }while(gap>1); //~~~~~~~~~~~~~~~~~~~~~~
 
 }

## 7 归并排序 ##

###  7.1 过程 ###

归并排序从小到大排序：首先让数组中的每一个数单独成为长度为1的区间，然后两两一组有序合并，得到长度为2的有序区间，依次进行，直到合成整个区间。

###  7.2 动图 ###

![20161009190940095][]

###  7.3 核心代码（函数） ###

递归实现

实现归并，并把数据都放在list1里面 
 void merging(int *list1, int list1_size, int *list2, int list2_size)
 {
 int i=0, j=0, k=0, m=0;
 int temp[MAXSIZE];
 
 while(i < list1_size && j < list2_size)
 {
 if(list1[i]<list2[j])
 {
 temp[k++] = list1[i++];
 }
 else
 {
 temp[k++] = list2[j++];
 }
 }
 while(i<list1_size)
 {
 temp[k++] = list1[i++];
 }
 while(j<list2_size)
 {
 temp[k++] = list2[j++];
 }
 
 for(m=0; m < (list1_size+list2_size); m++)
 {
 list1[m]=temp[m];
 }
 }
 //如果有剩下的，那么说明就是它是比前面的数组都大的，直接加入就可以了 
 void mergeSort(int array[], int n)
 {
 if(n>1)
 {
 int *list1 = array;
 int list1_size = n/2;
 int *list2 = array + n/2;
 int list2_size = n-list1_size;
 
 mergeSort(list1, list1_size);
 mergeSort(list2, list2_size);
 
 merging(list1, list1_size, list2, list2_size);
 }
 }
 //归并排序复杂度分析：一趟归并需要将待排序列中的所有记录 
 //扫描一遍，因此耗费时间为O(n),而由完全二叉树的深度可知， 
 //整个归并排序需要进行[log2n],因此，总的时间复杂度为 
 //O(nlogn),而且这是归并排序算法中平均的时间性能 
 //空间复杂度：由于归并过程中需要与原始记录序列同样数量级的 
 //存储空间去存放归并结果及递归深度为log2N的栈空间，因此空间 
 //复杂度为O(n+logN) 
 //也就是说，归并排序是一种比较占内存，但却效率高且稳定的算法

迭代实现

void MergeSort(int k[],int n) 
 { 
 int i,next,left_min,left_max,right_min,right_max; 
 //动态申请一个与原来数组一样大小的空间用来存储
 int *temp = (int *)malloc(n * sizeof(int)); 
 //逐级上升，第一次比较2个，第二次比较4个，第三次比较8个。。。 
 for(i=1; i<n; i*=2) 
 { 
 //每次都从0开始，数组的头元素开始 
 for(left_min=0; left_min<n-i; left_min = right_max) 
 { 
 right_min = left_max = left_min + i; 
 right_max = left_max + i; 
 //右边的下标最大值只能为n 
 if(right_max>n) 
 { 
 right_max = n; 
 } 
 //next是用来标志temp数组下标的，由于每次数据都有返回到K， 
 //故每次开始得重新置零 
 next = 0; 
 //如果左边的数据还没达到分割线且右边的数组没到达分割线，开始循环 
 while(left_min<left_max&&right_min<right_max) 
 { 
 if(k[left_min] < k[right_min]) 
 { 
 temp[next++] = k[left_min++]; 
 } 
 else 
 { 
 temp[next++] = k[right_min++]; 
 } 
 } 
 //上面循环结束的条件有两个，如果是左边的游标尚未到达，那么需要把 
 //数组接回去，可能会有疑问，那如果右边的没到达呢，其实模拟一下就可以 
 //知道，如果右边没到达，那么说明右边的数据比较大，这时也就不用移动位置了 
 
 while(left_min < left_max) 
 { 
 //如果left_min小于left_max，说明现在左边的数据比较大 
 //直接把它们接到数组的min之前就行 
 k[--right_min] = k[--left_max]; 
 } 
 while(next>0) 
 { 
 //把排好序的那部分数组返回该k 
 k[--right_min] = temp[--next]; 
 } 
 } 
 } 
 } 
 //非递归的方法，避免了递归时深度为log2N的栈空间，
 //空间只是用到归并临时申请的跟原来数组一样大小的空间，并且在时间性能上也有一定的提升，
 //因此，使用归并排序是，尽量考虑用非递归的方法。

## 8 桶排序（基数排序和基数排序的思想） ##

###  8.1 过程 ###

桶排序是计数排序的变种，把计数排序中相邻的m个”小桶”放到一个”大桶”中，在分完桶后，对每个桶进行排序（一般用快排），然后合并成最后的结果。

###  8.2 图解 ###

###  8.3 核心程序 ###

#include <stdio.h>
 int main()
 {
 int a[11],i,j,t;
 for(i=0;i<=10;i++)
 a[i]=0; //初始化为0
 
 for(i=1;i<=5;i++) //循环读入5个数
 {
 scanf("%d",&t); //把每一个数读到变量t中
 a[t]++; //进行计数(核心行)
 }
 
 for(i=0;i<=10;i++) //依次判断a[0]~a[10]
 for(j=1;j<=a[i];j++) //出现了几次就打印几次
 printf("%d ",i);
 
 getchar();getchar(); 
 //这里的getchar();用来暂停程序，以便查看程序输出的内容
 //也可以用system("pause");等来代替
 return 0;
 }

## 9 计数排序 ##

###  9.1 过程 ###

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

###  9.2 图解 ###

![这里写图片描述][SouthEast 5]

###  9.3 核心程序（函数） ###

程序1：
 #define NUM_RANGE (100) //预定义数据范围上限，即K的值
 
 void counting_sort(int *ini_arr, int *sorted_arr, int n) //所需空间为 2*n+k
 { 
 int *count_arr = (int *)malloc(sizeof(int) * NUM_RANGE); 
 int i, j, k; 
 
 //初始化统计数组元素为值为零 
 for(k=0; k<NUM_RANGE; k++){ 
 count_arr[k] = 0; 
 } 
 //统计数组中，每个元素出现的次数 
 for(i=0; i<n; i++){ 
 count_arr[ini_arr[i]]++; 
 } 
 
 //统计数组计数，每项存前N项和，这实质为排序过程
 for(k=1; k<NUM_RANGE; k++){ 
 count_arr[k] += count_arr[k-1]; 
 } 
 
 //将计数排序结果转化为数组元素的真实排序结果
 for(j=n-1 ; j>=0; j--){ 
 int elem = ini_arr[j]; //取待排序元素
 int index = count_arr[elem]-1; //待排序元素在有序数组中的序号
 sorted_arr[index] = elem; //将待排序元素存入结果数组中
 count_arr[elem]--; //修正排序结果，其实是针对算得元素的修正
 } 
 free(count_arr); 
 } 
 
 程序2：C++(最大最小压缩桶数)
 public static void countSort(int[] arr) {
 if (arr == null || arr.length < 2) {
 return;
 }
 int min = arr[0];
 int max = arr[0];
 for (int i = 1; i < arr.length; i++) {
 min = Math.min(arr[i], min);
 max = Math.max(arr[i], max);
 }
 int[] countArr = new int[max - min + 1];
 for (int i = 0; i < arr.length; i++) {
 countArr[arr[i] - min]++;
 }
 int index = 0;
 for (int i = 0; i < countArr.length; i++) {
 while (countArr[i]-- > 0) {
 arr[index++] = i + min;
 }
 }

## 10 基数排序 ##

###  10.1 过程 ###

基数排序是基于数据位数的一种排序算法。   
 它有两种算法   
 ①LSD–Least Significant Digit first 从低位（个位）向高位排。   
 ②MSD– Most Significant Digit first 从高位向低位（个位）排。   
 时间复杂度O(N\*最大位数)。   
 空间复杂度O(N)。

###  10.2 图解 ###

![这里写图片描述][SouthEast 6]   
 对a\[n\]按照个位0~9进行桶排序：   
![这里写图片描述][SouthEast 7]   
 对b\[n\]进行累加得到c\[n\]，用于b\[n\]中重复元素计数   
 ！！！b\[n\]中的元素为temp中的位置！！！跳跃的用++补上：   
![这里写图片描述][SouthEast 8]   
 temp数组为排序后的数组，写回a\[n\]。temp为按顺序倒出桶中的数据（联合b\[n\],c\[n\],a\[n\]得到），重复元素按顺序输出：   
![这里写图片描述][SouthEast 9]

###  10.3 核心程序 ###

//基数排序 
 //LSD 先以低位排，再以高位排 
 //MSD 先以高位排，再以低位排 
 void LSDSort(int *a, int n) 
 { 
 assert(a); //判断a是否为空，也可以a为空||n<2返回
 int digit = 0; //最大位数初始化
 for (int i = 0; i < n; ++i) 
 { //求最大位数
 while (a[i] > (pow(10,digit))) //pow函数要包含头文件math.h，pow(10,digit)=10^digit
 { 
 digit++; 
 } 
 } 
 int flag = 1; //位数
 for (int j = 1; j <= digit; ++j) 
 { 
 //建立数组统计每个位出现数据次数（Digit[n]为桶排序b[n]） 
 int Digit[10] = { 0 }; 
 for (int i = 0; i < n; ++i) 
 { 
 Digit[(a[i] / flag)%10]++; //flag=1时为按个位桶排序
 } 
 //建立数组统计起始下标（BeginIndex[n]为个数累加c[n]，用于记录重复元素位置
 //flag=1时，下标代表个位数值，数值代表位置，跳跃代表重复）
 int BeginIndex[10] = { 0 }; 
 for (int i = 1; i < 10; ++i) 
 { 
 //累加个数
 BeginIndex[i] = BeginIndex[i - 1] + Digit[i - 1]; 
 } 
 //建立辅助空间进行排序 
 //下面两条可以用calloc函数实现
 int *tmp = new int[n]; 
 memset(tmp, 0, sizeof(int)*n);//初始化 
 //联合各数组求排序后的位置存在temp中
 for (int i = 0; i < n; ++i) 
 { 
 int index = (a[i] / flag)%10; //桶排序和位置数组中的下标
 //计算temp相应位置对应a[i]中的元素，++为BeginIndex数组数值加1
 //跳跃间隔用++来补，先用再++
 tmp[BeginIndex[index]++] = a[i]; 
 } 
 //将数据重新写回原空间 
 for (int i = 0; i < n; ++i) 
 { 
 a[i] = tmp[i]; 
 } 
 flag = flag * 10; 
 delete[] tmp; 
 } 
 }

推荐一个非常好的算法可视化演示的网站：[https://visualgo.net/zh][https_visualgo.net_zh]

《[快速排序、归并排序、堆排序三种算法性能比较][Link 1]》

> 上文指出三种算法的性能差异：在数据量小的时候快速排序当属第一，堆排序最差，但随着数据的不断增大归并排序的性能会逐步赶上并超过快速排序，性能成为三种算法之首。可能在数据量大到一定数量时，快速排序的堆栈开销比较大，所以在性能上大打折扣，甚至堆排序的性能也能好过它，但总体上来说快速排序表现的还是比较优秀的。

[https_blog.csdn.net_yushiyi6453_article_details_76407640]: https://blog.csdn.net/yushiyi6453/article/details/76407640
[SouthEast]: /images/20220401/8f77e603cce54996be0a4231fd245268.png
[20161009190728886]: /images/20220401/d410f6f3a8154d6d811e09736019e44c.png
[20201009100055434.gif]: /images/20220401/1ad949a885f346159a38c6b610ef9fe8.png
[20161009190855230]: /images/20220401/9306080dcf774e3ea406e09b66c83011.png
[6f1e495521a1b510130e71c4b4a119ae.png]: /images/20220401/b9413b10843a4f258b26a1d6c5b496d6.png
[20161009191035090]: /images/20220401/5fc23e510d46409f99cd1ba43ea019d3.png
[cb345b3b3dc2ae27314570d8aa9b1830.png]: /images/20220401/4ec4f245019c40a687397f2d2d84085f.png
[SouthEast 1]: /images/20220401/6eac9cc377cf4e5eb0b5b08a4a1e8699.png
[SouthEast 2]: /images/20220401/cc7e6a18edbb4538a37fe3bd84c4d9f0.png
[20161009191011299]: /images/20220401/32f16dcd22b44f69ba5b7082b5faa505.png
[20150606133355179]: /images/20220401/ca8b4ec7f9f240b1850d595784c5b25b.png
[Center]: /images/20220401/70e5fd78af5543c78b441fd4a76916d7.png
[SouthEast 3]: /images/20220401/b6cdf0b5b96a430ea514a7c246dd94dd.png
[SouthEast 4]: /images/20220401/4b43cd3ca0e043c193a05c8dbb2cb516.png
[8cdd90954fa4e527190a7a7b48e0dfab.png]: /images/20220401/deb41cddeab0439ab05e863fe75217e5.png
[20161009190940095]: /images/20220401/efe1a9eacd4a4864a45f1e7d32fd01b0.png
[SouthEast 5]: /images/20220401/095c4d9c30c9439d83bca5ad4b1d0546.png
[SouthEast 6]: /images/20220401/544d478470ac48ecb591d6a079104916.png
[SouthEast 7]: /images/20220401/8ec01d9a93164b37ae1a43a99ba3120e.png
[SouthEast 8]: /images/20220401/dad3ee3e1b51464995336e51cab87021.png
[SouthEast 9]: /images/20220401/2f65213606f04779aefb21f902da6c72.png
[https_visualgo.net_zh]: https://visualgo.net/zh
[Link 1]: https://www.cnblogs.com/yu-chao/p/4324485.html