devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

排序算法的详解和分析对比（详细讲解）_各种排序算法的总结和比较

作者：Gausst松鼠会 | 2024-02-29 06:01:20

赞

踩

各种排序算法的总结和比较

前言

        排序算法各式各样，每种排序算法的思想也大同小异。读者应该深度了解每种算法的基本思想、排序每一步过程细节和每种排序的特性，看到特定的序列，应该立马想到最适合的排序方法。

一、排序的概念

什么是排序：将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程叫做排序。为了查找方便。计算机中的数据表都希望是按照关键字有序的，一般按照递增或递减方式排列。

排序算法的稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。（百度百科中的定义）

通俗的判断稳定性：假设小明高考分数为610分，小红高考分数也为610分，原名单表中，小明名字出现在小红前面。现在班主任对未排序的分数名单表按照总分进行排序，如果排序完后小明仍在小红前面，则该排序算法是稳定的；如果小红排在小明前面，则该排序算法是不稳定的。

二、排序的分类

以下是在数据结构中所会遇到的几类排序算法：

 内排序和外排序的区别：

        内排序定义：排序期间所有数据对象全在内存中完成。（一次性排序完）

        外排序定义：排序期间数据对象过多，导致不能一次性全部放入内存当中，必须根据排序过程要求，不断在内存、外存之间进行读写操作。（分成多部分进行排序）

        主要区别：影响内排序效率主要是比较次数，也就是时间复杂度；影响外排序效率主要是IO次数，也就是CPU的读写速度（比较次数也影响外排序效率，但是在操作系统中我们可以得知，CPU的运行速度要远大于其输入输出速度，所以可以把CPU处理速度忽略不计）。

三、常见排序算法的原理以及思想

1. 直接插入排序

1.1 直接插入排序的思想

 基本思想：直接插入排序是插入排序中最简单的一种排序，基本思想是每次将一个待排序的关键字按大小插入前面已排好的 “子序列” 中，直到全部关键字插入结束。

 通俗的解释：就好比我们在打扑克牌类似，一堆凌乱的牌在手中，我们需要进行从小到大进行整理。一般习惯于从手边右边大，左边小的顺序进行整理扑克牌，这是摸到一张牌时候，我们会很自然的将牌从左边整理好的牌面进行查找，选择一个合适的位置进行插入。

 1.2 直接插入排序代码实现

        （1）此代码a[0]未当数据，把a[0]当初一个哨兵（中间过渡用的），数据从a[1]开始。

  1. void InsertSort(a[], int n){    //数据从a[1]开始，a[0]作为哨兵进行辅助排序
  2.     int i,j;
  3.     for(i=2;i<n;i++){           //依次将a[2]~a[n]插入到前面已排好的序列，最初始的序列为a[1]
  4.         if(a[i]<a[i-1]){        //当i所在的数字小于前面数字时，将其插入到前排好序列中
  5.              a[0]=a[i];         //复制哨兵，a[0]不存放元素
  6.              for(j=i-1;a[0]<[j];j--)   //在排好序列中从后往前查找要插入的位置
  7.                 a[j+1]=a[j];           //向后挪位
  8.              a[j+1]=a[0];              //复制到插入位置
  9.         }
  10.     }
  11. }

         （2）数组从a[0]开始，另外设置一个过渡变量t进行充当哨兵。

  1. void InsertSort(a[], int n){    //数据从a[0]开始，t作为哨兵进行辅助排序
  2.     int i,j,t=a[0];
  3.     for(i=1;i<n;i++){           //依次将a[0]~a[n-1]插入到前面已排好的序列，最初始的序列为a[0]
  4.         if(a[i]<a[i-1]){        //当i所在的数字小于前面数字时，将其插入到前排好序列中
  5.              t=a[i];         //复制哨兵
  6.              for(j=i-1;a[0]<a[j];j--)   //在排好序列中从后往前查找要插入的位置
  7.                 a[j+1]=a[j];           //向后挪位
  8.              a[j+1]=t;              //复制到插入位置
  9.         }
  10.     }
  11. }

1.3 直接插入排序的详细过程       

设有原始数据a[10]={544，585，692，209，405，224，687，439，835，778}；

 按照上述算法进行每次直接插入排序的过程细节。

在每一趟的基础上，我们根据程序代码深度理解直接插入排序算法的步骤。

