九种排序方法辨析

た入场券 2023-10-06 07:19 5阅读 0赞

虽然网上有很多关于排序的文章，但那毕竟是别人。还是决定自己写一写，说不定会发现新的东西。如有错误，请务必指正！

目前为止学过的排序依次包括：冒泡排序，选择排序，插入排序，希尔排序，快速排序，归并排序，堆排序，基数排序，计数排序。

注：在每种排序后都注明该排序方法的稳定性。所谓稳定性就是排序前后两个相同元素的位置是否发生改变。若不变则是稳定排序，改变则是不稳定排序。规定本文中所有排序方式为从小到大排序。

##### 1. 冒泡排序（稳定排序） #####

冒泡排序的思想是比较两个相邻元素，若后面的元素更小则交换两个元素的位置，以此类推。每次迭代过后，当前序列中最大的元素就被置于末尾。  
冒泡排序的时间复杂度是O（n2），最好情况是已经有序，时间复杂度降至O（n）。

代码如下：

Status Bubble_Sort(int a[MAXSIZE+1])
    {
            
    	int i, j, temp;    
    	for (i=1; i<=MAXSIZE; i++)    
    	{
           //注意i, j相差的是一个i        
    		for (j=1; j<=MAXSIZE-i; j++)        
    		{
                    if (a[j] > a[j+1])        
    	    			{
                      
    	      				temp = a[j];
    		             		a[j] = a[j+1];         
    	           			a[j+1] = temp;       
    	                	}
    	         }    
    	 }    
    	 return OK;
    }

##### 2. 选择排序（不稳定排序） #####

选择排序的思想是比较选择当前序列中最大的元素与序列中最后一个元素做交换。特点是要保留最大元素的位置。  
选择排序的时间复杂度是O（n2），最好情况是已经有序，时间复杂度降至O（n）。  
代码如下：

Status Choose_Sort(int a[MAXSIZE+1])
    {
            
    	int i, j, temp;    
    	int minlocation, minnum;//minnum用于存储最小值，minlocation用于存储最小值位置    
    	for (i=1; i<=MAXSIZE; i++)    
    	{
                
    		minlocation = i;        
    		minnum = a[i];        
    		for (j=i; j<=MAXSIZE; j++)        
    		{
                    
    			if (a[j] < minnum)            
    			{
                        
    				minnum = a[j];
    		                minlocation = j;
    		        }		
    		}        
    		temp = a[minlocation];       
     		a[minlocation] = a[i];      
       		a[i] = temp;   
       	}    
        	return OK;
    }

##### 3. 插入排序（稳定排序） #####

插入排序的思想是，把当前元素与之前的每个元素作比较直至出现当前元素大于之前元素的情况。同时在比较过程中，对比较过但不合适的元素右移。在比较前做一个特殊处理：若当前元素小于前一个元素才进入循环作比较，否则说明为当前最大直接放在最后即可。  
插入排序的时间复杂度是O（n2），最好情况是已经有序，时间复杂度降低至O（n）。  
代码如下：

Status Insert_Sort(int a[MAXSIZE+1])
    {
           //实现插入排序，插入方法是从第二个元素往后每次和前面的进行比较。如果前面的比原来的大，则将    
        //大的向后移动，继续比较直到寻找到合适目标为止    
        int i, j;    
        for (i=2; i<=MAXSIZE; ++i)    
        {
                
        	if (a[i] < a[i-1])        
        	{
           //先进行一个判断，如果是最大的就不用继续再比了。减少比较次数            
        		a[0] = a[i];            
        		a[i] = a[i-1];            
        		for (j=i-2; a[j]>a[0]; j--)
        		{
                        
        			a[j+1] = a[j];
        		}  
        		a[j+1] = a[0];        
        	}    
        }    
        return OK;
    }

##### 4. 希尔排序（不稳定排序）： #####

希尔排序是插入排序的改进算法，调整了每次前移的距离。并在每轮迭代的时候将前移距离减少，最终下降至1。特点是需要提前准备好前移序列。  
希尔排序不稳定的原因：一次插入排序是稳定的，但多次使用插入排序可能会改变相同元素的相对位置。所以希尔排序是不稳定排序。  
希尔排序的平均时间复杂度是O（nlogn），不过也取决于前移序列的选择。上网查阅资料后得知，希尔排序的研究还未停止。时间复杂度分布在O（nlogn-n2）。  
代码如下：

Status Shell_Sort1(int a[MAXSIZE+1])
    {
            //Shell_Sort1主要进行轮数的确定，即确定几轮几个间隔    
         //设定为5轮， 分别为，9、7、5、3、1    
    	int intervel[5] = {
        9, 7, 5, 3, 1};    
    	for (int i=0; i<5; i++)    
    	{
                
    		Shell_Sort2(a, intervel[i]);    
    	}
    	return OK;
    }
    Status Shell_Sort2(int a[MAXSIZE+1], int intervel)
    {
            //Shell_Sort主要进行间隔数的调整    
    	int i, j;    
    	for (i=intervel+1; i<=MAXSIZE; i++)    
    	{
                
    		if (a[i] < a[i-intervel])        
    		{
                    
    			a[0] = a[i];            
    			for (j = i-intervel; j>0 && a[j]>a[0]; j -= intervel)            
    			{
                        
    				a[j+intervel] = a[j];
    			}            
    			a[j+intervel] = a[0];        
    		}    
    	}    
    	return OK;
    }

