内部排序算法（未完）

内部排序算法

先介绍几个排序算法中的概念：

排序的稳定性是指：待排序的记录序列中可能存在两个或两个以上关键字相等的记录，排序后具有相等关键字的记录的相对顺序不变。
例如排序前的记录序列A={2,4,1,2,8,1}；则稳定排序后的序列为B={1,1,2,2,4,8}。

原地排序是指：在排序过程中不使用额外的内存空间，而只是通过对原序列的记录两两进行比较和交换来完成排序过程。

由于待排序的记录数量不同，使得在排序过程中涉及的存储器不同，可将排序方法分为两类：
内部排序：待排序记录存放在计算机内存中进行排序的过程；
外部排序：待排序记录的数量非常大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序过程。
这里，我们主要介绍内部排序。内部排序大致可以分为五类：
(1) 插入排序
(2) 交换排序
(3) 选择排序
(4) 归并排序
(5) 计数排序

按照排序过程中的工作量，可以分为三类：
(1) 简单排序：时间复杂度为O(n^2)
(2) 先进排序：时间复杂度为O(n*logn)
(3) 基数排序：时间复杂度为O(d*n)

1、插入排序（Insertion Sort）

1.1 直接插入排序（Straight Insertion Sort）

直接插入排序是将一个记录插入到已排好序的有序表中，从而得到一个记录数加1的新有序表。

#include <stdlib.h>
#include <iomanip>
#include <iostream>
using namespace std;

typedef int KeyType, InfoType;

//记录类型
struct Record{
	KeyType key;
	InfoType otherinfo;
};

//待排序的 序列
#define MAXSIZE 20	//序列长度
struct SqList{
	Record Sq[MAXSIZE+1];	//将Sq[0]作为哨兵
	int length;
};

//随机初始化一个序列（待排序）
void Initialize_List(SqList &L){
	for(int i=1; i<=L.length; i++)
		L.Sq[i].key = 1+(int)(100.0*rand()/(RAND_MAX+1.0));	//关键字的值在100以内
}

//打印序列
void Print_List(SqList &L){
	for(int i=1; i<=L.length; i++){
		cout<<L.Sq[i].key<<setw(5);
	}
	cout<<endl;
}

//直接插入排序
void InsertSort(SqList &L){
	int i,j;
	for(i=2; i<=L.length; i++){		//将L.Sq[1]看作一个已排好序的序列
		if(L.Sq[i-1].key > L.Sq[i].key){
			L.Sq[0] = L.Sq[i];			//保存第i个记录
			L.Sq[i] = L.Sq[i-1];		//后移第i-1个记录
			for(j=i-2; L.Sq[j].key>L.Sq[0].key; j--)			//寻找插入位置j
				L.Sq[j+1] = L.Sq[j];	//将比第i个记录大的所有记录依次往后移动一个位置
			L.Sq[j+1] = L.Sq[0];		//插入新纪录
		}
	}
}



int main(){
	//生成一个伪随机序列
	SqList L;
	L.length = MAXSIZE;
	Initialize_List(L);
	Print_List(L);
	//排序后
	InsertSort(L);
	Print_List(L);

	return 0;
}

结果：

1   57   20   81   59   48   36   90   83   75   18   86   72   52   31    2   10   37   15   17
1    2   10   15   17   18   20   31   36   37   48   52   57   59   72   75   81   83   86   90

代码说明：如果待排序序列中有n个记录，则整个排序过程执行n-1趟插入。即：先将第1个记录看成是一个有序的子序列，然后从第2个记录开始逐个进行插入，直至整个序列变成按关键字非递减的有序序列为止。显然，直接插入排序的时间复杂度为O(n^2)，且插入排序是原地排序、稳定排序。

1.2 折半插入排序（Binary Insertion Sort）

直接插入排序在序列长度n很大时效率很低，在一个有序序列中插入一个新纪录，需要将该记录和序列中的已有纪录顺序两两比较，以确定新纪录的插入位置。在寻找新纪录的插入位置时候，我们可以采用二分法查找算法。注意：折半插入减少了关键字间的比较次数，但纪录的移动次数不变，因此，折半插入的时间复杂仍为O(n^2)。