1.4 直接插入排序算法的性能分析

        空间效率：仅使用一个哨兵t或者a[0]作为辅助单位，所以空间复杂度位O(1)。

        时间效率：在排序过程中，每个关键字插入需要操作n-1次，每次插入都要从前往后进行大小比较和移动元素，比较次数和移动次数取决于初始的序列的状态。         

        最优情况下：数组中元素已经有序，这时我们只需插入每个元素，无需过多的比较，而且不用移动元素，所以时间复杂度为O(n)。

        最坏情况下：数组的顺序与想要的顺序要全相反，比较次数会最多，为\sum_{i=2}^{n} i，移动次数也最多，为\sum_{i=2}^{n}(i+1)，所以时间复杂度为O(n^{2})。

        平均情况下：考虑每次排序的数组都元素都是随机的，因此可以取最优和最坏情况的平均值作为平均情况的时间复杂度，总比较次数与移动次数约为\frac{n^{2}}{4}。

        因此，直接插入排序算法的时间复杂度为O(n^{2})。

        稳定性：直接插入每次都是从后往前比较然后移动，当两个元素相同时候，既a[j]=a[j-1]时候，并不会进行移动，所以相同元素的先后位置并未发生改变，所以直接插入排序算法是一个稳定的排序方法。

        使用性：直接插入排序算法适用于顺序存储和链式存储的线性表。（若为链式存储时，可以从前往后查找指定元素的位置。）

         p.s.：大部分内排序算法都仅适用于顺序存储的线性表。

小彩蛋：插入排序舞蹈小视频，在学习插入排序后，就能很好理解该舞蹈乐趣所在，有兴趣的同学可以和班级里同学一起编排该舞蹈娱乐娱乐。

插入排序y

2. 希尔排序

2.1 希尔排序的思想

希尔排序是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。

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

通俗的解释：假设一些带有编号的运动员要进行排序，我们可以每隔五个的运动员分批进行内部排序， 之后再让每隔两个的运动员分配进行内部排序，最后让每隔一个的运动员，也就是全部运动员进行排序。虽然可能看上去会很复杂，但是每次排序完后，下一次排序会成倍的减少排序次数。

2.2 希尔排序代码实现

  1. void shellSort(int a[],int n){
  2. 	int i,j,t;
  3. 	int d=n;
  4. 		while(true){
  5. 		d=d/2;	//每次都将距离减少一般 
  6. 		 for(int x=0;x<d;x++){		//把数字分成了d个组进行排序 
  7.  
  8. 		    //--------------------------直接插入排序---------------------------
  9. 		 	//进行常规的直接插入排序，但是每次间隔不是原来的1了，而是变成了d 
  10. 			 for(i=x+d;i<n;i=i+d){		// 依次将每一组数据进行插入到排好的序列中 
  11. 		 		if(a[i-d]>a[i]){	// 当i所在组的数字小于前面数字时，将其插入到前排好序列中
  12. 		 			t=a[i];			//复制哨兵 
  13. 		 			for(j=i-d;j>=0&&a[j]>t;j=j-d){//在排好序列中从后往前查找要插入的位置
  14. 		 				a[j+d]=a[j];//向后挪位
  15. 					 }
  16. 					 a[j+d]=t;//复制到插入位置
  17. 				 }
  18. 			 }
  19.            //------------------------------直接插入排序-------------------------
  20. 		 }
  21. 		if(d<=1)
  22. 		 break;
  23. 	}
  24. }

2.3 希尔排序的详细过程

 (该程序会在文章最后供大家免费使用)

我们可以从每次排序后看出，每一次插入排序，我们的移动次数都是很少，尽管到了最后是全部元素的直接插入排序，但由于前两次的排序调整，只有少部分的数字还没按照顺序排列，但是数组中的序列已经相对有序了，所以再直接插入排序中，只需要移动个别元素就行了，极大的减少了排序因为移动元素而影响了时间效率。

 2.4 希尔排序算法的性能分析

        空间效率：仅使用常数个辅助单位，所以空间复杂度位O(1)。

        时间效率：由于希尔排序的时间复杂度依赖于增量序列的函数，这个数学上还没有得到确实的解决，所以时间复杂度分析起来非常困难。当n再某个特定范围时，希尔排序的时间复杂度约为 O(n^{1.3})。在最坏情况下希尔排序的时间复杂度为 O(n^{2})。

        稳定性：当相同元素呗划分成不同的子表时，可能会改变它们相对次序，因此希尔排序是一种不稳定的排序方法。

