devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

十大排序算法的实现以及各自的优缺点、适用情况_十大排序算法使用时怎么选择

作者：小丑西瓜9 | 2024-04-12 17:32:27

赞

踩

十大排序算法使用时怎么选择

学习排序算法的体会：

也许在一些题目中我们可以轻松地用STL库中的函数或者容器实现我们排序的需求，但在实际问题中，数据往往会很大要考虑时间空间复杂度，而排序的因素也可能很多，不仅仅是STL库能够解决的，所以我们在排序时不能仅仅考虑写着方便，还应该考虑程序的效率和内存问题。我们有必要熟悉各种排序算法的实现以及他们的优缺点。稳定性和适用情况会在最后总结。
在说这些排序算法之前，我们先来看看真香的sort库函数究竟是由什么算法实现的：
其实稍微一想也知道不可能只用一种排序算法实现，毕竟没有完美的排序算法，只有适合的排序算法，因为有很多情况要考虑，所以掌握不同算法的适用情况也很重要。
（1）首先声明一下并非所有容器都使用（能用、适用）sort算法，既然问的是STL的sort算法实现，那么先确认一个问题，哪些STL容器需要用到sort算法？首先，关系型容器（map、set、multimap、multiset）拥有自动排序功能，因为底层采用RB-Tree，所以不需要用到sort算法。其次，序列式容器中的stack、queue和priority-queue都有特定的出入口，不允许用户对元素排序。剩下的vector、deque，适用sort算法。
（2）实现逻辑
STL的sort算法，数据量大时采用QuickSort快排算法，分段归并排序。一旦分段后的数据量小于某个门槛（16），为避免QuickSort快排的递归调用带来过大的额外负荷，就改用Insertion Sort插入排序。如果递归层次过深，还会改用HeapSort堆排序。
从sort的实现逻辑我们可以看出不同情况对应使用不同的排序算法，甚至还会结合使用，而有时候要考虑的因素还不只这些。

1.选择排序：

（1）简单选择排序：

简单选择排序其实就是每次都选出未处理的元素中最小或最大的元素与未处理部分的第一个元素交换，直到有序。 显然，要想知道是否到达有序，总要进行完所有的比较，也就是无论这个数组的有序性怎样，都要比较n*(n-1)/2次，时间复杂度为O(n2) 。

