《数据结构与算法》——九个内部排序的总结

本是古典何须时尚 2021-12-12 22:11 193阅读 0赞

# 九种内部排序算法 #

## 绪 ##

内部排序在考研中会涉及到九种排序算法，分别是：直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序和基数排序。

它们可以根据不同的划分标准划分为不同的类别，例如：

根据排序操作划分：

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;width:91.9pt;"> 插入排序： </td> 
 <td style="vertical-align:top;width:322.9pt;"> 直接插入排序、折半插入排序、希尔排序 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:91.9pt;"> 交换排序： </td> 
 <td style="vertical-align:top;width:322.9pt;"> 冒泡排序、快速排序 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:91.9pt;"> 选择排序： </td> 
 <td style="vertical-align:top;width:322.9pt;"> 简单选择排序、堆排序 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:91.9pt;"> 其他排序： </td> 
 <td style="vertical-align:top;width:322.9pt;"> 归并排序、基数排序。 </td> 
 </tr> 
 </tbody> 
</table>

根据稳定性划分：

<table> 
 <tbody> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> 稳定： </td> 
 <td style="vertical-align:top;width:308.7pt;"> 直接插入排序、折半插入排序、 冒泡排序、归并排序、基数排序 </td> 
 </tr> 
 <tr> 
 <td style="vertical-align:top;width:106.1pt;"> 不稳定： </td> 
 <td style="vertical-align:top;width:308.7pt;"> 希尔排序、快速排序、简单选择排序、堆排序 </td> 
 </tr> 
 </tbody> 
</table>

本文本着易于理解、易于记忆的方法针对9个算法，从原理、算法思想、C++代码、时间复杂度、空间复杂度等方面进行逐个解析，**并综合9个算法特点对比总结在某些特定情况下最优算法选择（待完成）**。本文所有代码的编译环境为 ：win10专业版 + DEV C++ 5.11 + TDM-GCC 4.9.2 64bit 。

**目录**

九种内部排序算法

绪

一、直接插入排序

1.算法原理思想：

2.时间复杂度&空间复杂度

3.C++代码

二、折半插入排序

1.算法原理思想

2.时间复杂度&空间复杂度

3.C++代码

三、希尔排序

1.算法原理思想

2.时间复杂度&空间复杂度

3.C++代码

四、冒泡排序

1.算法原理思想

2.时间复杂度&空间复杂度

3.C++代码

五、☆快速排序

1.算法原理思想

2.时间复杂度&空间复杂度

3.C++代码

六、简单选择排序

1.算法原理思想

2.时间复杂度&空间复杂度

3.C++代码

七、☆堆排序

1.算法原理思想

2.时间复杂度&空间复杂度

3.C++代码

八、2-路归并排序

1.算法原理思想

2.时间复杂度&空间复杂度

3.C++代码

九、基数排序

1.算法原理思想

2.时间复杂度&空间复杂度

3.C++代码

十、综合比较

1.稳定性

2.适用性

3.动画演示

十一、参考文献

十二、总结

## 一、直接插入排序 ##

### 1.算法原理思想： ###

定义一个已知序列A，其中序列A是由两个序列——有序序列A1和乱序序列A2组成，即A=A1+A2。

取A2的首元素α与A1中各元素进行比较关键字值的大小，得出在A1中存在位置a1<=α<a2(若A1中的元素均小于α，则a2不存在，且α的位置应为A1序列的末端)，将α插入该位置，有序序列中的元素大于α的元素依次后移。A1、A2序列的长度发生变化，重复操作直至A2序列中无元素存在。

### 2.时间复杂度&空间复杂度 ###

时间的消耗为两个方面，一个是查找位置（比较），一个是放置（交换）。查找位置时，需要以此元素的前一位置向前进行一一比较，直至找到位置，并在比较的过程中进行元素的交换，最后将该元素插入目标位置，随后进行下一元素的查找。

最好的情况是该元素前所有的元素均小于该元素，即序列为正序序列，这样的比较次数即为n-1，并且无需交换移动元素，此时是时间复杂度为o(n)。