读者可以试试：{13   27   \tfrac{}{49}   55   4   49    38    65    97    76} 该序列用希尔排序后每一步的详细过程，并判断是否稳定。（提升：该序列不稳定）

小彩蛋：希尔排序舞蹈小视频，在学习希尔排序后，就能很好理解该舞蹈乐趣所在，有兴趣的同学可以和班级里同学一起编排该舞蹈娱乐娱乐。

希尔排序y

3. 冒泡排序

3.1 冒泡排序的思想

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中的二氧化碳气泡最终会上浮到顶端一样，故名“冒泡排序” 

基本思想：从后往前（或从前往后）两两比较相邻元素的值，若为逆序（即a[i-1]>a[i]），则交换它们，直到序列比较完。每一轮又有最大（或最小）未排序的元素排序完成。

3.2 冒泡排序代码实现

  1. void bubble_sort(int a[], int n) {
  2.         int i, j, t，flag;
  3.         for (i = 0; i < n - 1; i++){
  4.                 flag=0;                //flag用于判断序列是否一开始就有序，防止过多比较
  5.                 for (j = 0; j < n - 1 - i; j++)
  6.                         if (a[j] > a[j + 1]) {    //前面数据大于后面，进行交互位置
  7.                                 t = a[j];
  8.                                 a[j] = a[j + 1];
  9.                                 a[j + 1] = t;
  10.                                 flag=1;
  11.                         }
  12.         if(flag==0)            //本次遍历后没有发生交换，说明已经有序
  13.             return ;
  14.     }
  15. }

（可以改变if里面的判断大小来改变冒泡一开始的排序规则）

3.3 冒泡排序的详细过程

3.4 冒泡排序算法的性能分析

空间效率：仅使用常数个辅助单位，所以空间复杂度位O(1)。

时间效率：当初始序列完全有序时，显然第一趟冒泡后flag依然为0（本次冒泡没有元素进行交换），直接跳出循环，比较次数为n-1次，移动次数为0，所以最优情况下时间复杂度为O(n)；当初始序列为完全逆序时候，需要进行n-1趟排序，第i趟排序要进行n-i次元素的比较，而且每次比较后要进行3次的元素交换元素位置。

        这种情况下，比较次数=\sum_{i=1}^{n-1}\left ( n-i \right )= \frac{n(n-1))}{2},移动次数=\sum_{i=1}^{n-1}3(n-i)=\frac{3n(n-1)}{2}，所以最坏情况下的时间复杂度为 O(n^{2})，其平均时间复杂度也为 O(n^{2})。

稳定性：由于i>j且a[i]=a[j]时候，不会发生交换，因此冒泡排序是一种稳定的排序算法。

注意：冒泡排序所产生的有序子序列一定是最终的排序位置。

小彩蛋：冒泡排序舞蹈小视频，在学习冒泡排序后，就能很好理解该舞蹈乐趣所在，有兴趣的同学可以和班级里同学一起编排该舞蹈娱乐娱乐。

冒泡排序y

4. 快速排序

4.1 快速排序的思想

基本思想：快速排序的基本思想是基于分治法（分而治之），也是"交换"类的排序，它通过多次划分操作来实现排序。以升序为例，其执行流程可以 概括为;每一趟选择当前所有子序列中的一个关键字（通常是第一个）作为枢轴，将子序列中比枢轴小 的移到枢轴前面，比枢轴大的移到枢轴后面;当本趟所有子序列都被枢轴以上述规则划分完毕后会得到 新的一组更短的子序列，它们成为下一趟划分的初始序列集。

通俗的解释：首先在数组中取第一个数作为哨兵（基准数）；分区过程，将比这个大的数放在这个数右边，把比这个小的数放到这个数的左边（所以每次排序完成后都有一个数放到指定位置）；再以这个数划分成左右两个分区，直到每个区间只剩下一个数为止。

注意：很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影，所以快速排序是所有排序中比较重要的、有意义的一种排序。

