本文共 4316 字，大约阅读时间需要 14 分钟。

一、内部排序

3、选择排序

• 选择排序基本思想：每一趟在后面n-i+1（i=1, 2, ..., n-1) 个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟只剩下一个待排序元素，结束选择。

3.1、简单选择排序

• 直接选择排序代码如下：

  // 简单选择排序void SelectSort(int a[], int n){
       	int min;	for (int i = 0; i < n - 1; i++)	{
       		min = i;		for (int j = i + 1; j < n; j++)		{
       			if (a[j] < a[min])min = j;		}		if (min != i)		{
       			int t = a[i];			a[i] = a[min];			a[min] = t;		}	}}

• 简单选择排序的空间复杂度为常数阶。
• 时间复杂度始终是O(n²)。
• 稳定性方面，简单选择排序也是不稳定的排序算法。

3.2、堆排序

3.2.1、堆

• 长度为 n 的序列，若满足下面两个条件中的其中一个则称为堆
  ① L(i)>=L(2i) and L(i)>=L(2i+1)
  ② L(i)<=L(2i) and L(i)<=(2i+1)
• i 取值从 1 到不超过序列长度一般的最大整数。
• 满足条件①的，称为大堆根，显而易见，此时根节点的关键字要比其子树的关键字都大；满足条件②的称为小堆根，此时与大堆根相反，根节点的关键字小于其子树的关键字。
  

3.2.2、堆排序

• 堆排序的算法思想：先将待排序表建成初始堆，例如构成大堆根，此时堆顶元素就是最大值，可直接输出；输出堆顶元素后，将堆底元素送入堆顶，由于此时不满足大堆根性质，需要将堆顶元素向下调整使之恢复满足大堆根性质，在输出堆顶元素反复如此，直到堆中只剩下一个元素。
• 堆排序有两个关键步骤：一是构建初始堆，二是调整剩余元素使之满足大堆根。
  
• 通常用筛选法来进行调整，而构建初始堆则是反复使用筛选法进行构造。
• 算法代码如下：

  //小堆跟// 堆排序：①调整void MinHeapAdjust(int a[], int k, int len){
       	a[0] = a[k];	int i;	for (i = 2 * k; i <= len; i *= 2)	{
       		if (i < len&& a[i] < a[i + 1])			i++;		if (a[0] >= a[i])break;		else {
       			a[k] = a[i];			k = i;		}	}	a[k] = a[0];}//堆排序：②构建初始堆void CreateMinHeap(int a[], int len){
       	for (int i = len / 2; i > 0; i--)		MinHeapAdjust(a, i, len);}//堆排序：③排序void MinHeapSort(int a[], int len){
       	CreateMinHeap(a, len);	for (int i = len; i > 1; i--)	{
       		int t = a[i];		a[i] = a[1];		a[1] = t;		MinHeapAdjust(a, 1, i - 1);	}}// 大堆根// 调整void MaxHeapAdjust(int a[], int k, int len){
       	a[0] = a[k];	int i;	for (i = 2 * k; i <= len; i *= 2)	{
       		if (i < len && a[i] > a[i + 1])			i++;		if (a[0] <= a[i])break;		else {
       			a[k] = a[i];			k = i;		}	}	a[k] = a[0];}// 构造初始堆void CreateMaxHeap(int a[], int len){
       	for (int i = len / 2; i > 0; i--)		MaxHeapAdjust(a, i, len);}// 大堆根排序void MaxHeapSort(int a[], int len){
       	CreateMaxHeap(a, len);	for (int i = len; i > 1; i--)	{
       		int t = a[i];		a[i] = a[1];		a[1] = t;		MaxHeapAdjust(a, 1, i - 1);	}}

• 堆排序的空间复杂度仍然是常数阶，只用了常数个辅助单元。
• 时间复杂度方面，初建堆的时间为O(n)，之后有 n-1 次向下调整操作，每次调整的时间复杂的为O(h)，在最好、最坏和平均情况下，堆排序的时间复杂度为O(nlog₂n)。
• 堆排序是一种不稳定的排序算法。

4、其他内部排序

• 主要有归并排序和基数排序。

4.1、归并排序