最坏的情况是该元素前的所有元素均大于该元素，即序列为倒序序列，这样第i（2<=i<=n）个元素的比较次数（第一次比较+移动时比较）为i次，移动次数（临时存储+交换+最终放置）为i+1次，此时总消耗时间为*i=2**n**i**+**i=2**n**(i+1)*=*n+3**\*(n-1)**2*，即时间复杂度为o(n²)。

一般情况下，序列为随机序列，取最优和最差两种情况的平均值各约为*n²**4*，所以一般情况下时间复杂度为o(n²)。

空间复杂度，因为除最优情况下外，其他情况均只借用了一个元素大小空间来存储交换时的临时数据，所以时间复杂度为o(1)。

### 3.C++代码 ###

string InsertSort(string ss){//直接插入排序
       //课本上是双参数，第二个参数是ss的长度
       //课本上函数的返回类型为void，第一个参数是序列指针
       int i,j;
       char temp;
       for(i=1;i<ss.length();++i){
             if(ss[i]<ss[i-1]){
                   temp = ss[i];
                   for(j = i-1;j>=0&&temp<ss[j];--j)
                         ss[j+1] = ss[j];
                   ss[j+1]= temp;
             }//if    
       } //for
       return ss;
 } //fun

## 二、折半插入排序 ##

### 1.算法原理思想 ###

注：符号在直接插入排序算法中有说明，不进行重复说明。

折半插入算法和直接插入算法很类似，不同的是比较的过程：因为A1序列为有序序列，所以比较大小的时候，α首先和中间位置的元素a(mid)比较大小，若α< a(mid),则α需和前部分A1\[low,mid-1\]比较，否则和后部分A1\[mid+1，high\]比较，以此类推，可以确定α的最终位置，进行元素的移动，随后进行下一元素的比较直到A2序列为空。

### 2.时间复杂度&空间复杂度 ###

对于时间复杂度，可以和直接插入排序进行比较分析：

放置（交换）所消耗的时间与直接插入相比完全相同。查找位置（比较）所进行的操作为：以当前序列中间元素为基准并以0.5的倍率减少序列的长度，单个元素比较次数最多为\[*log**2*n\](向上取整)。

最好的情况为正序，此时比较次数为n-1，移动次数为0，时间复杂度为o(n)。

最坏的情况为逆序，此时比较次数为*i=2**n*\[*log**2**i*\]，移动次数为*i=2**n**(i+1)*=*n+4**\*n**2*，时间复杂度分别为o(*nlog**2**n*) 和o(n²)，起决定性的为后者，所以时间复杂度为o(n²)。

一般情况下，其时间复杂度为：o(n²)，但实际执行时间比直接插入要短。

空间复杂度和直接插入排序算法相同。

### 3.C++代码 ###

string InsertSortBin(string ss){//折半插入排序
       //课本上是双参数，第二个参数是ss的长度 
       int i,j,low,mid,high;
       low = 0;
       char temp;
       for(i=1;i<ss.length();++i)
             if(ss[i]<ss[i-1]){
                   temp = ss[i];
                   low = 0;
                   high = i-1;
                   while(low<=high){//定位
                         mid = (low + high)/2;
                         if(ss[mid]<temp)
                               low = mid + 1;
                         else
                         high = mid - 1;
                   }
                   for(j = i-1;j>=high+1;--j)//移动赋值
                         ss[j+1] = ss[j];
                   ss[j+1]= temp;
             }//if    
       return ss;
 } //fun

## 三、希尔排序 ##

### 1.算法原理思想 ###

希尔排序可以直接插入排序为理解基础。直接插入排序和折半插入排序在排序的过程中是以1为步长进行比较，即当前元素比较结束后比较相邻下一个元素。这样的话如果序列呈基本倒序的话，每个元素要移动的次数就会很多，致使程序运行消耗较多时间。于是提出了希尔排序，它的基本思想是：