4.2 快速排序算法的代码实现

  1. int partition(int *a,int low,int high){
  2. 	int pivot = a[low];		//取第一个数字当成哨兵 
  3. 	while(low<high){		//左右开始查找符合要求的数值 
  4. 		while(low<high&&a[high]>=pivot) high--;//进行遍历，从数值右边找比哨兵值小的再停下来 
  5. 		a[low]=a[high];						//刚查到的小于哨兵值的数与当前low所在数进行交换 
  6. 		while(low<high&&a[low]<=pivot)  low++;//进行遍历，从数值右边找比哨兵值大的再停下来 
  7. 		a[high]=a[low];				//刚查到的大于哨兵值的数与当前数high所在数进行交换 
  8. 		
  9. 	}
  10. 	a[low]=pivot;				//剩余一个空位，把哨兵填进去，该数这个位置已经是最终序列位置 
  11. 	return low;
  12. }
  13.  
  14. void quickSort(int *a,int low,int high){
  15. 	if(low<high){	 
  16. 		int pivotpost = partition(a,low,high);		//找到上一个哨兵位置现在位置 
  17. 		quickSort(a,low,pivotpost-1);		//左边遍历 
  18. 		quickSort(a,pivotpost+1,high);		//右边遍历 
  19. 	}
  20. 	
  21. }

4.3 快速排序的详细过程

  上面是每一趟排序的基本过程，接下来我要给大家讲解每一次比较进行改快速排序。

第一趟快速排序详细步骤：（考研常考题）

 第二、三趟快速排序详细步骤：

由于我们代码是向往左边递归，再往有边递归的（如果代码递归次序不一样，那画图次序是相反的）

 第四、五趟快速排序详细步骤：

 注意：一般考研只需要写第一趟排序的全过程就行了，所以大家也只需要对第一趟排序进行学习就行，后面的排序过程可以了解了解。如果想要直到后面几次排序的过程为什么会出现有排序一起并发执行，就需要了解堆栈的过程。所有如果了解堆栈，也可以尝试着将该递归的排序算法改成非递归的排序算法，大家有兴趣可以尝试一下，用来熟悉快速排序的整个过程。

4.4 快速排序算法的性能分析

空间效率：本算法的空间复杂度为 O(n{log_{2}}^{n})。快速排序是递归进行的，递归需要栈的辅助，因此它需要的辅助 空间比前面几类排序算法大。

时间效率：快速排序最好情况下的时间复杂度为 O(n{log_{2}}^{n})，待排序列越接近无序，本算法的效率越高。最坏情 况下的时间复杂度为 O(n)，待排序列越接近有序，本算法的效率越低。平均情况下的时间复杂度为 O(n{log_{2}}^{n})。快速排序的排序趟数和初始序列有关。 说明;后面还会出现多个时间复杂度同为 O(n{log_{2}}^{n})的排序算法，但仅有本节的算法称为快速排序， 原因是这些算法的基本操作执行次数的多项式最高次项为 X×n{log_{2}}^{n}(X为系数)，快速排序的X最小。 可见它在同级别的算法中是最好的，因此叫作快速排序。

 稳定性：在划分算法中，若右端区间有两个关键字相同，且均小于基准值的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序是一种不稳定的排序方法。

小彩蛋：快速排序舞蹈小视频，在学习快速排序后，就能很好理解该舞蹈乐趣所在，有兴趣的同学可以和班级里同学一起编排该舞蹈娱乐娱乐。

快速排序y

5. 简单选择排序

5.1 简单选择排序的思想

 基本思想：选择类排序的主要动作是"选择"，简单选择排序采用最简单的选择方式，从头至尾顺序扫描序列， 找出最小的一个关键字，和第一个关键字交换，接着从剩下的关键字中继续这种选择和交换，最终使序 列有序。

通俗的解释：从一个队列中从前往后找一个最小的数往第一个未排序的数交换（非递减为例），直到找到最后一个数为止。

5.2 快速排序算法的代码实现

  1. void selectSort(int a[],int n){
  2. 	int i,j,t,min;
  3. 	for(i=0;i<n-1;i++){
  4. 		min=i;				//设第一个为最小 
  5. 		for(j=i+1;j<n;j++){	  //找出最小的数字下表 
  6. 			if(a[j]<a[min])
  7. 				min=j;
  8. 		}
  9. 		if(min!=i){			//找出最小的，然后把i复制给min 
  10. 			t=a[i];
  11. 			a[i]=a[min];
  12. 			a[min]=t;
  13. 		}
  14. 	}
  15.  
  16. }

5.3 简单选择排序的详细过程   

下面是每次排序时候，在无序子序列中选择的最小值和前面数值交换的整个过程。

5.4 简单选择排序算法的性能分析

空间效率：仅使用常数个辅助单元，所以空间效率为O(1)。

时间效率：通过算法源代码我们可以看出，两次循环的执行次数和初始序列没有关系，外循环执行n次，内循环执行n-1次，将最内层循环中的比较操作视为最关键的操作，其执行次数为\frac{(n-1+1)(n-1)}{2}=\frac{n(n-1)}{2}，时间复杂度为 O(n^{2})。