//折半插入排序
void BinInsertSort(SqList &L){
	int low, high, mid;					//low,high标记插入区间
	for(int i=2; i<=L.length; i++){		//将L.Sq[1]看作一个已排好序的序列，从2个记录开始插入
		low = 1;
		high = i-1;
		while(low <= high){
			mid = (low+high)/2;
			if(L.Sq[mid].key > L.Sq[i].key)
				high = mid - 1;
			else low = mid + 1;
		}

		L.Sq[0] = L.Sq[i];				//保存待插入的新纪录到Sq[0]处
		for(int k=i-1; k>=high+1; k--)	//high后面的记录后移一个位置
			L.Sq[k+1] = L.Sq[k];
		L.Sq[high+1] = L.Sq[0];			//插入新纪录
	}
}

1.3 希尔排序（Shell's Sort）

从对直接插入排序的分析得知，其算法时间复杂度为O(n^2)，但是，若待排记录序列为“正序”时，其时间复杂度可提高至O(n)。由此可设想，若待排记录序列按关键字“基本有序”时，直接插入排序的效率就可大大提高。另一方面，由于直接插入排序算法简单，则在n值很小时效率也比较高。希尔排序正是从这两点分析出发对直接插入排序进行改进得到的一种算法，其时间复杂度为O(n^a)，其中1<a<2。并且希尔排序是非稳定排序、原地排序。
希尔排序又称为“缩小增量排序”（Diminishing Increment Sort），它的基本思想是：先将整个待排记录序列分割为若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。注意：子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。例如，如果增量为5，则待排记录序列中的{a1, a6, a11……}、(a2, a7, a12……)都构成一个子序列，我们分别对每个增量为5的子序列进行直接插入排序；然后缩小增量，最后分别对增量为1的所有子序列进行直接插入排序，并完成整个排序过程。

//一趟Shell排序，前后记录位置的增量是dk，而不是1
void ShellInsert(SqList &L, int dk){
	int i,j;
	for(i=dk+1; i<=L.length; i++){			//将L.Sq[i-dk]看作一个已排好序的序列
		if(L.Sq[i-dk].key > L.Sq[i].key){
			L.Sq[0] = L.Sq[i];			//暂存第i个记录
			for(j=i-dk; L.Sq[j].key>L.Sq[0].key && j>0; j-=dk)			//寻找插入位置j
				L.Sq[j+dk] = L.Sq[j];	//将比第i个记录大的所有记录依次往后移动一个位置
			L.Sq[j+dk] = L.Sq[0];		//插入新纪录
		}
	}
}

//按增量序列dlta[0..t-1]对顺序表做希尔排序
void ShellSort(SqList &L, int dlta[], int t){
	for(int k=0; k<t; k++)
		ShellInsert(L, k);
}

2、快速排序（Quick Sort）

2.1 冒泡排序（Bubble Sort）

第 1 躺冒泡排序是从第1个记录到第n个记录，依次比较 第一个记录和第二记录（逆序则交换），第二个记录和第三个记录……，最后会将最大的记录换到最后一个位置上。
第 2 躺冒泡排序是从第1个记录到第n-1个记录，依次比较 第一个记录和第二记录（逆序则交换），第二个记录和第三个记录……，最后会将次最大的记录换到倒数第二个位置上。
第 m 躺冒泡排序是依次两两比较从第1个记录到第n-m+1个记录，并将整个序列中第m大的记录放到序列中的倒数第m个位置上去。经过n-1躺冒泡排序，就得到一个完整的有序序列。
冒泡排序的时间复杂度为O(n^2)，且也是稳定排序、原地排序。

//交换两个记录
void swap(Record &r1, Record &r2){
	Record tmp;
	tmp = r1;
	r1 = r2;
	r2 = tmp;
}