取一个小于n的步长，将原序列分割为若干个形如L\[I,i+d,i+2d,…i+kd\]的新子序列。例如：123456，取步长为2进行分割，得135，246两个序列。随后对于每个子序列内部进行直接插入排序，这样即完成一次操作。减少步长重复操作直至步长为1。

一般情况下，设增量为*d**1**=**n**2*，\[*d**i+1**=**d**i**2*\]向下取整，最后一个增量为1，即增量以*1**2*的倍率变化。

### 2.时间复杂度&空间复杂度 ###

时间复杂度当n在某个特定范围时，希尔排序的时间复杂度约为o(*n**1.3*)，在最坏的情况下希尔排序的时间复杂度为o(*n**2*).（书上所写）

与前两种插入方法相比较而言，希尔排序减少的时间体现在**单个元素与有序序列的比较次数**以及**有序序列中元素后移的次数。**

空间复杂度：仅使用了常数个辅助单元，所以空间复杂度为o(1)。

### 3.C++代码 ###

string ShellSort(string ss){//希尔排序
         //课本上是双参数，第二个参数是ss的长度 
         int i,j,dk;
         char temp;
         dk = ss.length()/2;
         while(dk>=1){
                  for(i = dk ; i < ss.length();++i)
                          if(ss[i]<ss[i-dk]){
                                   temp = ss[i];
                                   for(j = i-dk ;j >= 0 && ss[j]>temp; j -= dk)//比较交换
                                           ss[j+dk] = ss[j];
                                   ss[j+dk]= temp;
                          }//if 
                  dk = dk/2;
         }//while
         return ss;
 } //fun

## 四、冒泡排序 ##

### 1.算法原理思想 ###

冒泡排序是我学习计算机以来接触的第一个排序算法，当时就感觉这种方法比较慢，理解起来大的元素（气泡）先往上浮动。

定义一个已知序列A，其中序列A是由两个序列——有序序列A1和乱序序列A2组成，即A=A2+A1，长度为n=a+b;

在A2中取第一个元素α和第二个元素β比较大小，若α>β，则交换两个元素，若α<=β,则不进行操作。随后，第二个元素和第三个元素比较，以此类推，直到比较/交换完A2的最后一个元素为止，将A2最后一个元素添加到A1的首位,序列长度作相应变化。直到a=0或者此次排序元素位置未发生变动为止，此时序列为正序序列。

### 2.时间复杂度&空间复杂度 ###

本算法时间消耗分为两个方面，比较和交换。

最好的情况：顺序序列，此时需比较n-1次，移动0次，时间复杂度为o(n).

最坏的情况：倒序序列，此时第i个元素需比较和移动n-i次，求和得*n(n-1)**2*,总时间为*n(n-1)*，所以时间复杂度为o(n²)。

空间复杂度：只使用了有限常数个单元，所以空间复杂度为o(1)。

### 3.C++代码 ###

string BubbleSort(string ss){//冒泡排序
         //课本上是双参数，第二个参数是ss的长度 
         int i,j;
         bool flag = true;
         char temp;
         while(flag){
                  flag = false;
                  for(i = ss.length()-1 ; i >=1 && flag;--i)
                          for( j = 0 ; jss[j+1]){
                                           swap(ss[j],ss[j+1]);
                                           flag = true;
                                   }//if 
         }//while
         return ss;
 } //fun

## 五、☆快速排序 ##

### 1.算法原理思想 ###

快速排序是对冒泡排序的一种改进。快速排序是基于分治思想的，简单来讲就是，选定一个特定元素并找出其最终位置，这样的话一个混乱序列就变成了两个分散的子序列，对于每个子序列再执行上述过程直至子序列长度为1为止，此时整个序列即是有序的。

例如：53974621，如果直接用冒泡排序，第一趟结果展示：35946219，此时前7个元素仍为无顺序，因为这一趟的结果说明前7个元素都比9小，即它们在一个“属于它们的空间”，但不精确，没有更多的信息说明它们各自在什么位置，下一次前7个元素再分出一个属于前6个元素的空间，以此类推。