稳定性：在第i趟找到最小值后，和第i个元素交换，可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。例如：{3，3，1}，排序完后，就会变成{1，3，3}，两个3的前后位置发生了改变。所以简单选择排序算法是一种不稳定的排序算法。

小彩蛋：选择排序舞蹈小视频，在学习选择排序后，就能很好理解该舞蹈乐趣所在，有兴趣的同学可以和班级里同学一起编排该舞蹈娱乐娱乐。

选择排序yu

6. 堆排序

6.1 堆排序的思想

什么是堆：堆是一种数据结构，可以把堆看成一棵完全二叉树，这棵完全二叉树满足∶任何一个非叶结点的值 都不大于（或不小于）其左、右孩子结点的值。若父亲大孩子小，则这样的堆叫作大顶堆;若父亲小孩 子大，则这样的堆叫作小顶堆。

基本思想：根据堆的定义知道，代表堆的这棵完全二叉树的根结点的值是最大（或最小）的，因此将一个无序 序列调整为一个堆，就可以找出这个序列的最大（或最小）值，然后将找出的这个值交换到序列的最后 （或最前），这样，有序序列关键字增加1个，无序序列中关键字减少1个，对新的无序序列重复这样的 操作，就实现了排序。这就是堆排序的思想。

堆排序中最关键的操作是将序列调整为堆。整个排序的过程就是通过不断调整，使得不符合堆定义的完全二叉树变为符合堆定义的完全二叉树。

注意：考研中常常出现堆排序的身影，但是大多数情况下都只是要求考生画出堆排序的调整大根堆或者小根堆的过程。编写代码而言，大多数人还是比较困难的，所以这就要求我们加大提升自己的代码水平能力。（大家也可以去看看青岛大学王卓老师讲数据结构堆排序的讲解）

6.2 堆算法的代码实现

  1. //调整堆
  2. void HeadAdjust(int *a,int k,int n){
  3. 	a[0]=a[k];				//a[0]用于存放子树的根结点 
  4. 	for(int i=2*k;i<=n;i*=2){		//进入他的孩子结点，因为k说在结点的孩子结点是2k和2k+1 
  5. 		if(i<n&&a[i]<a[i+1])	//判断左右孩子谁大 ，左孩子大i不变，右孩子大i加一 
  6. 			i++;
  7. 		if(a[0]>a[i])		//判断k所在的值与最大的孩子值谁大 
  8. 			break;
  9. 		else{	//k所在位置值大不变，孩子大进行把孩子赋值给k所在位置的值 
  10. 			a[k]=a[i];
  11. 			k=i;
  12. 		}
  13. 		a[k]=a[0];		//被筛选结点的值放入最终位置 
  14. 	}
  15. }
  16.  
  17.  
  18. //建立初始大根堆
  19. void BuildMaxHeap(int *a,int n){
  20. 	for(int i=n/2;i>1;i--){	//从i=[n/2]~1，反复调整堆 
  21. 		HeadAdjust(a,i,n);
  22. 	}
  23. }
  24.  
  25.  
  26. //堆排序
  27. void HeapSort(int *a,int n){
  28. 	int t;	
  29. 	BuildMaxHeap(a,n);	//先建立初始堆 
  30. 	for(int i=n;i>1;i--){		//n-1趟的交换和建堆过程 
  31. 		t=a[i];
  32. 		a[i]=a[1];			//堆顶和堆低元素交换 
  33. 		a[1]=t;
  34. 		HeadAdjust(a,1,i-1);		//调整，把剩余的i-1个元素整理成堆 
  35. 	}
  36. }

在该代码中，我们选择是将序列调整成大根堆，如果大家想要用小根堆的话，也可以进行尝试。

6.3 堆排序的详细过程   

在堆排序中，数组a所呈现的值如下图

 （1）将上述数组用完成二叉树的形式构建出来如下图（a[0]是空的我们就直接从a[1]开始构建）

 （2）将初始的完成二叉树进行初始构建大根堆如下图（就是代码中BuildMaxHead函数）

 

 

 

注意：数据交换之后，要看下面有小堆没有完成大根堆的调整，要继续对小堆将其大根堆调整

（3）将排好的大根堆数据移到数组后面，也是就树的最后一个元素进行交换。

 （4）重复（1）中的操作进行之后的大根堆调整。