##### 5. 快速排序（不稳定排序）： #####

快速排序的思想是递归选取一个中心点（常选取中心点是序列的第一个元素），将小于中心的值移动到左边，将大于中心的值移动到右边。  
快速排序的平均时间复杂度是O（nlogn），影响时间复杂度的是中心点的选取，即左右两边的比重。最坏情况是选取一边没有元素的中心点，这样时间复杂度下降至O（n2）。最优情况是选取得中心点恰好是序列的中心点，时间复杂度为O（nlogn）。可证当选取中心点出现左边1个，右边n个的情况时间复杂度也为O（nlogn）。说明快速排序的坏情况是间隔出现的有两种方式可以解决这个问题：1.不选取序列第一个元素，改为随机选取。2.打乱当前序列。经过验证第二种方式的实际效果更好。可以使用随机化算法，先将序列打乱顺序再使用快速排序。这样时间复杂度可稳定在O（nlogn）。  
代码如下:

Status Quick_Sort(int a[MAXSIZE+1], int low, int high)
    {
            
    	int tag;    
    	if (low < high)    
    	{
                
    		tag = Tag(a, low, high);
    		Quick_Sort(a, low, tag-1);
    		Quick_Sort(a, tag+1, high);  
    	}
        	return OK;
    }
    int Tag(int a[MAXSIZE+1], int low, int high)
    {
            //tag取最左侧元素，作为标记位，会被移到中间去。左边会比tag小，右边会比tag大   
    	 int tag;    
    	 tag = a[low];    
    	 while (low < high)    
    	 {
                
    	 	while (low < high && a[high] >= tag)
    	         {
           //此处必须包含等于，等于的情况下也是应该移动的，如果等于发生交换那么后序无法进行       
    	              high--;        
    	         }        
    	         a[low] = a[high];        
    	         while (low < high && a[low] <= tag)
    	         {
           //在移动过程中要时刻判断low和high的关系，可能在Low++后已经超过，但依旧循环            
    	         	low++;        
    	         }        
    	         a[high] = a[low];    
    	  }    
    	  a[low] = tag;    
    	  return low;
    }

##### 6. 归并排序（稳定排序）： #####

归并排序的思想是将序列递归分治，分解至最小模块后。不断归并有序序列，最终得到整体有序。  
归并排序是稳定排序的原因：保持归并排序的稳定性可做特殊处理，保证两组有序序列merge时按照前后两个序列的先后顺序插入即可维持稳定。  
归并排序的时间复杂度是O（nlogn）。最好最坏的情况都是O（nlogn）。因为归并排序层数都是logn向下取整。整体merge都是n。特点是比较稳定，不受输入序列顺序的影响。但需要O（n）的空间复杂度。  
代码如下：

Status  Merge_Insert(int *temp_merge, int *merge, int s, int m, int t)
    {
           //具体归并的过程类似于，将两个链表在遍历一次的情况下合成到另一个链表上去，一次移动一位    
    	int i, j, k;    
    	for (i=s, j=m+1,k=s; i<=m&&j<=t; ++k)    
    	{
                
    		if (temp_merge[i] < temp_merge[j])
    		{
                    
    			merge[k] = temp_merge[i++];
    		}        
    		else        
    		{
                    
    			merge[k] = temp_merge[j++];
    		}    
    	}    
    	//进行补位，若哪半边还有剩余的直接依次补齐    
    	if (i > m)    
    	{
                
    		while (j <= t)        
    		{
                    
    			merge[k++] = temp_merge[j++];
    		}    
    	}    
    	if (j > t)    
    	{
                
    		while (i <= m)        
    		{
                    
    			merge[k++] = temp_merge[i++];
    		}    
    	}
    }
    Status  Merge_Sort(int a[MAXSIZE+1], int *merge, int s, int t)
    {
            
    	if (s == t)    
    	{
           //先进行一次判断，若只有一个元素则直接输出即可 
    	       merge[s] = a[s];    
    	}    
    	else    
    	{
                
    		int m;        
    		int temp_merge[MAXSIZE+1];        
    		m = (s + t)/2;        
    		Merge_Sort(a, temp_merge, s, m);
    		//将temp_merge的前半部分归并有序，并将temp_merge的后半部分归并有序        
    		Merge_Sort(a, temp_merge, m+1, t);
    		Merge_Insert(temp_merge, merge, s, m, t);
    		//最后将两部分有序的统一归并到merge中    
    	}    
    	return OK;
    }

##### 7. 堆排序（不稳定排序）： #####

