第九节：排序（上）
9.1 概述
对于之后应用到的一些说明：
（1）void X_Sort(ElementType A[], int N) X为排序名称。
①大多数情况下，为了简单起见，讨论从小到大的整数排序。
②默认N为正整数。
③只讨论基于比较的排序（>=<都是有定义的）。
④只讨论内部排序（一次性可以写入内存，然后只在内存里面的数据排序）。
⑤稳定性：任意两个相等的数据，排序前后的相对位置不发生改变。
没有一种排序是任何情况下都表现最好的！！！
9.2 简单排序算法
9.2.1 冒泡排序
在一次排序完成后，最后面的一定是最大的，第二次排序的时候只需要对前N-1个排序即可，然后N-2……一直到最后完成。
冒泡排序的伪码描述如下：
void Bubble_Sort(ElementType A[], int N)
{
for(P=N-1;P>=0;P--)
{
flag = 0;
for(i=0;i<P;i++)
{/*一趟冒泡*/
if(A[i]>A[i+1])
{
Swap(A[i],A[i+1);]
flag = 1;/*标志发生了交换*/
}
}
if(flag==0)
break;/*全程无交换，已经排好*/
}
}
最好情况：顺序T=O(N)；最差情况：逆序T=O(N2)
这个算法具有稳定性！
9.2.2 插入排序
类似于打扑克的时候拿到牌之后进行排序 。
源代码：
void InsertionSort( ElementType A[], int N )
{ /* 插入排序 */
int P, i;
ElementType Tmp;
for ( P=1; P<N; P++ ) {
Tmp = A[P]; /* 取出未排序序列中的第一个元素*/
for ( i=P; i>0 && A[i-1]>Tmp; i-- )
A[i] = A[i-1]; /*依次与已排序序列中元素比较并右移*/
A[i] = Tmp; /* 放进合适的位置 */
}
}
最好情况：顺序T=O(N)
最坏情况：逆序T=O (N2)
此方法也具有稳定性。
举例，问序列{34,8,64,51,32,21}中用插入排序和冒泡排序分别需要交换多少次？
答：冒泡法：9次；插入法，9次。
它们的次数相等，是巧合还是必然？见下一节。
9.2.3 时间复杂度下界
1.逆序对
对于下标i<j，如果A[i]>A[j]，则称(i,j)是一对逆序对（inversion）。
我们来看上一节中最后的序列{34,8,64,51,32,21}，它里面有多少逆序对呢？
(34,8)(34,42)(34,21)(64,51)(64,21)(64,21)(51,32)(51,21)(32,21)
一共9个逆序对。这说明，前面两种算法，交换2个相邻元素正好消去1个逆序对！
插入排序时间复杂度：T(N,I)=O(N+I)。这里面N是元素个数，I是逆序对个数。这个可以这样理解，时间复杂度最低为元素个数N，即逆序对为0，也就是顺序排列情况下；然后随着多一个逆序对，复杂度加1。
如果序列基本有序，那么插入排序简单且高效。
2.定理1：任意N个不同元素组成的序列平均具有N(N-1)/4个逆序对。
3.定理2：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为Ω（N2）。（注意：Ω是下界，O是上界）
这意味着，要提高算法效率，我们必须：每次消去不止1个逆序对！每次交换相隔较远的2个元素！
9.3 希尔排序
1.简单举例
它利用了插入排序的简单，同时克服了交换每次只交换相邻两个元素的缺点。
用下面这个序列来进行希尔排序的举例：
|
81 |
94 |
11 |
96 |
12 |
35 |
17 |
95 |
28 |
58 |
41 |
75 |
15 |
（1）首先以每5个元素取一个的规律进行排序：这里取了81、35、41。用插入排序对其进行排序：
|
35 |
94 |
11 |
96 |
12 |
41 |
17 |
95 |
28 |
58 |
81 |
75 |
15 |
然后取94、17、75进行插入排序，得到下面的结果：
|
35 |
17 |
11 |
96 |
12 |
41 |
75 |
95 |
28 |
58 |
81 |
94 |
15 |
然后考虑11、95、15，得到下面结果：
|
35 |
17 |
11 |
96 |
12 |
41 |
75 |
15 |
28 |
58 |
81 |
94 |
95 |
然后考虑96、28，得到下面结果：
|
35 |
17 |
11 |
28 |
12 |
41 |
75 |
15 |
96 |
58 |
81 |
94 |
95 |
然后考虑12和58：
|
35 |
17 |
11 |
28 |
12 |
41 |
75 |
15 |
96 |
58 |
81 |
94 |
95 |
（2）再用每3个元素取一个的规律进行排序：这里取35、28、75、58、95，结果如下：
|
28 |
12 |
11 |
35 |
15 |
41 |
58 |
17 |
94 |
75 |
81 |
96 |
95 |
（3）再做1间隔排序（即普通插入排序）。我们可以发现，此时整个序列已经基本有序，所以此时插入排序简单高效。
|
11 |
12 |
15 |
17 |
28 |
35 |
41 |
58 |
75 |
81 |
94 |
95 |
96 |
该算法的步骤：
①.定义增量序列DM>DM-1>…>D1=1
②对每个Dk进行“Dk-间隔”排序。
注意：“Dk-间隔”有序的序列，在执行“Dk-1-间隔”排序后，仍然是“Dk-间隔”有序的。
2.希尔增量序列
（1）原始希尔排序：DM=[N/2]，Dk=[Dk+1/2]。其中，[]代表取整。
伪代码如下：
void Shell_Sort(ElementType A[], int N)
{
for(D=N/2;D>0;D/=2)
{
for(P=D;P<N;P++)
{
Tmp= A[P];
for(i=P;i>=D&&A[i-D]>Tmp;i-=D)
A[i]=A[i-D];
A[i]=Tmp;
}
}
}
最坏情况：T=θ(N2)（θ代表即使上界也是下界，即可以达到的值）
这种情况即，增量元素不互质，则小增量可能根本不起作用。
3.其它增量序列
（1）Hibbard增量序列：Dk=2k-1（相邻元素互质）。最坏情况：T=θ(N3/2)，猜想Tavg=O(N5/4)。
（2）Sedgewick增量序列：{1,5,19,41,109}（9×4i-9×2i+1或4i-3×2i+1），猜想Tavg=O(N7/6)，Tworst=O(N4/3)。
4.稳定性：不稳定。
9.4 堆排序
9.4.1 选择排序
void Selection_Sort(ElementType A[], int N)
{
for(i=0;i<N;i++)
{
MinPosition = ScanForMin(A, i N-1);
/*从A[i]到A[N-1]中找最小元，并将其位置赋给MinPosition*/
Swap(A[i], A[MinPosition]);
/*将未排序部分的最小元换到有序部份的最后位置*/
}
}
无论如何，T=θ(N2)。
如何快速寻找到最小元？见下一节。
9.4.2 堆排序（选择排序的改进）
1.算法1：
void Heap_Sort ( ElementType A[], int N )
{
BuildHeap(A); /*调整为最小堆，复杂度为O(N) */
for ( i=0; i<N; i++ )
TmpA[i] = DeleteMin(A); /*以此把最小元弹出来放到这个临时数组中*/
/*复杂度为O(logN) */
for ( i=0; i<N; i++ )/* O(N) */
A[i] = TmpA[i];/*把临时数组的数组返回原来的数组*/
}
时间复杂度：T(N)=O(NlogN)
缺点：需要额外O(N)空间，并且复制元素需要时间。
2.算法2：
注意，在堆排序里面的这个堆，元素是从0的位置开始的；原来学堆的时候，0是用来放哨兵的。
因此，在堆排序中，元素下标从0开始。则对于下标为i的元素，其左、右孩子的下标分别为：2i+1, 2i+2。
伪码描述如下：
void Heap_Sort ( ElementType A[], int N )
{
for ( i=N/2-1; i>=0; i-- )/* BuildHeap */
PercDown( A, i, N );
for ( i=N-1; i>0; i-- ) {
Swap( &A[0], &A[i] ); /* DeleteMax */
PercDown( A, 0, i );
}
}
定理：堆排序处理N个不同元素的随机排列的平均比较次数是2NlogN-O(Nlog logN)。
注意：虽然堆排序给出最佳平均时间复杂度，但实际效果不如用Sedgewick增量序列的希尔排序。
整体C语言源代码：
void Swap( ElementType *a, ElementType *b )
{
ElementType t = *a; *a = *b; *b = t;
}
void PercDown( ElementType A[], int p, int N )
{ /* 改编代码4.24的PercDown( MaxHeap H, int p ) */
/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
int Parent, Child;
ElementType X;
X = A[p]; /* 取出根结点存放的值 */
for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
Child = Parent * 2 + 1;
if( (Child!=N-1) && (A[Child]<A[Child+1]) )
Child++; /* Child指向左右子结点的较大者 */
if( X >= A[Child] ) break; /* 找到了合适位置 */
else /* 下滤X */
A[Parent] = A[Child];
}
A[Parent] = X;
}
void HeapSort( ElementType A[], int N )
{ /* 堆排序 */
int i;
for ( i=N/2-1; i>=0; i-- )/* 建立最大堆 */
PercDown( A, i, N );
for ( i=N-1; i>0; i-- ) {
/* 删除最大堆顶 */
Swap( &A[0], &A[i] ); /* 见代码7.1 */
PercDown( A, 0, i );
}
}
9.5 归并排序
9.5 1有序子列的归并
1.举例：假设我们有两个有序序列如下：
|
1 |
13 |
24 |
26 |
|
2 |
15 |
27 |
38 |
我们要将它们合并成一个序列并按照顺序排序。我们需要设置三个指针，如图1所示。Aptr指向A序列的第一个元素（1），Bptr指向B序列的第一个元素（2），Cptr指向合并后的第一个元素。这里的指针其实是三个整数，分别存储的三个元素的下标。首先比较Aptr和Bptr指向的元素那个比较小，选择比较小的放入Cptr所代表的下标的那个位置。然后将Aptr加1，Cptr加1，用Bptr所代表的的下标的元素和Aptr所代表的的下标的元素比较，发现Bptr下标的元素（2）小，将2存入Cptr代表下标的元素，即C[Cptr]。然后依次类推。
图1
时间复杂度T(N)=O(N)。
伪代码描述如下：
/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置 */
void Merge( ElementType A[], ElementType TmpA[],
int L, int R, int RightEnd )
{
LeftEnd = R - 1; /* 左边终点位置。假设左右两列挨着 */
Tmp = L; /* 存放结果的数组的初始位置 */
NumElements = RightEnd - L + 1;
while( L <= LeftEnd && R <= RightEnd )
{
if( A[L] <= A[R] )
TmpA[Tmp++] = A[L++];
else TmpA[Tmp++] = A[R++];
}
while( L <= LeftEnd ) /* 直接复制左边剩下的 */
TmpA[Tmp++] = A[L++];
while( R <= RightEnd ) /*直接复制右边剩下的 */
TmpA[Tmp++] = A[R++];
for(i=0;i<NumElements;i++,RightEnd--)
A[RightEnd] = TmpA[RightEnd];
}
9.5.2递归算法
1.分而治之
如图2所示，该算法是稳定的。
图2
伪码描述如下：
void MSort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{
int Center;
if ( L < RightEnd ) {
Center = ( L + RightEnd ) / 2;
MSort( A, TmpA, L, Center );
MSort( A, TmpA, Center+1, RightEnd );
Merge( A, TmpA, L, Center+1, RightEnd );
}
}
时间复杂度为：T(N)=T(N/2)+T(N/2)+O(N)，即T(N)=O(NlogN)。
2.统一函数接口
为了与前面的函数接口统一，因此我们需要再写一个函数来统一函数接口。其伪码描述如下：
void Merge_sort( ElementType A[], int N )
{
ElementType *TmpA;
TmpA = malloc( N * sizeof( ElementType ) );
if ( TmpA != NULL )
{
MSort( A, TmpA, 0, N-1 );
free( TmpA );
}
else Error( “空间不足" );
}
如果只在Merge中声明临时数组，那么两个子函数声明如下：
void Merge( ElementType A[], int L, int R, int RightEnd )
void MSort( ElementType A[], int L, int RightEnd )
这样也不是不行，但是这样的话，每一次在子函数里面用一次释放一次，增加了时间复杂度，还不如直接在最外层的代码里面定义好。
整体的源代码实现如下：
/* 归并排序 - 递归实现 */
/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
{ /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
int LeftEnd, NumElements, Tmp;
int i;
LeftEnd = R - 1; /* 左边终点位置 */
Tmp = L; /* 有序序列的起始位置 */
NumElements = RightEnd - L + 1;
while( L <= LeftEnd && R <= RightEnd ) {
if ( A[L] <= A[R] )
TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
else
TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
}
while( L <= LeftEnd )
TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
while( R <= RightEnd )
TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
for( i = 0; i < NumElements; i++, RightEnd -- )
A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}
void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
{ /* 核心递归排序函数 */
int Center;
if ( L < RightEnd ) {
Center = (L+RightEnd) / 2;
Msort( A, TmpA, L, Center ); /* 递归解决左边 */
Msort( A, TmpA, Center+1, RightEnd ); /* 递归解决右边 */
Merge( A, TmpA, L, Center+1, RightEnd ); /* 合并两段有序序列 */
}
}
void MergeSort( ElementType A[], int N )
{ /* 归并排序 */
ElementType *TmpA;
TmpA = (ElementType *)malloc(N*sizeof(ElementType));
if ( TmpA != NULL ) {
Msort( A, TmpA, 0, N-1 );
free( TmpA );
}
else printf( "空间不足" );
}
9.5.3 非递归算法
非递归算法的图示如图3所示。
图3
额外空间复杂度是O(N)。我们只需要开一个临时数组就可以了，没必要每次都开一个。
其伪码描述如下：
void Merge_pass( ElementType A[], ElementType TmpA[], int N,int length )
/* length = 当前有序子列的长度*/
{
for ( i=0; i <= N–2*length; i += 2*length )
Merge1( A, TmpA, i, i+length, i+2*length–1 );
if ( i+length < N ) /* 归并最后2个子列*/
Merge1( A, TmpA, i, i+length, N–1);
else /* 最后只剩1个子列*/
for ( j = i; j < N; j++ ) TmpA[j] = A[j];
}
统一接口如下：
void Merge_sort( ElementType A[], int N )
{
int length = 1; /* 初始化子序列长度*/
ElementType *TmpA;
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 Error( “空间不足" );
}
具有稳定性！
缺点是需要额外空间之类的~此方法主要用在外排序。
C语言实现源代码：
/* 归并排序 - 循环实现 */
/* 这里Merge函数在递归版本中给出 */
/* length = 当前有序子列的长度*/
void Merge_pass( ElementType A[], ElementType 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( ElementType A[], int N )
{
int length;
ElementType *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( "空间不足" );
}