第二趟堆排序

第三趟堆排序

第四趟堆排序

 第五趟堆排序

 

 第六趟堆排序

第七趟堆排序

 第八趟堆排序

 第九趟堆排序

注意：我们可以发现，每一次排序完成之后，总会有一个元素在其规定的位置上面，而且排序好的序列都是按照从小到大或者从大到小的顺序固定好的。我们就可以利用这种特性，用来求前几位或者后几位的排序（比如：求前三名的成绩）。

         在考研或者软考中，一般都只要求第一趟弄成大根堆的形式，所以读者着重把第一次排序弄情况什么情况就差不多了。但是想要真正了解程序，还是需要把每一次排序过程全部自己演算一遍，会让自己更加熟悉。

6.4 堆排序算法的性能分析

空间效率：仅使用了常熟个辅助单元，因此空间复杂度为O(1)。

时间效率：建堆时间为O(n)，之后n-1次向下调整操作，每次调整的时间复杂度为0(n)，所以无论是在最优、最坏、平均情况下，堆排序的时间复杂度为  O(n{log_{2}}^{n})。

稳定性：进行筛选时候，有可能把后面相同关键字的元素调整到前面，所以堆排序是一种不稳定的排序算法。例如：{1，4，4}，构造初始堆时困难将2交换到堆顶，此时{4，1，4}，最终排序变成了{1，4，4}，所以4与4位置已经发生变化。

7. 归并排序

7.1 归并排序的思想

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

7.2 归并算法的代码实现

  1. //因为要放在a数组中，所以要用b进行辅助 
  2. int *b = (int *)malloc((n+1)*sizeof(int));	//	辅助数组b 
  3.  
  4. void Merge(int *a,int low ,int mid ,int high){
  5. 	//a的两段a[low...mid]和a[mid+1...high]各自有序，将其合并成一个数组 
  6. 	int i,j,k;
  7. 	for(k=low;k<=high;k++)		//将a数组赋值给b 
  8. 		b[k]=a[k];
  9. 	for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){	 
  10. 		if(b[i]<=b[j])	//比较b的左右两段中的元素 
  11. 			a[k]=b[i++];	//将较小的值复制到a中 
  12. 		else
  13. 			a[k]=b[j++];
  14. 	}
  15. 	while(i<=mid)	a[k++]=b[i++];//若第左边表没有检测完，直接全部复制 
  16. 	while(j<=high)	a[k++]=b[j++];//若第右边表没有检测完，直接全部复制
  17. }
  18.  
  19. void MergeSort(int *a,int low ,int high){
  20. 	if(low<high){
  21. 		int mid=(low+high)/2;	//从中间划分两个子序列 
  22. 		MergeSort(a,low,mid);	//对左子序列进行递归 
  23. 		MergeSort(a,mid+1,high);//对右子序列进行递归 
  24. 		Merge(a,low,mid,high);	//归并 
  25. 	}
  26. }

7.3 归并排序的详细过程

 每次划分子序列和归并子序列的细节

注意：归并排序就类似于我们在数据结构第一章学的两个有序链表合并成一个链表的那种基本操作，只是加了分治法的思想先将序列进行层层拆分，然后才能将有序表进行合并。

 7.4 归并排序算法的性能分析

空间效率：因为归并排序需要转存整个待排序序列，所以空间复杂度为O(n)。

时间效率：每趟归并时间复杂度O(n)，一共要进行{log_{2}}^{n}向上取整趟进行归并，所以时间复杂度为   O(n{log_{2}}^{n})。

稳定性：由于Merge( )操作不会改变相同元素值的相对次序，所以归并排序是一种稳定的排序算法。

小彩蛋：插入排序舞蹈小视频，在学习插入排序后，就能很好理解该舞蹈乐趣所在，有兴趣的同学可以和班级里同学一起编排该舞蹈娱乐娱乐。

归并排序y

8. 基数排序

8.1 基数排序的思想

基本思想：基数排序的思想是"多关键字排序"，前面已经讲过了。基数排序有两种实现方式;第一种叫作最高 位优先，即先按最高位排成若干子序列，再对每个子序列按次高位排序。

通俗的解释：举扑克牌的例子，就是先按花 色排成4个子序列，再对每种花色的13张牌进行排序，最终使所有扑克牌整体有序。第二种叫作最低位 优先，这种方式不必分成子序列，每次排序全体关键字都参与。最低位可以优先这样进行，不通过比较， 而是通过"分配"和"收集"。还是扑克牌的例子，可以先按数字将牌分配到13个桶中，然后从第一个 桶开始依次收集;再将收集好的脾按花色分配到 4个桶中，然后还是从第一个桶开始依次收集。经过两 次"分配"和"收集"操作，最终使牌有序。