堆排序思想使用堆的数据结构（前面有过专门的文章介绍堆，有需要的朋友可以去看看）。使用最小/大堆，每次将堆顶的元素放到合适的位置。堆排序共有两步：将堆顶元素放于合适位置->重新将堆调整至最小/大堆。  
堆排序的时间复杂度是O（nlogn），堆排序的过程包括构造堆和取出两步，最好最坏时间复杂度都是O（nlogn）。两者相差是常数级别。  
代码如下：

Status Heap_Sort(int a[MAXSIZE+1])
    {
            
    	int temp;    
    	//先将普通数组调成大顶堆    
    	for (int i=MAXSIZE/2; i>0 ; i--)    
    	{
                
    		Heap_Insert(a, i, MAXSIZE);    
    	}    
    	for (int i=MAXSIZE; i>1; i--)    
    	{
           //每次重新调整成大顶堆，并且将第一个元素移到最后 
    	       temp = a[1];        
    	       a[1] = a[i];        
    	       a[i] = temp;        
    	       Heap_Insert(a, 1, i-1);    
    	}    
    	return OK;
    }
    Status Heap_Insert(int a[MAXSIZE+1], int s, int m)
    {
            
    	int temp = a[s];//最开始第一个元素不满足条件，其余满足。将该元素暂存    
    	for (int j=2*s; j<=m; j *= 2)
    	//j是s的子节点，必须是s的二倍    
    	{
           //选择左右子树大的那一个        
    		if (j<m && a[j] < a[j+1])        
    		{
                    
    			j++;        
    		}        
    		if (temp >= a[j])        
    		{
           //当标记元素比当前元素大（即比当前元素的兄弟都大），即可放入双亲节点
    			break;        
    		}        
    		a[s] = a[j];//s就是j的双亲，每次j移动，s跟上        
    		s = j;    
    	}    
    	a[s] = temp;    
    	return OK;
    }

##### 8. 基数排序（稳定排序） #####

基数排序的思想是从最低位开始排序，依次向前移动且不改变相同值的相对位置。可以使用链表来实现，留出10个（0，1，。。。9）空间按照最低位放入空间再连接完成一次迭代。  
基数排序的时间复杂度是O（n）。之前很困惑为什么基数排序的时间复杂度比快速排序更低，但是却没有快速排序常用。经过查找资料得出原因：基数排序的时间复杂度实际是O（kn）。且常数K的值往往很大，而快速排序的常数值很小。并且基数排序也是相对比较消耗空间的。大多数应用条件下使用快速排序更佳。  
代码如下：

Status Radix_Sort(int a[MAXSIZE+1])
    {
           //基数排序，每轮即从个位向前进行排序。使用队列的存储形式。      
        //建立一个总的队列元素个数为MAXSIZE+2，使用顺式结构循环队列 
        //同时建立十个（0-9）队列数组，编号即代表位数。当从总队列遍历时，进入对应的队列数组。全部完成后    
        //清空总队列，将各个队列数组元素依次进入总队列    
        int temp;//temp用来存储当前对应的一位数字    
        int afterpow;    
        Queue Ten[10];    
        for (int i=0; i<10; i++)    
        {
                
        	InitQueue(Ten[i]);    
        }    
        for (int i=0; i<5; i++)    
        {
           //本次样本中，没有超过五位数的，进行五轮就可以 
               for (int j=1; j<=MAXSIZE+1; j++)        
               {
                    
               	afterpow = pow(10, i);            
               	temp = (a[j] / afterpow) % 10;
               	EnQueue(Ten[temp], a[j]);        
               }        
        	for (int j=1; j<=MAXSIZE+1; )        
        	{
                    
        		for (int i=0; i<10; i++)            
        		{
                        
        			while (Ten[i].rear != Ten[i].front)
        			{
                            
        				DeQueue(Ten[i], temp);//此处temp起转移作用                    
        				a[j++] = temp;                
        			}            
        		}        
        	}        
        	for (int i=0; i<10; i++)        
        	{
           //每次完成之后，将数组队列清空  
                  	Ten[i].front = 0;            
                  	Ten[i].rear = 0;        
        	}    
       }    
       return OK;
    }

##### 9. 计数排序（不稳定排序）： #####

计数排序的思想是，统计最小元素到最大元素之间每个序列中每个出现的元素个数并制成表。表中包括每个元素开始的位置，是前一项的起始顶点加前一项的个数得到。再遍历一遍原序列，按照表中位置直接插入指定位置。并动态更新表。  
计数排序的时间复杂度是O（n），不过计数排序只适用于最大元素不是特别大的情况，原因在于需要保留最小元素到最大元素中每一个元素的个数，有的元素个数为0但仍要占空间。

排序方法的选择更多的是依靠实际序列的特点和规模。对于规模变化大的序列排序，可以使用混合的方法，只要计算出临界值即可。

排序真是编程中最基本的操作之一了，不过这么多方法完全弄懂也是有一定难度的。老师说过：对于排序算法要考虑N无穷的情况，切不可贪图方便只使用O（n2）的方法啦！

**因本文作者水平有限，如有问题，请各位高手在下方评论区指正，谢谢！**