//冒泡排序
void BubbleSort(SqList &L){
	int m, n;
	bool isOK = false;							//哨兵，用于提前结束冒泡排序

	for(m=1; m<=L.length-1 && !isOK; m++){		//第m躺将第m大的记录放到倒数第m个位置上
		isOK = true;							//假定该趟排序能够完成
		for(n=2; n<=(L.length-m+1); n++)
			if(L.Sq[n].key < L.Sq[n-1].key){	//交换两个相邻的逆序记录
				swap(L.Sq[n-1], L.Sq[n]);
				isOK = false;					//如果发生了记录交换的事件，就认为排序未完成
			}
	}
}

代码说明：如果初始序列恰好已经是非递减序列了，则只需进行一趟排序。可见冒泡排序并不一定要走完所有n-1躺才能排好，所以上面的代码中设置了一个哨兵，来检测能够提前完成的冒泡排序。

2.2 快速排序（Quick Sort）

快速排序是对冒泡排序的一种改进，它的基本思想是：通过一趟排序将待排记录序列分割成两个独立的部分，其中一部分记录的关键字均比另一部分记录的关键字小（以支点记录来划分），则可分别对这两部分记录继续进行排序，以达到整个序列有序。
一趟快速排序的具体做法是：附设两个指针low和 high，设支点记录（pivot）的关键字为pivotkey，则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录并和支点记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和支点记录互相交换，重复这两步直至low=high为止。

//快速排序
int Partition(SqList &L, int low, int high){
	KeyType pivotkey = L.Sq[low].key;
	while(low < high){
		while(low<high && L.Sq[high].key>=pivotkey) high--;	//从high起向前搜索，找到第一个小于支点记录的位置
		swap(L.Sq[low],L.Sq[high]);
		while(low<high && L.Sq[low].key<=pivotkey) low++;	//从 low其向后搜索，找到第一个大于支点记录的位置
		swap(L.Sq[low],L.Sq[high]);
	}
	return low;	//返回支点记录所在的位置
}

//对子序列[low high]进行快速排序（递归实现）
void QuickSort(SqList &L, int low, int high){
	KeyType pivotkey;
	if(low < high){
		pivotkey = Partition(L, low, high);
		QuickSort(L, low, pivotkey-1);
		QuickSort(L, pivotkey+1, high);
	}
}

代码说明：上面在一趟快速排序的过程中，每交换一对记录（调用swap函数）需要进行3次赋值操作，而实际上，在排序过程中对支点记录的赋值时多余的，因为只有在一趟排序结束时，即low=high的位置才是支点记录的最后位置。由此Partition函数可以改写为下面的形式，先将支点记录暂存在L.Sq[0]的位置上，直至一趟排序结束后再将支点记录移至正确的位置上。

int Partition_Improved(SqList &L, int low, int high){
	KeyType pivotkey = L.Sq[low].key;
	L.Sq[0] = L.Sq[low];	//暂存支点记录
	while(low < high){
		while(low<high && L.Sq[high].key>=pivotkey) high--;	//从high起向前搜索，找到第一个小于支点记录的位置
		L.Sq[low] = L.Sq[high];
		while(low<high && L.Sq[low].key<=pivotkey) low++;	//从 low其向后搜索，找到第一个大于支点记录的位置
		L.Sq[high] = L.Sq[low];
	}
	L.Sq[low] = L.Sq[0];	//还原支点记录到位
	return low;	//返回支点记录所在的位置
}

3、选择排序（Selection Sort）

3.1 简单选择排序（Simple Selection Sort）

选择排序的基本思想是：第 m 躺选择排序是遍历从第m个记录到第n个记录的子序列，并将整个序列中第m小的记录放到序列中的第m个位置上去。经过n-1躺选择排序，就得到一个完整的有序序列。
与冒泡排序相比，选择排序是找到关键字最小的记录并交换到相应的位置上；而冒泡排序是找到关键字最大的记录并交换到相应的位置上。