而快速排序的结果为1324 5 679，这个结果给出的就是，比5小的元素在前4位，比5大的元素在后面，可以清楚地看到除元素5以外剩余7个的位置相对来讲准确。这样再对两个子序列分别使用快速排序，以此类推。

由此可见，快速排序执行一趟获得的信息比冒泡排序获取的信息要更多更快，所以快速排序明显快于冒泡排序。当然这是从一个例子的角度去分析理解的。

从原理上来讲，这里引入分治法的概念思想，分治法是一个可以解决具有重复性的复杂问题的方法。它的步骤是：将母问题分解为若干个子问题——若子问题好解决则直接求解，否则继续进行分解（递归）——合并子问题的求解得到母问题的解。

快速排序速度较快的原因就是它不用进行重复的比较和交换，前序列的元素是不会和后序列的元素进行比较，更不用说交换了。但是冒泡排序中不管你是什么元素，一个字，比！再来个字，换！那么这个时候时间差就出来了。

### 2.时间复杂度&空间复杂度 ###

本算法时间消耗分为比较和交换，**具体的时间推导过程在《算法导论》一书中有说明，现在没有兴趣去看，等后面看了，再进行补充。**

最好的情况：每次选定的元素正好是当前序列的中间位置元素，此时时间复杂度o(*nlog**2**n*)。

最坏的情况：正序序列，逆序序列，时间复杂度为o(*n**2*)。

空间复杂度：使用到了递归，所需空间变大， o(*log**2**n*)。（证明过程后期补上）

### 3.C++代码 ###

struct ReturnStruct{//用于序列和特定位置值传递
         int num;
         string ss;
 };
 
 
 ReturnStruct Partation(string ss , int low , int high){
         char temp=ss[low];
         ReturnStruct rs;
         while(low < high){
                  while(low < high && temp<=ss[high]) //查找比当前值小的元素
                          high--;
                  ss[low] = ss[high];
                  while(low < high && temp>=ss[low])//查找比当前值大的元素
                          low++;
                  ss[high] = ss[low];
         }
         ss[low] = temp;
         rs.num = low;
         rs.ss = ss;
         return rs;
 }
 
 string QuickSort(string ss , int low , int high){//快速排序 
         if(low<high){
                  int i,j,*part;
                  ReturnStruct rs;
                  rs = Partation(ss,low,high);
                  ss = QuickSort(rs.ss,low,rs.num-1);//前部分
                  ss = QuickSort(ss,rs.num + 1,high);//后部分
         }      
         return ss;
 } //fun

## 六、简单选择排序 ##

### 1.算法原理思想 ###

简单选择算法可以理解为，经过不断比较选出乱序序列中最大的元素并将其放置于最高位，再选出次高元素放于次高位，以此类推。

### 2.时间复杂度&空间复杂度 ###

本算法时间消耗分为比较和交换，比较需要每个元素依次比较，交换是找到最大元素后才进行交换，故最多交换n-1次。当然交换所消耗的时间和比较所消耗的时间相比微不足道。o(*n**2*)

最好的情况：正序序列，此时只比较不交换， o(*n**2*)

最坏的情况： 每趟比较都需要交换元素，同上面所说，交换时间起不了决定作用。o(*n**2*)

空间复杂度： o(1)

### 3.C++代码 ###

string SelectSort(string ss){//简单选择排序 
         //课本上是双参数，第二个参数是ss的长度 
         int i,j,temp;
         for(i = ss.length()-1 ; i >=1;--i){
                  temp = i;
                  for( j = 0 ; jss[temp]){
                                   temp = j; 
                          }//if 
                  swap(ss[i],ss[temp]);      
         }//for
         return ss;
 } //fun

## 七、☆堆排序 ##

### 1.算法原理思想 ###

堆排序是一种树形选择排序的方法，它的特点是将序列L\[1…n\]看作是完全二叉树的顺序存储结构。根据父母节点和子女节点之间的数据关系，可以选择出最大或最小的元素，以此类推，父母节点的父母节点的…….父母节点即根节点即为整个序列中最大或最小的元素，选出最大元素的操作被称为建立大顶堆，选出最小元素的操作被称为建立小顶堆。（概念可以查询资料，当然这个也会在我的未来几篇博客中进行讲解。）

