考研笔记 | 数据结构 §8. 排序

发表于 2018-05-19 分类于课业阅读次数：本文字数： 4.9k 阅读时长 ≈ 4 分钟

排序：重新排序表中元素，使其满足按关键字递增或递减的过程。
方法：
- 内部排序：排序期间全放在内存中的排序；
- 外部排序：排序期间元素无法同时在内存，在排序期间不断在内外存间移动的排序。

§1 插入排序

直接插入排序：“将待排序记录插入有序序列中，重复 $n-1$ 次”

算法空间效率 $O (1)$，时间 $O (n)$/$\sum^n_i=2 (i+1)$，平均 $\frac {n^2}{4}$/$O (n^2)$，算法稳定。

    void InsertSort(ElenType A[], int n){
  int i,j; // 适用于顺序存储和链式存储的线性表
  for(i=2;i<=n;i++){
	if(A[i],key<A[i-1].key){
	  A[0]=A[j];
	  for(j=i-1;A[0].key<A[j].key;--j)
	  A[j+1]=A[j];
	  A[j+1]=A[0];
	}
  }
}

折半插入排序：查找有序子表由折半法实现，其他不变。

```c
void InsertSort(ElemType A[],int n){
int i,j,low,high,mid;
for(i=2;j<=n;i++){
A[0]=A[i];
low=1;high=i-1;
while(low<=high){
mid=(low+high)/2;
if(A[mid].key>A[0].key)
high=mid-1;
else
low=mid+1;
}
for(j=i-1;j>high+1;–j){
A[j+1]=A[j];
A[high+1]=A[0];
}
}
}// 时间复杂度 O (n^2), 算法稳定

7. 希尔排序（缩小增量排序）：将序列分为若干个子块，分别进行直接插入排序，直至对整个序列进行直接插入排序。
8. 步骤：
	1. 分成子序列（增量dk）；
	2. 对子序列排序
	3. 缩小增量，重复以上步骤
	4. 增量序列最后一个增量一定是1，如(9,5,3,2,1)或(3,2,1)
9. 例子：对于(52,49,80,36,14,58,61)
	  ![希尔排序示意图][2]
	  时间复杂度$O(n)^{\frac {3}{2}}$，算法不稳定
10. ```c
	void ShellSort(ElemType A[],int n){//前后记录位置增量是dk,不是1
	  for(dk=n/2;dk>=1;dk=dk/2){
		for(i=dk+1;dk>=1;dk=dk/2){
		  if(A[i].key<A[i-dk].key){
			A[0]=A[i];
			for(j=i-dk;j>0&&A[0].key<A[j].key;j-=dk){
			  A[j+dk]=A[j]//记录后移
			  A[j+dk]=A[0];
			}
		  }
		}
	  }
	}

空间效率 $O (l)$，时间效率 $O (n^2)$，不稳定，适用于线性表顺序存储。

§2 交换排序

冒泡排序：“依次比较相邻元素，‘逆序’则交换，重复 n-1 次”

```c
void BubbleSort(ElemType A[],int n){
for(i=0;i<n-1;i++){
flag=false;// 表示交换的标志
for(j=n-1;j>1;j–){
if(A[j-1].key>A[j].key){
swap (A [j-1],A [j]);// 交换
flag=true;
}
}
if(flag==false)
return;// 未交换，说明有序
}
}// 没糖排序都有一个元素放到最终位置

	空间复杂度$O(1)$，时间复杂度：最坏$O(n^2)$，最好$O(n)$，平均$O(n^2)$，算法稳定。
13. 快速排序：一趟排序把记录分为两份，一份关键字比另一份小。
14. ```c
	int Dived(ElemType A[],int low,int high){
	  ElemType pivot=A[low];
	  while(low<high){
		while(low<high&&A[high]>=pivot){
		  --high;
		  A[low]=A[high];
		}
		while(low<high&&A[low]<=pivot){
		  ++low;
		  A[high]=A[low];
		}
		A[low]=pivot;
		return low;
	  }
	  void QuickSort(ElemType A[],int low,int high){
		if(low<high){//跳出条件
		  int pivot=Dived(A,low,high);
		  QuickSort(A,low,pivot-1);
		  QuickSort(A,pivot+1,high);
		}
	  }
	}

空间复杂度：最好 $\lceil \log_2 {(n+1)} \rceil$，最坏 $O (n)$，平均 $O (log_2n)$
时间复杂度：最好，平均 $O (n\log n)$，最坏 $O (n^2)$
算法不稳定。

快速排序，是内部排序算法中平均性能最优的算法。
简单选择排序：“在待排序记录中选取最小的，交换到合适位置，重复 n-1 次。”