与插入排序相比，选择排序是确定一个位置的记录；而插入排序是确定一个记录的位置。
简单选择排序的时间复杂度为O(n^2)，且也是稳定排序、原地排序。

//简单选择排序
void SimpleSelectionSort(SqList &L){
	int index;
	for(int i=1; i<L.length; i++){
		index = i;		//index为关键字最小值记录对应的索引值
		for(int j=i+1; j<L.length-1; j++)
			if(L.Sq[j].key < L.Sq[index].key)
				index = j;
		if(i != index)
			swap(L.Sq[i], L.Sq[index]);
	}
}

3.2 堆排序（Heap Sort）

4、归并排序（Merging Sort）

归并的含义是将两个或两个以上的有序表组合成一个新的有序表。利用归并的这种思想很容易实现排序：假设待排记录序列有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列（[ ]表示向上取整）；再两两归并，如此重复，直到得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。注意：归并排序的时间复杂度为O(n*logn)，并且它是一种稳定排序，但不是原地排序。

//将序列SR的两个相邻子序列SR[m,...,k]和SR[k+1,...,n]归并为有序的TR[m,...,n]
void Merge(Record SR[], Record TR[], int m, int k, int n){
	int i, j;
	//m遍历序列SR[m,...,k]，j遍历序列SR[k+1,...,n]，i遍历序列TR
	for(i=m, j=k+1; m<=k && j<=n; i++){
		if(SR[m].key <= SR[j].key)
			TR[i] = SR[m++];
		else
			TR[i] = SR[j++];
	}
	while(m <= k)TR[i++] = SR[m++];	//将剩余的SR[m,...,k]复制到TR中
	while(j <= n)TR[i++] = SR[j++];	//将剩余的SR[j,...,n]复制到TR中
}

//将序列SR[s,...,t]归并排序为TR1[s,...,t]
void MSort(Record SR[], Record TR1[], int s, int t){
	int mid;
	Record TR2[MAXSIZE+1];			//辅助存储空间
	if(s == t) TR1[s] = SR[s];
	else {
		mid = (s+t)/2;				//将序列两等分
		MSort(SR, TR2, s, mid);		//递归地将SR[s,...,mid]归并为有序的TR2[s,...,mid]
		MSort(SR, TR2, mid+1, t);	//递归地将SR[mid+1,...,t]归并为有序的TR2[mid+1,...,t]
		Merge(TR2, TR1, s, mid, t);	//将TR2[s,...,mid]和TR2[mid+1,...,t]归并到TR1[s,...,t]
	}
}

//2-路归并排序
void MergeSort(SqList &L){
	MSort(L.Sq, L.Sq, 1, L.length);
}

值的注意的是：归并排序需要进行[logn]躺（[ ]表示向上取整），实现归并排序需要和待排记录数量相等的辅助存储空间（非原地排序）。此外，递归形式的算法在形式上简洁，但实用性很差，为了效率通常要采用其非递归形式的算法。

5、基数排序（Radix Sorting）

前面讨论的各类排序方法都是通过关键字之间的比较和移动记录这两种操作来实现的，基数排序是一种完全不同的排序方法。基数排序是借助多关键字排序思想对单逻辑关键字进行排序的方法。

6、总结

综合比较本文所讨论的各种内部排序算法，大致有如下结果：

(1) 上表中的简单排序包括除希尔排序之外的所有插入排序、冒泡排序和简单选择排序，其中以直接插入排序为最简单，当序列中的记录“基本有序”或n值较小时，它是最佳排序方法。
(2)从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。而后两者相比的结果是，在n较大时，归并排序所需时间较堆排序省，但它所需的辅助存储量最多。
(3) 基数排序适用于n值很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的“最高位关键字”均不同，则亦可先按“最高位关键字”不同将序列分成若干“小”的子序列，而后进行直接插入排序。
(4) 从方法的稳定性来比较，所有时间复杂度为O(n^2)的简单排序法也是稳定的，然而，快速排序、堆排序和希尔排序等时间性能较好的排序方法都是不稳定的。


To be continued....