以自下向上调整大顶堆为例，初始序列为 asdfghjklqwert（n=14）

作图表如下：

*   *  从i =*n-1**2*=6,开始执行算法,第6位的一个子节点比当前节点值大，交换，i向前推进一位；
     *  i=5时，两个子节点r>h，交换，i向前推进一位；
     *  i=4时，两个子节点w>g，交换，i向前推进一位；
     *  i=3时，两个子节点l>f，交换，i向前推进一位；

此时堆图变为了：

*   *  i=2时，两个子节点t>d，交换，i向前推进一位；
     *  i=1时，两个子节点w>s，交换，i向前推进一位；

此时堆图变为了：

*  i=0时，两个子节点w>a，交换，此时已经到达根节点，结束一趟大顶堆的调整。watlsrdkfqgehj

此时堆图变为了：

对于堆排序来讲，将当前堆最高位与最低位的值进行交换，此时可以达到一个值完成排序的操作。

将新堆设置为jatlsrdkfqgeh，即去掉最后一个最大的元素，重复上述操作，直至所有的元素均放置于相应位置。

其中构建大小顶堆的过程就是选择排序中的 “选择”过程。

### 2.时间复杂度&空间复杂度 ###

本算法时间消耗：建堆时间为o(n)，之后又n-1次向下调整操作，每次调整的时间复杂度为o(h)，在平均情况下其时间复杂度为o(*nlog**2**n*)。【摘自《2019王道数据结构》】

最好的情况：逆序序列构建大顶堆，正序序列构建小顶堆，只比较不交换元素位置。

最坏的情况： 逆序序列构建小顶堆，正序序列构建大顶堆。

空间复杂度： 使用了常数个辅助单元，故时间复杂度为o(1)。

### 3.C++代码 ###

string AdjustDown(string ss ,  int num , int len){//自顶向下调整 ,len为最大序列下标
         char temp = ss[num];
         int  i;
         for(i = num*2;i <= len;i*=2){
                  i = ((i<len)&&(ss[i]<ss[i+1]))?i+1:i;//选定子女节点中的最大值
                  if(temp>=ss[i])//由于第一次执行算法时就是
                                 //从最底端最后一个元素进行比较的，
                                 //所以不用考虑子女节点的子女节点的值会大于当前父母节点的值，
                                 //因为这种情况绝不会出现！
                          break;
                  else{
                          ss[num] = ss[i];
                          num = i;
                  }//else     
         }//for
         ss[num] = temp;
         return ss;
 }//fun
 
 
 string AdjustUp(string ss ,  int len ){//自顶向下调整
         int i = len/2,j;//此次调整的首元素，需要判断其有无孩子节点
         //由孩子节点数量以及大小判定待交换元素
         j = ( (i*2 < len) && ss[i*2]>ss[i*2+1])?len-1:len;
         if (ss[j]>ss[i])
                  swap(ss[j],ss[i]);
         if((--i)<0)
                  return ss;
         for(;i>=0;i--){
                  j = (ss[i*2]>ss[i*2+1])?i*2:i*2+1;//确定待交换元素
                  if (ss[j]>ss[i])
                          swap(ss[j],ss[i]);
         }
         return ss;
 }//fun
 
 
 string BuildMaxHeap(string ss){
         ss = AdjustUp(ss,ss.length()-1);
         /*
         for(int i = (ss.length()-1)/2;i>=0;--i)//#取消-1
                  ss = AdjustDown(ss,i,ss.length());
         */
         return ss;
 }//fun
 
 
 string HeapSort(string ss){//堆排序 
         //调整时有两个算法一个是AdjustDown，
         //一个是AdjustUp，两个算法任选其一即可
         //在示例代码里，将需要用的算法在HeapSort()和 BuildMaxHeap()
         //两个方法里取消注释即可
         ss = BuildMaxHeap(ss);
         for(int i = ss.length()-1;i>=1;i--){//初始化为下标
                  swap(ss[0],ss[i]);
                  //ss = AdjustDown(ss,0,i-1);
                  ss = AdjustUp(ss,i-1);
         }
         return ss;
 } //fun