注意：基数排序一般在考研和软考中不要求写代码出来，因为该排序的数据类型不同，选用的排序方法也会不同。只需要了解基数排序的整个过程就行，一般会在选择题或者填空要求写出第一次排序情况，也有简答题画出第一次排序情况。

8.2 基数算法的代码实现

  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. }

8.3 基数排序的详细过程

（1）用数组直接查找每一位的顺序

 （2）链式基数排序，用链表来排序每一位的顺序。（考研常考）

个位数开始排列

 十位数开始排列

 百位数开始排列

 8.4 基数排序算法的性能分析

空间效率：基数排序空间复杂度为O(r)，r为队列长度。

时间效率：基数排序平均和最坏情况下都是O(d(n+r))。

稳定性：基数排序排序是一种稳定的排序算法。

四、不同排序算法的对比

1. 算法运行时间、比较次数和移动次数对比

上述我们介绍了数据结构中最经典的八种排序算法：直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序以及基数排序。我们现在通过实验平台来进行实验比对这些排序算法在不同情况下的运行时间、比较次数和移动次数。

一、我们用随机数随机出来5万条数据，下面是我们运行出来的结果。

（1）排序用时（从高到低来排列）

        （1）简单选择排序（2）直接插入排序（3）折半插入排序（4）冒泡排序

        （5）递归归并排序（6）希尔排序       （7）二路归并排序（8）堆排序

        （9）基数排序       （10）快速排序2   （11）快速排序

（2）比较次数（从高到低来排列）

        （1）简单选择排序        （2）冒泡排序        （3）直接插入排序        （4）希尔排序

        （5）快速排序               （6）堆排序            （7）快速排序2         （8）折半插入排序                （9）二路归并排序        （10）递归归并排序

由于基数排是通过不同数位来进行排序的，所以无需进行比较，详细请看上面写的基数排序。

（3）移动次数（从高到低来排列）

        （1）冒泡排序       （2）直接插入排序        （3）折半插入排序 （4）希尔排序

        （5）二路归并排序（6）递归归并排序        （7）堆排序            （8）快速排序2      

        （9）快速排序        （10）简单选择排序 

由于基数排是通过不同数位来进行排序的，所以无需进行移动，只需要进行存储就行，详细请看上面写的基数排序。

        我们可以清楚的发现，简单选择排序、直接插入排序、折半插入排序和冒泡排序的运行时间数量级远大于其他排序算法。这几种算法都是效率很低的算法，尤其是直接插入排序和冒泡排序，无论是运行时间、比较次数和移动次数，都是非常高的。所以在现实中我们写排序算法，应该尽量避免运用，让我们系统更加高效，让用户体验感更好。

二、 我们用随机数随机出来1000万条数据，下面是我们运行出来的结果。

在千万级别的数据规模下，我们只选取了算法效率高的几种算法。从中我们可以发现，快速排序的运行时间低于其他几种排序，而基数排序的时间最多。而且基数排序在这种情况下，所有的空间也是千万级别的，所以我们尽量在排序大数据时候，避免运用基数排序，多用快速排序。

2.不同数据规模的运行时间分析

小知识：有时候运行该程序时候，可以发现小数量级的运行时间，比大数量级的排序时间更久，这是因为在运行程序时候，我们不能保证每次电脑运行环境都是一样的，可能在运行一千数据时候，我们电脑的一些进程将其挂起，现运行其他优先级高的进程，所有导致运行时间增加。

Y轴坐标是扩大1000倍之后的运行时间，因为在开头，我们发现，运行时间过短，导致只有毫秒级，不利于我们观察。

注意： 因为选择排序、直接插入排序、折半插入排序和冒泡排序，在上述讲，这四种排序是算法效率较低的几种排序算法，如果数据过大，就会导致运行时间差异性过大，导致没有可比性，所以我们只对低数量级的部分数据进行检测分析。

 注意： 在上述讲，这六种排序是算法效率较高的几种排序算法，如果数据过小，就会导致运行时间没有太大区别，导致没有可比性。就比如在2000000数量以前，所有的运行时间都是基本重叠，导致很难观察，所以我们只对大数据样本进行检测分析。