```c
void SelectSort (ElemType A [],int n){// 伪代码
for(i=0;i<n-1;j++){
min=j;
for(j=i+1;j<n;j++){
if(A[j]<A[min])
min=j;
}if(min!=i)
swap (A [i],A [min]);// 交换
}
}

	空间复杂度：$O(1)$
	时间复杂度：最好$0$，最坏和平均情况$O(n^2)$，算法不稳定

# §3 堆排序

18. 树形选择排序，将$L[1,\dots,n]$看成一棵完全二叉树的顺序存储结构，且
	1. $L(i) \leq L(2i)$且$L(i) \leq L(2i+1)$
	2. $L(i) \geq L(2i)$且$L(i) \geq L(2i+1)$
	满足1为小顶堆，满足2为大顶堆。
19. 建堆（大顶堆）：对$\lfloor \frac{n}{2} \rfloor$个结点为根的子树筛选（最后一个结点父亲），若根结点关键字小于左右子女关键字较大者，则交换。重复步骤。
20. ```c
	void BuildMaxHeap(ElemType A[],int len){//建大根堆
		for(int i=len/2;i>0;i--){
			AdjustDown(A,i,len);
		}
	}
	void AdjustDown(ElemType A[],int k,int len){
		A[0]=A[k];
		for(i=2*k;i<=len;i*=2){
			if(i<len&&A[i]<A[i+1])
				i++;//取key较大子结点向下取下标
			if(A[0]>=A[i])
				break;
			else{
				A[k]=A[i];//将A[i]调到双亲上
				k=i;//修改k值
			}
		}
		A[k]=A[0];
	}//调整时间与树高有关，为O(n)

```c
void HeapSort(ElemType A[],int len){
BuildMaxHeap (A,len);// 初始建堆
for (i=len;i>1;i–){//n-1 趟交换与建堆
Swap(A[i],A1);
AdjustDown (A,1,i-1);// 输出堆顶，调整
}
}

	空间复杂度：$O(1)$，建堆$t=O(n)$
	时间复杂度：$O(n\log_2n)$,算法不稳定
22. ```c
	void AdjustUp(ElemType A[],int k){//建立大顶堆，上调法
		A[0]=A[k];
		int i=k/2;
		while(i>0&&A[i]<A[0]){
			A[k]=A[i];
			k=i;
			i=k/2;//双字下调，向上比较
		}
		A[k]=A[0];
	}

§4 归并排序

归并排序：两个及以上有序表组合为一个有序表
二路归并排序：

```c
ElemType *B=(ElemType ) malloc((n+1) sizeof (ElemType));// 辅助数组
void Merge(ElemType A[],int low,int mid,int high){
for(int k=low;k<=high;k++)
B [k]=A [k];// 将 A 中元素复制到 B
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
if(B[i]<=B[j])
A [k]=B [k+1];// 比较 B 中两段元素，将较小值赋予 A 中
else
A[k]=B[j++];
}
while (i<=mid) // 两个 while 仅一个会执行
A [k+1]==B [i++];// 若一表未检测完，复制
while(j<=high)
A [k++]=B [j++];// 若二表未检测完，复制
}

26. ```c
	void MergeSoft(ElemType A[],int low,int high){
		if(low<high){
			int mid=(low+high)/2;//从中间划分两个子序列
			MergeSoft(A,low,mid);
			MergeSoft(A,mid+1,high);
			Merge(A,low,mid,high);//归并
		}
	}

空间复杂度:$O (n)$，时间复杂度 $O (n
log_2n)$，算法稳定

§5 基数排序

基数排序：借 “分配” 与 “收集” 两种操作对关键字进行排序。
分类：最高位优先（MSD），最低位优先（LSD）
方法：按个位分配到一个链表，并按个位收集，依次……
空间效率：$O (r)$，时间效率：$O (d (n+r)$，其中 n 为排序，r 为收集，算法稳定。

§6 小结

内部排序算法比较

排序方法		时间复杂度		空间	稳定	特点
	最好	平均	最坏	复杂度	与否
直接插入排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是	元素少或基本有序时高效
冒泡排序	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	是
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	否	比较次数最多
希尔排序	$O(n^{\frac {3}{2}})$	$O(n^{\frac {3}{2}})$	$O(n^{\frac {3}{2}})$	$O(1)$	否
快速排序	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(n^2)$	$O(\log_2 n)$	否	平均时间性能最好
堆排序	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(1)$	否	辅助空间少
2 - 路归并排序	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(n\log_2 n)$	$O(n)$	是	算法稳定
基数排序	$O(d(n+r))$	$O(d(n+r))$	$O(d(n+r))$	$O(r)$	是	适合个数多关键字少的情况

排序方法的选择
1. 若 n 较小（$n\leq 50$），可用直插式简单选则排序，效果最好；
2. 若基本有序，宜直插式冒泡；
3. n 较大，应采用 $O (n\log_2n)$ 方法：快排，堆排或归并；
4. 当文件 n 个关键字随机时，任何借助 “比较” 的算法，至少 $O (n\log_2n)$；
5. 若 n 很大，且关键字可分解，用基数排序；
6. 当记录本身信息量大，为避免大量移动，可用链表存储。
小结
1. 排序稳定，且关键字为实数（不可分解，double，float 类），选择直接插入排序；
2. - 稳定的排序方法：冒泡排序、直接插入排序、归并排序、基数排序；
  - $O (n\log_2n)$ ：堆排序、归并排序、快速排序；
  - $O (n^2)$：直接插入排序、冒泡、简单选择排序；
  - 可达 $O (n)$：直接插入排序、冒泡排序；
3. 辅助空间：快速排序 $O (\log2_n)$＞归并排序 $O (n)$＞直接插入排序、冒泡排序、简单选择排序、希尔排序、堆排序 $O (1)$；
4. 排序趟数与序列原始状态无关：简单选择排序、直接插入排序、基数排序；
5. 每趟排序结束至少确定一个元素位置：简单选择排序、快速排序、堆排序；
6. 一般情况下，查找效率最低的是：堆排序。