• 归并排序的基本思想：将待排序表的 n 个元素，视作 n 个有序的子表，然后两两归并，得到 (n/2) 或 (n/2)+1 个长度为 1 或 2 的有序表；然后继续两两归并……直到合并成一个长度为 n 的有序表为止。由于每次都是两两合并，因此又称为二路归并排序。
• 代码如下：

  // 二路归并排序int* b = new int[20];void Merge(int a[], int low, int mid, int high){
       	int i, j, k;	for (k = low; k <= high; k++)		b[k] = a[k];	for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)	{
       		if (b[i] <= b[j])			a[k] = b[i++];		else			a[k] = b[j++];	}	while (i <= mid) a[k++] = b[i++];	while (j <= high)a[k++] = b[j++];}void MergeSort(int a[], int low, int high){
       	if (low < high)	{
       		int mid = (low + high) / 2;		MergeSort(a, low, mid);		MergeSort(a, mid + 1, high);		Merge(a, low, mid, high);	}}

• 以 { 49,38,65,97,76,13,27 } 为例，二路归并过程如下：

• 二路归并排序的空间复杂度为 O(n)。
• 二路归并排序每趟的时间为 O(n)，共需要 log₂n 或 log₂n + 1，所以算法的时间复杂的为 O(nlog₂n)。
• 稳定性方面，二路归并排序是一种稳定的算法。

4.2、基数排序

• 此种排序方法，基于关键字各位的大小进行排序，是一种借助多关键字排序的思想堆单逻辑关键字进行排序的方法。
  
• 实现多关键字排序，通常有两种方法：最高位优先法(MSD)和最低位优先法(LSD)，前者按照关键字位权重递减依次逐层划分成若干跟小子序列，最后将所有序列依次连接成一个有序序列；后者按照关键字递增依次进行排序，同样最后形成一个有序序列。
  
• 通常采用链式基数排序。最低位优先法示例如下：
  
• 基数 r=10，故需要 10 个链队，每个关键字由 3 个子关键字——个位、十位和百位组成，第一趟按照最低位进行分配，凡是个位数一样的放到同一个链队：
  
• 接着对链队依次收集，得到部分有序序列：
  
• 一次分配和一次收集，完成了最低位优先法的第一趟排序，接着进行第二趟，先按照十位上的数字进行分配：
  
• 再次进行收集，得到序列：
  
• 再按照百位进行分配：
  
• 此时进行收集便得到了一个全部有序的序列：
  
• 以静态链表为例，伪代码如下：

  #define MAXNUM_KEY 8#define RADIX 10#define MAX_SPACE 1000typedef struct{
       	int keys[MAXNUM_KEY];	int next;}SLCell;typedef struct{
       	SLCell r[MAX_SPACE];	int keyNum;	int recNum; // 链表当前长度}SLList;typedef int ArrType[RADIX];void Distribute(SLCell &r, int i, ArrType &f, ArrType &e){
       	for(int j=0;j

5、小结

• 各个常用内部排序算法的最好情况、最坏情况与平均情况下的时间复杂度，空间复杂度、稳定性，总结如下表：
  
• 选取何种排序算法，通常从以下几个方面进行考虑：
  ① 问题规模 n；
  ② 元素的信息量大小；
  ③ 关键字的结构及其分布情况；
  ④ 稳定性的要求；
  ⑤ 语言工具的条件。
• 若n较小，可采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动次数较简单选择排序的多，因而当记录本身信息量较大时，用简单选择排序较好。
• 若序列的初始状态的关键字已经基本有序，则选用直接插入排序或冒泡排序较好。
• 若n较大，则应采用时间复杂度为O(nlog₂n）的排序方法：快速排序、堆排序或归并排序。快速排序被认为是目前基于比较的内部排序方法中最好的方法，当待排序的关键字随机分布时，快速排序的平均时间最短。堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况，这两种排序都是不稳定的。若要求排序稳定且时间复杂度为 O(nlog₂n),则可选用归并排序。更好的是，将直接插入排序和归并排序结合，先利用直接插入排序求出一个较长的有序子序列，然后两两归并。
• n很大时，记录的关键字位数较少且可以分解时，采用基数排序较好。
• 当记录的本身信息量较大时，为避免耗费大量时间移动记录，可用链表作为存储结构。
• 在基于比较的排序方法中，每次比较两个关键字的大小之后，仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的m个关键字随机分布时，任何借助于“比较”的排序算法，至少需要O( nlog₂n）的时间。

转载地址：http://bhqgn.baihongyu.com/