## 八、2-路归并排序 ##

### 1.算法原理思想 ###

归并排序算法也是基于分治法，它的核心思想是将那个有序的序列进行合并，序列的长度由1开始依次以整数倍增大至最终的n，每次不同的长度便进行一次合并，最终合并为最终序列。

而2路-归并排序是序列长度以2为倍数增大的归并排序算法。

示例：

下面有一个序列，其下标分别为1~16，表格中的数据表示下标，算法演示：

### 2.时间复杂度&空间复杂度 ###

本算法时间消耗每进行一趟算法，其时间复杂度为，o(n)，总共执行（*\[log**2**n\]*向上取整）次，所以总的时间复杂度为o(*nlog**2**n*)。

最好的情况：正序序列，只比较不交换。

最坏的情况：逆序序列，比较一次交换一次。

空间复杂度：需要一个辅助序列空间，o(n)。

### 3.C++代码 ###

string tt="                          ";
 
 string Merge(string ss , int low , int mid , int high ){//归并
         for(int k = low;k<=high;k++)//将现有序列元素复制到辅助空间当中
                  tt[k] = ss[k];    
         int c=low , i=low , j=mid+1;//对于新序列来讲，改变的元素为low~high位，其他位置不变
         for(;i<=mid && j<=high;c++){
                  if(tt[i]<=tt[j])
                          ss[c] = tt[i++];
                  else
                          ss[c] = tt[j++];
         }//顺序比较两个序列中元素大小
         while(i<=mid)
                  ss[c++] = tt[i++];
         while(j<=high)
                  ss[c++] = tt[j++];
         cout<<endl<<ss<<endl;
         return ss;
 }
 
 string MergeSort(string ss , int low ,int high ){//2路-归并排序 
         if(low<high){
                  int mid = (low+high)/2;
                  ss = MergeSort(ss,low,mid);
                  ss = MergeSort(ss,mid+1,high);
                  ss = Merge(ss,low,mid,high);  
         }
 
         return ss;
 } //fun

## 九、基数排序 ##

### 1.算法原理思想 ###

基数排序又被称为“桶排序”，它不是基于比较数据而进行排序，而是基于多关键字排序的思想进行排序的。**借助“分配”和“收集”两种操作对单逻辑关键字进行排序。**基排又被分为最高位优先（MSD）和最低位优先（LSD）排序。

以下例对最低位优先排序进行说明：

假设每个元素*a**i*是由d个位组成的（*a**i**=**k**i**0**+**k**i**1**+…+**k**i**d*）,其中*k**i*∈\[min,max\],即每个k*i**j*均有一定的取值范围。所以，可以使用r=num(max-min)个队列*Q**0**、**Q**1**、*……*Q**r-1*作为辅助空间。

以*k**i**d*为依据，将*a**i*存放至*Q**k**i**d*中，直至将所有的*a**i*全部插入完毕，将所有的Q首尾连接组成新的序列。随后以*k**i**d-1*位依据，重复以上操作，直到*k**i**0*这一步执行结束，此时得到正序序列。

### 2.时间复杂度&空间复杂度 ###

本算法时间消耗：基数排序需要进行d趟分配和收集，一趟分配需要o(n)，一趟收集需要o(r)，所以时间复杂度为o(d(n+r))。

最好的情况：和初始状态无关；

最坏的情况：和初始状态无关；

空间复杂度： 一趟排序需要的辅助空间是r个队列，且这些队列可以重复使用。所以空间复杂度为o(n)。

### 3.C++代码 ###