void swap(int & a,int & b)
{
	int tmp=a;
	a=b;
	b=tmp;
}
void SimpleChooseSort(int A[],int N)//序列A及元素个数
{
	for(int i=0;i<N;i++){
		int min=i;
		for(int j=i+1;j<N;j++){//寻找i后面的最小元素下标 
			if(A[min]>A[j])
				min=j;
		}
		if(min==i) continue;//如果i后面的元素都大于等于i，那么 min还是i，就不用了交换了 
		swap(A[i],A[min]); //交换 
	}	
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

（2）堆排序

思想：
顾名思义，堆排序就是利用堆（优先队列）对序列进行排序，因为优先级最高的元素永远在堆顶，所以我们可以一直取堆顶元素然后重新生成堆直到有序。这个过程其实就是根据上面的冒泡排序，把找最优元素的任务交给了堆 来降低时间复杂度。
细节：
我们可以额外开一个数组存每次取出的堆顶元素，然后重新生成堆，但是这样需要额外的空间O（N），会提升空间复杂度。因此我们要用一个不需要额外开辟空间的做法：每次循环让堆顶元素与最后一个叶子结点交换，然后对除去最后一个叶子节点（也就是之前的堆顶元素）的新序列重新生成堆（其实只是对交换后的堆顶元素进行下滤操作）,所以每次交换后堆中的元素就会少一个，就是取出堆顶元素，以此类推，可以实现由最大堆生成递增序列，由最小堆生成递减序列 。

//用最大堆生成递增序列举例 
//在这里我们假定堆用数组存放而不是链表，故根节点的下标是0，最后一个叶子节点下标就是N-1。而用链表实现的堆是从1开始的（涉及到下滤函数的不同）
void PercDown(int A[],int start,int N)//存放堆的数组A、堆顶下标（0）、当前堆元素个数 
{
	int child,parent;
	int X=A[start];
	for(parent=start;(parent*2+1)<N;parent=child){
		child=parent*2+1;
		if(child!=N-1&&A[child]<A[child+1]) //child!=N-1就意味着不会对A[N]进行比较，也就相当于除去了之前的堆顶元素
			child=child+1;
		if(A[child]>A[parent])//如果子节点大于父节点
			A[parent]=A[child];
		else 
			break;
	}
	A[parent]=X;
}
void swap(int & a,int & b)
{
	int tmp=a;
	a=b;
	b=tmp;
}
void HeapSort(int A[],int N)//堆排序
{ 
	for(int i=N/2-1;i>=0;i--)//建立最大堆 
		PercDown(A,i,N);
	for(int i=N-1;i>0;i--){
		swap(A[0],A[i]);// 让堆顶元素与最后一个叶子结点交换
		PercDown(A,0,i); //对除去最后一个叶子节点（也就是之前的堆顶元素）的新序列重新生成堆
	}	
} 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

优缺点：
可以看出下滤函数PercDown的时间复杂度是O（logN），而堆排序函数中对所有节点遍历进行下滤，故堆排序的时间复杂度为O（NlogN），额外空间复杂度为O（1）。当我们的问题是要从大量的N个数据中找最大/最小的k个元素时，用堆排序是比较快的。

2.插入排序：

（1）直接插入排序：

思想：
其实就是把待排序列分为已排好序和未排序的两个序列，每次从为排序的序列中取一个元素插入到已经排好序的序列中并进行交换实现有序，直到未排序的序列中没有元素。
对于每次插入：
其实就是从已排好序的序列的最后一个元素开始比较，如果插入的元素优先级低于比较的元素，就交换二者的顺序，直到插入元素找到合适位置。

void SimpleInsertSort(int A[],int N)
{
	int i,j;
	for(i=1;i<N;i++){//要插入的元素下标i（已排好的序列一开始肯定得有第一个元素0啊，故插入的元素从1开始）
		int tmp=A[i];//因为不是用swap交换，所以要先存上要插入的元素
		for(j=i;j>0&&A[j-1]>tmp;j--)//从已排好序的序列的最后一个元素开始比较
			A[j]=A[j-1];
		A[j]=tmp;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

优缺点：
用了两个嵌套的循环，所以时间复杂度为O(n2) 。最坏情况下（逆序）要进行n2次比较，而最好情况（本身符合有序）会在第二个循环判断一次就跳出来，故要比较n次。

（2）希尔排序：

思想：
简单的插入排序每次只比较两个元素只能交换两个错位的元素，所以效率很低，希尔排序在此基础上通每次比较（并交换）相隔一定距离的元素，从而提高排序效率。
做法：
将待排序列按一定间隔分成若干序列，分别进行插入排序（分别的意思是对应，不是在每个序列中进行插入排序），间隔从大到小直到间隔为1，也就是就剩两两之间没有排序。这么说很难体会，我们来看一个例子：
对下面这个序列进行希尔排序
在这里插入图片描述
首先我们以间隔为5来举例：
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
这样我们就完成了5-间隔的排序，然后我们减小间隔，继续排序，注意：每次减小间隔后再排序是对上一个间隔得到的序列进行排序，不是对原序列！！！ 也就是下图第二项内容说明的问题。
在这里插入图片描述
增量序列其实就是存放间隔的序列，显然是递减的。我们来看一个坏例子：
对下面这个序列进行希尔排序：
在这里插入图片描述
为什么直到1间隔序列才发生变化呢？因为增量元素不互质，使得小增量根本不起作用，所以增量元素的选择也有文章。。。。。。。来看看大神的增量序列：
优缺点：
在这里插入图片描述
avg是平均时间复杂度，worst是最坏情况的时间复杂度。猜想就是不确定。而时间复杂度还是取决于增量序列选择的好坏，选择的好可以<N2。
如果数量级在几万，我们结合Sedgewick增量序列使用希尔排序还是很划算的。下面是相关代码：

void ShellSort( int A[], int N )
{ /* 希尔排序 - 用Sedgewick增量序列 */
     int Si, D, P, i;
     /* 这里只列出一小部分增量 */
     int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};      
     for ( Si=0; Sedgewick[Si]>=N; Si++ ) 
     	; /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */
     for ( D=Sedgewick[Si]; D>0; D=Sedgewick[++Si] ){
         for ( P=D; P<N; P++ ) { /* 插入排序*/
             int Tmp = A[P];
             for ( i=P; i>=D && A[i-D]>Tmp; i-=D )
                 A[i] = A[i-D];
             A[i] = Tmp;
         }
     }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

3.交换排序 :

（1）冒泡排序：

思想：
进行N-1次循环，在第k次循环中从0开始到N-k-1每次比较相邻的两个元素，看是否需要交换。
细节：
我们可以增加一个标记flag用于查看每次循环是否交换了元素，如果没有，就说明序列已经有序了，这样就不用进行完所有循环了（除非逆序）
代码：
在这里插入图片描述
平均时间复杂度是O（N2）。

（2）快速排序：

思想：
和插入排序时一样，冒泡排序每次只比较相邻的两个元素，所以效率也会很低，如果我们每次取未排序的序列中的一个元素（称为主元）把未排序的序列分成两个子序列，其中一个全部小于主元，另一个全部大于主元，然后递归地进行这样的排序。
细节：
（1）本质：其实就是用分治法把问题的规模变小来改善时间复杂度。
（2）如何选主元？（也是对快速排序时间复杂度的分析）
如果我们随便选，显然不合适，如果我们每次选得恰好是靠边上的元素，那递归层次就会很深，最坏情况就要和冒泡排序一样了（O（N2）），而如果我们恰好每次都选的中间大小的元素，那么递归就很平均（接近二分），最好情况可以让递归层次是log2N ，每次递归的比较都是O（N）次，所以最好时时间复杂度为O（Nlog2N），相对于其他内部排序，快速排序平均效率是最高的。
我们取头中尾三个元素的中间值作为主元来避免取到靠边元素的尴尬情况：
要保证A[Left] <= A[Center] <= A[Right]

int Median3( ElementType A[], int Left, int Right )//选主元
{ 
    int Center = (Left+Right) / 2;
    if ( A[Left] > A[Center] )
        Swap( A[Left], A[Center] );
    if ( A[Left] > A[Right] )
        Swap( A[Left], A[Right] );
    if ( A[Center] > A[Right] )
        Swap( A[Center], A[Right] );
    /* 此时A[Left] <= A[Center] <= A[Right] */
    Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
    /* 只需要考虑A[Left+1] … A[Right-2] */
    return  A[Right-1];  /* 返回基准Pivot */
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

把主元放在Right-1的位置上我们就不用了管右边的序列了，更加方便。
（3）子集的划分：
其实就是看主元选的好不好（自己举个例子画图看代码体会吧）

void Qsort( int A[], int Left, int Right )
{ /* 核心递归函数 */ 
     int Pivot, Cutoff, Low, High;      
     if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多，进入快排 */
          Pivot = Median3( A, Left, Right ); /* 选主元 */ 
          Low = Left; High = Right-1;
          //子集划分：自己举例子画图体会
          while (1) { /*将序列中比主元小的移到基准左边，大的移到右边*/
               while ( A[++Low] < Pivot ) ;
               while ( A[--High] > Pivot ) ;
               if ( Low < High ) Swap( &A[Low], &A[High] );
               else break;
          }
          //注意此时low在中间位置，但Right-1没有变，此时再把在Right-1的center放在low的位置上，low放在边上
          Swap( A[Low], A[Right-1] );   /* 将基准换到正确的位置 */ 
          Qsort( A, Left, Low-1 );    /* 递归解决左边 */ 
          Qsort( A, Low+1, Right );   /* 递归解决右边 */  
     }
     else SimpleInsertSort( A+Left, Right-Left+1 ); /* 元素太少，用简单排序 */ 
}
 
void QuickSort( int A[], int N )
{ /* 统一接口 */
     Qsort( A, 0, N-1 );
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

优缺点：
当比较的数据比较少时，用递归显然是不划算的，所以我们用Cutoff来控制数据数量级，如果数据少就用插入排序。时间复杂度已经在前面分析过了。而因为要递归，根据前面的分析，最好递归层次是log2N，这样只需要O（log2N）的栈空间，但是如果子集划分不够平均

4.归并排序：

思路：
顾名思义，归并排序就是根据归并操作的原理，把序列中的N个元素看成N个有序的子序列，每次合并两个相邻有序子序列，直到剩下一个长度为N的 序列，即为原序列排好序后的有序序列。我们来看过程图：
在这里插入图片描述
细节：
归并操作的实现：首先要有额外的储存空间存放每一步归并得到的序列，其次每次归并都让“两个指针”分别指向两个子序列的头，依次比较，每次把优先级高的放入额外的储存空间中，如果有一个序列为空，就把另一个序列剩余的元素依次放入，直到两个子序列为空。最后我们再把额外的储存空间的序列传回原序列对应的部分。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
。。。。。。。。。。。。直到两个子序列为空
下面是归并操作的代码：

void Merge(int A[],int Tmp[],int LeftStart,int RightStart,int RightEnd)//假定从小到大排序
{//待排序列A、Tmp就是那个额外空间、左边子序列起始点、右边子序列起始点、右边子序列终点
	int LeftEnd=RightStart-1;//左边子序列终点
	int Num=RightEnd-LeftStart+1;//两个子序列的元素总数
	int tmp=LeftStart;//结果序列（Tmp）的起始位置
	while(LeftStart<=LeftEnd&&RightStart<=RightEnd){
		if(A[LeftStart]<=A[RightStart]) Tmp[tmp++]=A[LeftStart++];
		else Tmp[tmp++]=A[RightStart++];
	}
	//如果有一个序列为空，就把另一个序列剩余的元素依次放入，直到两个子序列为空
	while(LeftStart<=LeftEnd) Tmp[tmp++]=A[LeftStart++];
	while(RightStart<=RightEnd) Tmp[tmp++]=A[RightStart++];
	//把结果序列传回原序列对应的部分
	for(int i=0;i<Num;i++,RightEnd--)
		A[RightEnd]=Tmp[RightEnd];
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

归并排序的代码：

void MSort(int A[],int Tmp[],int LeftStart,int RightEnd)
{
	int center;
	if(LeftStart<RightEnd){
	 	center=(LeftStart+RightEnd)/2;
		MSort(A,Tmp,LeftStart,center);//递归解决左边
		MSort(A,Tmp,center+1,RightEnd);//递归解决右边
		Merge(A,Tmp,LeftStart,center+1,RightEnd);//合并两端有序序列
	}
}
//统一接口：
void MergeSort(int A[],int N)
{
	int *Tmp=new int[N];
	if(Tmp!=NULL){
		MSort(A,Tmp,0,N-1);
		delete [] Tmp;
	}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

非递归的写法（循环实现）：

/* length = 当前有序子列的长度*/
void Merge_pass( int A[], int TmpA[], int N, int length )
{ /* 两两归并相邻有序子列 */
     int i, j; 
     for ( i=0; i <= N-2*length; i += 2*length )
         Merge( A, TmpA, i, i+length, i+2*length-1 );
     if ( i+length < N ) /* 归并最后2个子列*/
         Merge( A, TmpA, i, i+length, N-1);
     else /* 最后只剩1个子列*/
         for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}
 
void Merge_Sort( int A[], int N )
{ 
     int length; 
     int *TmpA;      
     length = 1; /* 初始化子序列长度*/
     TmpA = malloc( N * sizeof( ElementType ) );
     if ( TmpA != NULL ) {
          while( length < N ) {
              Merge_pass( A, TmpA, N, length );
              length *= 2;
              Merge_pass( TmpA, A, N, length );
              length *= 2;
          }
          free( TmpA );
     }
     else printf( "空间不足" );
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

优缺点：
从最前面的流程图我们可以看出每一趟归并操作（流程图的每一行）都进行O（N）比较，而一共将进行O（log2N）次趟归并，所以整个归并排序的时间复杂度是O（Nlog2N），而空间复杂度因为我们额外开了与原序列大小一致的空间，所以整个归并排序的空间复杂度是O（N）。但是算法中需要来回复制结果数组和原序列，很耗时，所以归并排序一般用于外排序
前面的排序都是基于比较大小的来决定元素位置，而有一个结论是如果只通过比较元素大小来决定元素顺序那么即使使用最快的算法，最坏时间复杂度的下界也到达O（NlogN）。

5.表排序：

思想：
当我们要排序的对象不是简简单单的一个数列，而是一个庞大结构的序列，比如几本书，我们不可能把书的内容移来移去，我们可以另外开一个“指针“”数组，代表排序对象的下标，这样我们不用移动原始数据，只需要移动指向他们位置的指针。来看一个例子：
在这里插入图片描述
上面是初始化一个table，然后我们根据关键字选一种排序方法通过交换table来实现排序：
在这里插入图片描述
注意理解时table值代表就是该位置应给放的元素在原序列的下标。
所以如果我们要顺序输出排好序的序列，只需要：
在这里插入图片描述
优缺点：
显然我们只遍历了一遍关键字就确定了table，所以时间复杂度是线性的O（N）。
但是如果非要我们在物理上对这几本书进行排序，我们该怎么办？
我们先来看得到的结果table：
在这里插入图片描述
从头看，f的table是3，他指向a，a的table是1，它指向d，d的table是5，它指向b，b的table为0，又指回了f；再来看c，c的table是2指向它自己，结束；再来看g，g的table是7，指向e，e的table是6，指向h，h的table是4，又指回了g。显然，这些书形成了三个独立的环，在环内移动这些书的位置即可。
这就是N个数字的排列是由若干个独立的环组成。 所以只需要先取出第一本书，根据table移动对应的书，直到第一本书所在环结束（while(table[i]==i)），把第一本书移入结束的位置即可。
优缺点：
最好情况（本身有序）只需要遍历一次即可，最坏情况（逆序）就会存在N/2个环，每个环两个元素需要移动三次（把其中一个取出来也是移动），这样就需要移动3*N/2次，总之，我们还是能够在线性时间复杂度O（N）内完成这个排序。

6.基数排序：

（1）桶排序：

思路：
如果已知N个关键字的取值范围是0~M-1，而N远大于M，我们就可以把每个关键字的可能取值设为一个桶，把N个关键字按照他们的取值依次放入0-M-1这M个桶中，按桶的顺序收集一遍就自然有序了。
例：
在这里插入图片描述
优缺点：
这种情况下我们得到有序序列只需要遍历N个元素在遍历M个桶就可以了，所以时间复杂度为O(N+M)。

（2）基数排序：单关键字的基数分解（多关键字排序）

思想：
是桶排序的延伸，排序时不止考虑单个关键字。
其实就是单纯用一种关键字来排序效率低，我们可以对于在一种分类后子序列还能分为许多种子序列（也就是多层关键字）的情况用基数排序，也就是将单个整形关键字按某种基数分解为多关键字，再进行排序。
来看下面的例子理解：
现在情况恰好与上一种相反，是M远大于N，也就是序列元素的取值范围远大于序列元素的个数。 如果M是100000而N为10，我们不可能建M个桶来存N个元素。
思想：
既然M（取值范围大），我们不妨让位数来做关键字，从个位一直到M数量级的位数按桶排序的方式把N个元素分别放入基数个桶中，这样就有M数量级的位数个关键字。这就是次位优先排序（Least Significant Digit）。所谓基数就是指每一位数的范围（10就是0-9,8就是0-7），其实和进制类似，十进制的数每一位数只能是0-9，八进制的数每一位数只能是0-7，基数的选择会影响基数排序的效率。
在这里插入图片描述
所谓次位优先就是从个位数开始到十位、百位。。。。

/* 基数排序 - 次位优先 */
 
/* 假设元素最多有MaxDigit个关键字（位数，从个位到MaxDigit位），基数全是同样的Radix */
#define MaxDigit 4//数量级为4
#define Radix 10//0,1，2，3，4，5,6，7,8，9
 
/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node {
    int key;
    PtrToNode next;
};
 
/* 桶头结点 */
struct HeadNode {
    PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];
  
int GetDigit ( int X, int D )/* 获得当前元素X的当前位D的数字 */
{ /* 默认次位D=1, 主位D<=MaxDigit */
    int d, i;
     
    for (i=1; i<=D; i++) {
        d = X % Radix;
        X /= Radix;
    }
    return d;
}
 
void LSDRadixSort( ElementType A[], int N )
{ /* 基数排序 - 次位优先 */
     int D, Di, i;
     Bucket B;
     PtrToNode tmp, p, List = NULL; 
      
     for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */
         B[i].head = B[i].tail = NULL;
     for (i=0; i<N; i++) { /* 将原始序列逆序存入初始链表List */
         tmp = (PtrToNode)malloc(sizeof(struct Node));
         tmp->key = A[i];
         tmp->next = List;
         List = tmp;
     }
     /* 下面开始排序 */ 
     for (D=1; D<=MaxDigit; D++) { /* 对数据的每一位循环处理 */
         /* 下面是分配的过程 */
         p = List;
         while (p) {
             Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
             /* 从List中摘除 */
             tmp = p; 
             p = p->next;
             /* 插入B[Di]号桶尾 */
             tmp->next = NULL;
             if (B[Di].head == NULL)
                 B[Di].head = B[Di].tail = tmp;
             else {
                 B[Di].tail->next = tmp;
                 B[Di].tail = tmp;
             }
         }
         /* 下面是收集的过程 */
         List = NULL; 
         for (Di=Radix-1; Di>=0; Di--) { /* 将每个桶的元素顺序收集入List */
             if (B[Di].head) { /* 如果桶不为空 */
                 /* 整桶插入List表头 */
                 B[Di].tail->next = List;
                 List = B[Di].head;
                 B[Di].head = B[Di].tail = NULL; /* 清空桶 */
             }
         }
     }
     /* 将List倒入A[]并释放空间 */
     for (i=0; i<N; i++) {
        tmp = List;
        List = List->next;
        A[i] = tmp->key;
        free(tmp);
     } 
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81

有次位优先就有主位优先：
比如一副扑克牌可以用两种关键字来排序，先按照黑红梅方的花色顺序把一副扑克牌分为四组，再对四组都用1，2，3，4.。。。。。。就J，Q，K，A的顺序排序。
其本质就是先用主位关键字 （花色）建四个桶，就是主位优先（Most Significant Digit），再在每个桶内用次位关键字（面值）建13个桶。这样就自然有序了。

/* 基数排序 - 主位优先 */
 
/* 假设元素最多有MaxDigit个关键字，基数全是同样的Radix */
 
#define MaxDigit 4
#define Radix 10
 
/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node{
    int key;
    PtrToNode next;
};
 
/* 桶头结点 */
struct HeadNode {
    PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];
  
int GetDigit ( int X, int D )
{ /* 默认次位D=1, 主位D<=MaxDigit */
    int d, i;
     
    for (i=1; i<=D; i++) {
        d = X%Radix;
        X /= Radix;
    }
    return d;
}
 
void MSD( ElementType A[], int L, int R, int D )
{ /* 核心递归函数: 对A[L]...A[R]的第D位数进行排序 */
     int Di, i, j;
     Bucket B;
     PtrToNode tmp, p, List = NULL; 
     if (D==0) return; /* 递归终止条件 */
      
     for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */
         B[i].head = B[i].tail = NULL;
     for (i=L; i<=R; i++) { /* 将原始序列逆序存入初始链表List */
         tmp = (PtrToNode)malloc(sizeof(struct Node));
         tmp->key = A[i];
         tmp->next = List;
         List = tmp;
     }
     /* 下面是分配的过程 */
     p = List;
     while (p) {
         Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
         /* 从List中摘除 */
         tmp = p; p = p->next;
         /* 插入B[Di]号桶 */
         if (B[Di].head == NULL) B[Di].tail = tmp;
         tmp->next = B[Di].head;
         B[Di].head = tmp;
     }
     /* 下面是收集的过程 */
     i = j = L; /* i, j记录当前要处理的A[]的左右端下标 */
     for (Di=0; Di<Radix; Di++) { /* 对于每个桶 */
         if (B[Di].head) { /* 将非空的桶整桶倒入A[], 递归排序 */
             p = B[Di].head;
             while (p) {
                 tmp = p;
                 p = p->next;
                 A[j++] = tmp->key;
                 free(tmp);
             }
             /* 递归对该桶数据排序, 位数减1 */
             MSD(A, i, j-1, D-1);
             i = j; /* 为下一个桶对应的A[]左端 */
         } 
     } 
}
 
void MSDRadixSort( ElementType A[], int N )
{ /* 统一接口 */
    MSD(A, 0, N-1, MaxDigit); 
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79

优缺点：
基数排序用链表实现可以不用进行物理上的移动，不过这样我们需要额外的O(N)的空间。
对N个关键字用R个桶进行基数排序时，其时间复杂度为O（D(N+R)），D为分配的躺数（其实也就是完成排序的数量级的位数），显然基数R与效率密切相关，而对基数的选择要综合考虑待排序列的规模和关键字的取值范围。

总体的评价以及应用：

先来看几个问题：
（1）排序算法的性能取决于什么？
取决于算法中比较和交换的次数以及是否需要额外的空间用于存放临时值（如果数据很大会遇上空间不够的问题就会出错）。
（2）什么样的排序算法是稳定的呢？
稳定其实就是在比较过程中，关键字（数组元素的值）相同的两个元素不会发生交换。而有时候我们比较的关键字不是那些对象的唯一属性，也许比较的关键字相同但是对象的其他属性不同，如果这时交换了关键字（数组元素的值）相同的两个对象，那么对象的其他属性也会跟着变化，那就不好了。回到前面的算法去一一看看哪些算法稳定哪些不稳定。（判断的方法其实就是如果排序是在相邻两元素间进行，就不可能发生关键字（数组元素的值）相同的两个元素交换的事情，而如果是跳跃（间隔）的排序，显然算法并不知道会不会有相同的关键字在当前元素的前面或后面，它就会交换）
下面给出所有排序算法的复杂度及稳定性：
在这里插入图片描述
总之，不存在最好的排序算法，我们需要根据上面这些性能选择合适的方法，甚至是结合使用。下面是我从一篇腾讯新闻里看到的：
（1）当数据规模较小时候，可以使用简单的直接插入排序或者直接选择排序。
（2）当文件的初态已经基本有序，可以用直接插入排序和冒泡排序。
（3）当数据规模较大时，应用速度最快的排序算法，可以考虑使用快速排序。当记录随机分布的时候，快速排序平均时间最短，但是会出现最坏的情况，这个时候的时间复杂度是O(n^2)，且递归深度为n,所需的占空间为O(n)。
（4）堆排序不会出现快排那样最坏情况，且堆排序所需的辅助空间比快排要少，但是这两种算法都不是稳定的，要求排序时是稳定的，可以考虑用归并排序。
（5）归并排序可以用于内部排序，也可以使用于外部排序。在外部排序时，通常采用多路归并，并且通过解决长顺串的合并，加上长的初始串，提高主机与外设并行能力等，以减少访问外存额外次数，提高外排的效率。
（6）特殊的桶排序、基数排序都是稳定且高效的排序算法，但有一定的局限性：
1、关键字可分解。
2、记录的关键字位数较少，如果密集更好
3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。
上面这些看看也就行了，别人说的再好，也不如自己去找一些数据试试哪种情况哪种算法最快。

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

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

  

闽ICP备14008679号