3. 算法运行时间总结

 注意：In-place指运用常数个辅助空间，与数据规模n无关，大多数是O(1)。

            Out-place指运用的辅助空间大小与数据规模n有关，大多数是O(n)。

            基数排序中的k是指数组中的数的最大的位数，比如数组中最大的数为999，所有k=3

        一些简单的排序算法中，虽然效率不高，但是在低数量规模情况下，就比如一万数量级以下，一般运行时间还能可以被人们所接受，零点几秒左右很难被察觉出来。但是如果到了十万数量级，排序就需要非常久的时间，可能会导致我们一些系统会出现误差，从而引起巨大的麻烦和问题。而在这些简单算法中，比较优秀的是折半插入排序，相对于其他三种排序来说，他的运行效率是最高的，所用的时间，从数据规模来看，都是最少的。所以如果大家忘记其他比较复杂高效率的排序算法时候，可以选择折半插入排序进行排序。

        在比较难的排序算法中，其效率肯定是比前四个简单的排序算法高。但是其实现起来也比较麻烦，所以需要读者反复堆这些算法进行学习和巩固，加强自己的理解。

        从整体上看，运行时间无论在哪个数量级上面，快速排序<STL排序<归并排序<堆排序<希尔排序<基数排序。所以在没有特定要求的条件下，我们尽可能的使用快速排序来对我们所编写的系统进行相关数据排序。

4. 特定条件下选用排序算法

（1）当n较小，我们可采用直接插入排序或简单选择排序。但是直接插入排序移动次数较简单选择排序的多，所以当记录本身信息量较多时，用简单选择排序较好；所以当记录本身信息量较少时，用直接插入排序较好。

（2）当n较大，就可以在效率高的排序算法中选一种（时间效率为  O(n{log_{2}}^{n})），所以可以从堆排序、快速排序、归并排序中进行选择。

        快速排序：当序列没有规律分布时候，其平均时间是最短。但当序列中有特定规律，比如数组以及有序或者倒序，所有元素都相同，都会导致快速排序出现最坏情况。如果没有最坏情况出现，而且没有稳定性要求，就可以选择快速排序。

        堆排序：需要的空间比快速排序要少，而且不会出现最优和最坏情况，而平均情况运行时间少于快速排序。如果有特殊最坏情况出现，就可以选用堆排序算法。

        归并排序：相比上述两种，归并排序最大的有点是一种稳定的排序，而上述两种是不稳定排序，当要求排序是文档时候，我们就可以选用归并排序算法。

（3）当序列基本有序时候，我们可以选用直接插入和冒泡排序最佳。

（4）假如n很大，但是每个关键字的位数较少而且可以分解时候，可以采用基数排序最佳。

（5）若n较大，则应采用时间复杂度为  O(n{log_{2}}^{n})的排序方法:快速排序、堆排序或归并排序。快速排序被认为是目前基于比较的内部排序方法中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况，这两种排序都是不稳定的。若要求排序稳定且时间复杂度为  O(n{log_{2}}^{n})，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后两两归并。直接插入排序是稳定的，因此改进后的归并排序仍是稳定的。

（6）假如记录本身信息量比较大，为了避免移动元素成本过大，我们可以用链表作为存储结构。

（7）如果只需要对部分排序，就比如一个序列的前几名，我们就可以选用冒泡排序、堆排序、简单选择排序。

总结

       以上就是今天要讲的内容，本文详细介绍了八大基本排序算法的基本思想、代码和每一步的排序过程，以及每种排序的在不同数据规模上的性能分析。最后再讲解了，在不同条件情况下，用哪种排序算法是最优异的。

        排序算法是我们学习其他算法的基础，也是每个在开始学习数据结构小白的噩梦，尤其是快速排序、堆排序和归并排序，这几种较为复杂的排序算法。希望这篇文章能为大家有所帮助，也希望大家对不同的排序算法有更深一步的理解。

参考文献：

[1] 苏小红，孙志刚，陈惠鹏等编著. C语言大学实用教程（第四版）[M]. 北京：电子工业出版社，2017.

[2] 严蔚敏，吴伟民. 数据结构[M]. 北京：清华大学出版社.

[3] 罗勇君， 郭卫斌.算法竞赛_入门到进阶[M].北京：清华大学出版社.

参考资料：

百度百科，小部分图片、视频来源于网络；

作者：

江西师范大学_姜嘉鑫；   江西师范大学_龚俊
 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/164032
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号