/*本着能偷懒就偷懒的原则，本算法从来没有实际实现过，今天是第一次实现
 
 完整可执行
 
 核心算法是LSDSort()方法
 
 */
 
 
 
 #include<iostream>
 #include<string>
 #include<queue>
 
 using namespace std;
 
 struct ReturnSs{
         string SS[100];
         int length;
 };
 
 ReturnSs LSDSort(ReturnSs sss , int n , int len){//基数排序-最低位优先
         queue<string> que[len];
         int l=n;
         while((--l)>=0){//趟数划分
                  for(int i = 0;i<sss.length;i++)//分配
                          que[sss.SS[i][l]-'a'].push(sss.SS[i]);
                  for(int j = 0,k = 0;j<len;j++)//收集——合并队列
                          while(!que[j].empty()){
                                   sss.SS[k++] = que[j].front();
                                   que[j].pop();
                          }//while
         }      
         return sss;
 } //fun
 
 int main(){
         //string ss = "asdfghjklqwertyuiopzxcvbnm";
         string temp[20] = { "ahd","dfg","htr","fds","dcv",
                              "gbf","ase","dcf","vgl","bnh",
                              "lkh","vfd","cvd","qwe","ewq",
                              "tgb","mji","ugr","cfa","olp"};
         string ok[20]   = { "ahd","ase","bnh","cfa","cvd",
                             "dcf","dcv","dfg","ewq","fds",
                             "gbf","htr","lkh","mji","olp",
                             "qwe","tgb","ugr","vfd","vgl"};
         ReturnSs sss;
         for(int i=0;i<20;i++)
                  sss.SS[i] = temp[i];
         sss.length = 20;
 
         sss = LSDSort(sss,3,26);
 
         cout<<"初始\t结果\t标准\t比较"<<endl;
         for(int i=0;i<20;i++){
                  cout<<temp[i]<<"\t"<<sss.SS[i]<<"\t"<<ok[i]<<"\t "<<(sss.SS[i]==ok[i])<<endl;
         }//判断排序是否成功
         return 0;
 }

## 十、综合比较 ##

### 1.稳定性 ###

<table> 
 <tbody> 
 <tr> 
 <td style="width:207.4pt;"> 是否稳定 </td> 
 <td style="width:207.4pt;"> 排序算法 </td> 
 </tr> 
 <tr> 
 <td style="width:207.4pt;"> 是 </td> 
 <td style="width:207.4pt;"> 直接插入 折半插入 冒泡排序 简单选择排序 2-路归并排序 基数排序 </td> 
 </tr> 
 <tr> 
 <td style="width:207.4pt;"> 否 </td> 
 <td style="width:207.4pt;"> 希尔排序 快速排序 堆排序 </td> 
 </tr> 
 </tbody> 
</table>

### 2.适用性 ###

适用性部分计划在后期刷题、编程的过程逐渐完善。

### 3.动画演示 ###

算法动画演示：

[https://www.bilibili.com/video/av685670?from=search&seid=4751620152043737654][https_www.bilibili.com_video_av685670_from_search_seid_4751620152043737654]

有个比较：（ps：随机排序真带劲儿！）

[https://www.bilibili.com/video/av25136272/?spm\_id\_from=trigger\_reload][https_www.bilibili.com_video_av25136272_spm_id_from_trigger_reload]

## 十一、参考文献 ##

1.  严蔚敏，吴伟民. 数据结构（C语言版）\[M\]. 北京： 清华大学出版社，2013.
2.  王道论坛 2019年数据结构考研复习指导\[M\]. 北京： 电子工业出版社，2018.

## 十二、总结 ##

在学习的过程中出现了以下问题：

1.  无法完全准确的命中函数中循环的边界值，究其原因为算法理解不到位以及编程经验少；
2.  算法的时间复杂度以及空间复杂度不能完全的计算出来，原因为算法理解不到位以及数学基础不扎实；
3.  在文中可能会出现笔误、理解错误、计算错误等问题，若读者有发现，还请不吝指正。
4.  我要去看辛巴！！！

[https_www.bilibili.com_video_av685670_from_search_seid_4751620152043737654]: https://www.bilibili.com/video/av685670?from=search&seid=4751620152043737654
[https_www.bilibili.com_video_av25136272_spm_id_from_trigger_reload]: https://www.bilibili.com/video/av25136272/?spm_id_from=trigger_reload