第九讲 排序(上)
简单排序
前提
冒泡排序
1 | //伪代码 |
最好情况:顺序T=O(N)
最坏情况:逆序T=O(N^2)
稳定
插入排序
1 | void Insertion_Sort (ElementType A[],int N) |
最好情况:顺序T=O(N)
最坏情况:逆序T=O(N^2)
稳定
时间复杂度下界
- 定理:任意N个不同元素组成的序列平均具有N(N-1)/4个逆序对
- 定理:任何仅以交换相邻两元素来排序的算法,其平均时间复杂度为Ω(N^2)
意味着:要提高算法效率,我们必须
- 每次消去不止1个逆序对
- 每次交换相隔较远的2个元素
希尔排序
希尔增量序列
原始希尔排序
1
2
3
4
5
6
7
8
9
10
11void Sheel_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=Θ(N^2)
增量元素不互质,则小增量可能根本不起作用
更多增量序列
Hibbard增量序列
Sedgewick增量序列
堆排序
选择排序
1 | void Selection_Sort(ElementType A[],int N) |
无论如何T=Θ(N^2)
堆排序
算法1
1
2
3
4
5
6void 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++)A[i]=TmpA[i];//O(N)
}T(N)=O(NlogN)
需要额外O(N)空间,并且复制元素需要时间
算法2
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
31void Heap_Sort(ElementType A[],int N)
{
for(i=N/2;i>=0;i--)
PercDown(A,i,N); //BuildHeap
for(i=N-1;i>0;i--){
Swap(&A[0],&A[i]); //DeleteMax
PercDown(A,0,i);
}
}
void Swap(ElementType *a,ElementType *b)
{
ElementType t=*a;*a=*b;*b=t;
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++;
if(X>=A[Child]) break;
else A[Parent]=A[Child];
}
A[Parent]=X;
}
void PrecDown(ElementType A[],int p,int N)
{
}
归并排序
有序子列的归并
1 | void Merge(ElementType A[],ElementType TmpA[],int L,int R,int RightEnd) |
递归算法
分而治之
1
2
3
4
5
6
7
8
9
10void 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)=O(NlogN)
稳定
统一函数接口
1
2
3
4
5
6
7
8
9
10void Merge_sort(ElementType A[],itn N)
{
ElementType *TmpA;
TmpA=malloc(N*sizeof(ElementType));
if(TmpA!=NULL){
MSort(A,TmpA,0,N-1);
free(TmpA);
}
else Error("空间不足");
}若用临时数组的话,会浪费很大部分空间
非递归算法
额外空间复杂度是O(N)
1 | /* 归并排序 - 循环实现 */ |