排序#
我们假设 "<" ">" 运算符存在，这两种运算是仅有的允许对输入数据进行的操作，这称为基于比较的排序. 我们假定 N 为要排序的元素个数，数据从位置 0 开始。
插入排序#
插入排序有 N-1 趟(pass), 对于 \(P=1\) 到 \(P=N-1\) 趟我们保证位置 0 到位置 \(P-1\) 上的元素是已经排序好的，而第 \(P\) 趟要做的就是将位置 \(P\) 的元素向左移动到它在前 \(P+1\) 个元素中的正确位置上。
void InsertionSort ( ElementType A[ ], int N )
{
int j, P;
ElementType Tmp;
for ( P = 1; P < N; P++ ) {
Tmp = A[ P ]; /* the next coming card */
for ( j = P; j > 0 && A[ j - 1 ] > Tmp; j-- )
A[ j ] = A[ j - 1 ];
/* shift sorted cards to provide a position
for the new coming card */
A[ j ] = Tmp; /* place the new card at the proper position */
} /* end for-P-loop */
}
- 最佳情况 - 输入数据是已经排好序的，那么运行时间为 \(O(N)\)
- 最坏情况 - 输入数据是逆序的，那么运行时间为 \(O(N^2)\)
简单排序算法的下界#
一个逆序是指数组中 \(i<j\) 但 \(A[i]>A[j]\) 的序偶 \((A[i],A[j])\)
交换不按原序排列的相邻元素会恰好消除一个逆序，因此插入排序的运行时间为 \(O(I+N)\). 其中 \(I\) 为原始数组中的逆序数，当逆序数较少时插入排序以线性时间运行。
\(N\) 个互异数的数组的平均逆序数为 \(\dfrac{N(N-1)}{4}\)
通过交换相邻元素进行排序的任何算法平均需要 \(\Omega(N^2)\) 时间
希尔排序#
希尔排序使用一个 \(h_1,h_2,\ldots,h_t\) 的增量序列(\(h_1=1\)).
\(h_k\)-sort 的一般做法是，对于 \(h_k,h_k+1,\ldots,N-1\) 中的每一个位置 \(i\), 将其元素放到 \(i,i-h_k,i-2h_k,\ldots\) 中间的正确位置上。相当于对 \(h_k\) 个独立的子数组各进行一次插入排序。\(h_k\)-sort 之后，对于每一个 \(i\) 我们都有 \(a_i\leq a_{i+h_k}\), 此时成称为 \(h_k\)-sorted.
希尔排序的一个重要性质: 一个 \(h_k\)-sorted 的文件（此后将是 \(h_{k-1}\)-sorted）保持他的 \(h_k\)-sorted 性质。
希尔增量序列#
\(h_t=\lfloor N/2 \rfloor, h_k=\lfloor h_{k+1}/2 \rfloor\)(可以有更好的增量序列)
void Shellsort( ElementType A[ ], int N )
{
int i, j, Increment;
ElementType Tmp;
for ( Increment = N / 2; Increment > 0; Increment /= 2 )
/*h sequence */
for ( i = Increment; i < N; i++ ) { /* insertion sort */
Tmp = A[ i ];
for ( j = i; j >= Increment; j - = Increment )
if( Tmp < A[ j - Increment ] )
A[ j ] = A[ j - Increment ];
else
break;
A[ j ] = Tmp;
} /* end for-I and for-Increment loops */
}
-
最坏情形分析
使用希尔增量时的希尔排序的最坏情形运行时间为 \(\Theta(N^2)\)
-
Hibbard 增量序列
\(h_k= 2^k-1\), 且其最坏情形下运行时间为 \(O(N^{3/2})\)
堆排序#
如果我们先 BuildHeap, 再 Delete N 次最小元素，这样需要多使用一个附加数组，使得存储需求增加一倍。
每次 DeleteMin 后，堆的大小缩小了 1, 因此我们可以用堆中最后的单元来存放刚刚删去的元素。
整体流程：
- 以线性时间建一个 Max 堆
- 将堆中最后元素与第一个元素交换，缩减堆的大小并进行下滤。执行 N-1 次
DeleteMax操作 - 算法终止时，数组按顺序即为从小到大的排序结果
void Heapsort( ElementType A[ ], int N )
{ int i;
for ( i = N / 2; 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 );
}
}
注：这里的堆我们是从 0 开始计数的，因此左儿子应该是 2*i+1
对 N 个互异项的随机排列进行堆排序，平均比较次数为 \(2N\log N-O(N\log\log N)\)
归并排序#
基本操作：合并两个已排序的表，我们可以用双指针的方法在线性时间内完成两个表的合并，具体操作如下
- 取两个输入数组 A 和 B, 一个输出数组 C, 以及三个计数器 Aptr, Bptr, Cptr, 分别对应数组的开端。
- 每次
A[Aptr]和B[Bptr]中的较小者会被拷贝到 C 中的下一个位置，，相关的计数器向前推进一步。 - 当两个输入表中有一个用完时，将另一个表的剩余部分拷贝到 C 中。
- 我们最多进行 \(N-1\) 次比较，因此合并时间显然是线性的。
因此归并排序的流程就是，如果 N=1 那么只有一个元素需要排序，答案是显然的；否则递归地将前半部分数据和后半部分数据各自归并排序，得到排序后的两部分数据，然后使用刚刚描述的合并操作将这两个部分合并到一起。
需要注意的是，如果我们每次递归调用 Merge 都局部声明一个临时数组，那么任意时刻就会有 \(\log N\) 个临时数组处于活动期，这对于小内存的机器是致命的。注意到 Merge 只在每次递归调用的最后一行，因此任何时刻只需要一个临时数组活动，而且可以使用该临时数组的任意部分，这样节约了空间。
void MSort( ElementType A[ ], ElementType TmpArray[ ],
int Left, int Right )
{ int Center;
if ( Left < Right ) { /* if there are elements to be sorted */
Center = ( Left + Right ) / 2;
MSort( A, TmpArray, Left, Center ); /* T( N / 2 ) */
MSort( A, TmpArray, Center + 1, Right ); /* T( N / 2 ) */
Merge( A, TmpArray, Left, Center + 1, Right ); /* O( N ) */
}
}
void Mergesort( ElementType A[ ], int N )
{ ElementType *TmpArray; /* need O(N) extra space */
TmpArray = malloc( N * sizeof( ElementType ) );
if ( TmpArray != NULL ) {
MSort( A, TmpArray, 0, N - 1 );
free( TmpArray );
}
else FatalError( "No space for tmp array!!!" );
}
/* Lpos = start of left half, Rpos = start of right half */
void Merge( ElementType A[ ], ElementType TmpArray[ ],
int Lpos, int Rpos, int RightEnd )
{ int i, LeftEnd, NumElements, TmpPos;
LeftEnd = Rpos - 1;
TmpPos = Lpos;
NumElements = RightEnd - Lpos + 1;
while( Lpos <= LeftEnd && Rpos <= RightEnd ) /* main loop */
if ( A[ Lpos ] <= A[ Rpos ] )
TmpArray[ TmpPos++ ] = A[ Lpos++ ];
else
TmpArray[ TmpPos++ ] = A[ Rpos++ ];
while( Lpos <= LeftEnd ) /* Copy rest of first half */
TmpArray[ TmpPos++ ] = A[ Lpos++ ];
while( Rpos <= RightEnd ) /* Copy rest of second half */
TmpArray[ TmpPos++ ] = A[ Rpos++ ];
for( i = 0; i < NumElements; i++, RightEnd - - )
/* Copy TmpArray back */
A[ RightEnd ] = TmpArray[ RightEnd ];
}
- 运行时间分析
注：Mergesort 需要线性外部内存，复制数组缓慢，因此不适合用于内部排序，但对于外部排序是有用的。
快速排序#
快速排序是在实践中已知的最快的排序算法，平均运行时间是 \(O(N\log N)\)
快速排序的算法流程：（将数组 S 排序）
- 如果 S 中的元素个数是 0 或者 1 则返回
- 从 S 中取任意元素为主元
- 将 \(S-\{v\}\) 分为两个不相交的集合 \(S_1=\{x\in S-\{v\}|x\leq v\}, S_2=\{x\in S-\{v\}|x\geq v\}\)
- 返回 \(quicksort(S_1), v, quicksort(S_2)\)
对于不同主元的选取，分割的描述不是唯一的。
选取主元#
- 错误的方法
Pivot=A[0]
这样如果输入是顺序或者反序的，那么每次划分所有元素全部落入 \(S_1\) 或者 \(S_2\), 选取主元并没有带来任何帮助，完成排序需要 \(O(N^2)\) 的时间。 - 安全做法
Pivot = random select from A[]
但随机数的产生是昂贵的 - 三数中值分割法
Pivot = median(left, center, right)
一组 N 个数的中值是第 \(\lceil N/2 \rceil\) 大的数，主元最好是选择中值，但这很难算出，而且会明显减慢排序的速度。因此我们可以使用左端、右端和中心位置上的三个元素的中值作为主元。
这样消除了错误方法中的最坏情形，减少了快速排序大概 5% 的运行时间。
划分策略#
首先我们将主元和最后的元素交换，使得主元离开将要分割的数据段，随后 i 从第一个元素开始，j 从倒数第二个元素开始。（假设所有元素互异）
- 当 i 在 j 的左边时，我们将 i 右移，移过那些小于主元的元素，并将 j 左移，移过那些大于主元的元素。
- 当 i 和 j 停止时，i 指向一个大元素而 j 指向一个小元素，如果 i 在 j 的左边那么将这两个元素互换。
- 直到 i 和 j 彼此交错时，停止交换
- 将 i 和主元交换
对于那些等于主元的关键字，我们采用停止 i j 并交换的策略。因为若 i j 不停止，对于数组中所有关键字都相同的情况，我们需要有程序防止 i j 超出数组的界限。最后我们会把主元交换到 i 的最后位置上，也就是倒数第二个位置，这样我们又陷入了最坏情况。
小数组#
对于很小的数组(\(N\leq 20\))快速排序不如插入排序，因此我们可以设置一个截止范围 Cutoff(e.g. 10). 当 N 小于阈值的时候采用插入排序.
实现#
void Quicksort( ElementType A[ ], int N )
{
Qsort( A, 0, N - 1 );
/* A: the array */
/* 0: Left index */
/* N – 1: Right index */
}
/* Return median of Left, Center, and Right */
/* Order these and hide the pivot */
ElementType 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 ] );
/* Invariant: A[ Left ] <= A[ Center ] <= A[ Right ] */
Swap( &A[ Center ], &A[ Right - 1 ] ); /* Hide pivot */
/* only need to sort A[ Left + 1 ] … A[ Right – 2 ] */
return A[ Right - 1 ]; /* Return pivot */
}
void Qsort( ElementType A[ ], int Left, int Right )
{ int i, j;
ElementType Pivot;
if ( Left + Cutoff <= Right ) { /* if the sequence is not too short */
Pivot = Median3( A, Left, Right ); /* select pivot */
i = Left; j = Right – 1; /* why not set Left+1 and Right-2? */
for( ; ; ) {
while ( A[ + +i ] < Pivot ) { } /* scan from left */
while ( A[ – –j ] > Pivot ) { } /* scan from right */
if ( i < j )
Swap( &A[ i ], &A[ j ] ); /* adjust partition */
else break; /* partition done */
}
Swap( &A[ i ], &A[ Right - 1 ] ); /* restore pivot */
Qsort( A, Left, i - 1 ); /* recursively sort left part */
Qsort( A, i + 1, Right ); /* recursively sort right part */
} /* end if - the sequence is long */
else /* do an insertion sort on the short subarray */
InsertionSort( A + Left, Right - Left + 1 );
}
- 在最开始选取主元时，我们将
A[left],A[mid],A[Right]进行排序。这样的话我们将较小值放在了最左边，较大值放在了最右边，这符合分割的要求。此外由于A[left]比主元小，我们不用担心 j 越界。
复杂度分析#
\(T(N)=T(i)+T(N-i-1+)+cN\) 其中 \(i=|S_1|\)
- 最坏情形：主元始终是最小元素，此时 \(i=0\) 则递推关系为 \(T(N)=T(N-1)+cN,N>1\) 那么 \(T(N)=T(1)+d\sum\limits_{i=2}^N i=O(N^2)\)
- 最好情形：主元正好位于中间 \(T(N)=2T(N/2)+cN\Rightarrow T(N)=O(N\log N)\)
- 平均情形：\(T(N)=\dfrac{2}{N}\sum\limits_{j=0}^{N-1}T(j)+cN\Rightarrow T(N)=O(N\log N)\)
大型结构的排序#
交换两个大型的结构可能是非常昂贵的，因此我们让输入数组包含指向结构的指针，通过比较指针指向的关键字，必要时交换指针来进行排序。
排序的一般下界#
只使用比较的任意排序算法最坏情形下都需要 \(\Omega(N\log N)\)
使用决策树证明：共 \(N!\) 种排序可能，因此决策二叉树有 \(N!\) 片叶子，则树的深度至少为 \(\log(N!)=\Omega(N\log N)\)
桶排序#
若输入数据 \(A_1,A_2,\ldots,A_N\) 都小于 \(M\), 那么我们可以用一个大小为 \(M\) 的 Count 数组，初始化为全 0. 于是 Count 有 \(M\) 个桶，读入到 \(A_i\) 时 Count[Ai] 自增一。所有数据读完后扫描数组 Count 打印排序后的表。
\(O(M+N)\)
LSB MSB
Created: 2023年9月27日 10:52:36