排序:是将一批(组)任意次序的记录重新排列成按关键字有序的记录序列的过程。关键字可以是记录的主关键字,也可以是次关键字或若干数据项的组合。

内部排序:在排序过程中,若整个数据表都是存放在内存中处理,排序时不涉及数据的内、外存交换。

外排序:排序过程中要进行数据的内、外存交换。

内部排序的分类:是否基于关键字的比较,分为基于比较的排序算法和不基于比较的排序。(插入排序、交换排序、选择排序和归并排序都是基于比较的排序算法。基数排序是不基于比较的排序算法。)

算法的稳定性:如果待排序的表中,存在有多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,称这种排序方法是稳定的;反之,若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。

正序:待排序记录的关键字顺序正好和要排序顺序相同。

反序:若待排序记录的关键字顺序正好和要排序顺序相反。

评价排序算法的标准:执行时间和所需的辅助空间,其次是算法的稳定性。时间是由比较和移动的次数之和确定的,两个记录的一次交换一般需要3次移动。

插入排序

插入排序:每一趟将一个待排序的记录,按其关键字值的大小插入到已经排序的部分文件中适当位置上,直到全部插入完成。

直接插入排序:依次将每个记录插入到一个有序的序列中去。初始时,有序区只有一个元素R[0],i=1~n-1,共经过n-1趟排序。

代码实现:

// ------ 待排记录的数据类型--------
#define MAXSIZE 20 // 一个用作示例的小顺序表的最大长度
typedef int KeyType; // 定义关键字类型为整型
typedef struct { // 记录类型
	KeyType key; // 关键字项
	InfoType otherinfo; // 其它数据项,具体类型在主程中定义
} RedType;
typedef struct { // 顺序表类型
	RedType r[MAXSIZE + 1]; // r[0]闲置或用作哨兵单元
	int length; // 顺序表长度
} SqList;

void InsertSort(RedType R[], int n)
{
	int i, j;
	RedType tmp;
	for (i=1;i<n;i++){ //从第二个元素即R[1]开始的
		if (R[i-1].key>R[i].key){ 
			tmp=R[i]; //取出无序区的第一个元素R[i]
			j=i-1; //在R[0..i-1]中找R[i]的插入位置
			do{ 
				R[j+1]=R[j]; //将关键字大于tmp.key的元素后移
				j--; //继续向前比较
			} while (j>=0 && R[j].key>tmp.key);
			R[j+1]=tmp; //在j+1处插入R[i]
		}
	}
}

//设置哨兵
void InsertSort(SqList &L)
{
	// 对顺序表L作直接插入排序。算法10.1
	int i, j;
	for(i = 2; i <= L.length; ++i)
		// "<",需将L.r[i]插入有序子表
		if (LT(L.r[i].key, L.r[i - 1].key)) {
			L.r[0] = L.r[i]; // 复制为哨兵
			for(j = i - 1; LT(L.r[0].key, L.r[j].key); --j)
				L.r[j + 1] = L.r[j]; // 记录后移
			L.r[j + 1] = L.r[0]; // 插入到正确位置
		}
}

折半插入排序:有序区的有序性。可以采用折半查找方法先在R[0..i-1]中找到插入位置,再通过移动记录进行插入。这样的插入排序称为折半插入排序或二分插入排序。折半插入排序的元素移动次数与直接插入排序相同,不同的仅是变逐个移动为集中移动。

代码实现:

void binSort(RedType a[],int n)//按递增序进行二分法插入排序
{
	int i,j,left,mid,right;
	for (i=1;i<n;i++){
		left=0;right=i-1; 循环寻找位置
		while (left<=right){
			mid=(left+right)/2;
			if (a[i].key<a[mid].key)
				right=mid-1;
			else
				left=mid+1;
		}
		for(j=i-1;j>=left;j--)
			a[j+1]=a[j];//将排序大于ki 的记录后移插入
		if(left!=i) 
			a[left]=a[i];
	}
}

希尔排序:(缩小增量排序)先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序。然后取第二个增量d2(<d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。

代码实现:

//取d1= n/2,di+1=⌊di/2⌋时
void ShellSort(RedType R[],int n)
{
	int i,j,d;
	RedType tmp;
	d=n/2; //增量置初值
	while (d>0){ 
		for (i=d;i<n;i++){ 
			tmp=R[i]; //对所有相隔d位置的记录组采用直接插入排序
			j=i-d;
			while (j>=0 && tmp.key<R[j].key){
				R[j+d]=R[j];
				j=j-d;
			}
			R[j+d]=tmp;
		}
		d=d/2; //减小增量
	}
}
void ShellInsert(SqList &L, int dk)
{
	// 对顺序表L作一趟希尔插入排序。本算法是和一趟直接插入排序相比,
	// 作了以下修改:
	// 1.前后记录位置的增量是dk,而不是1;
	// 2.r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。算法10.4
	int i, j;
	for(i = dk + 1; i <= L.length; ++i)
		if (LT(L.r[i].key, L.r[i - dk].key) ) {
			// 需将L.r[i]插入有序增量子表
			L.r[0] = L.r[i]; // 暂存在L.r[0]
			for(j = i - dk; j > 0 && LT(L.r[0].key, L.r[j].key); j -= dk)
				L.r[j + dk] = L.r[j]; // 记录后移,查找插入位置
			L.r[j + dk] = L.r[0]; // 插入
		}
}

交换排序

交换排序:交换排序是一类基于“交换”的排序,系统地交换反序的记录的偶对,直到不再有这样的偶对为止。交换排序的基本思路:两两比较待排序记录的关键字,并交换不满足次序要求的那些偶对,直到全部满足为止。

冒泡排序:设待排序记录序列中的记录个数为n。最多作n-1 趟冒泡,i = 1, 2, 。。, n-1。在第i 趟中从后向前,j = n-1, n-2, 。。, i,顺次两两比较r[j-1].key和r[j].key。如果发生逆序,即r[j-1].key>r[j].key ,则交换r[j-1].key和r[j].key。

代码实现:

void BubbleSort(RedType R[],int n)
{ 
	int i,j,exchange;
	RedType tmp;
	for(i=0;i<n-1;i++){
		exchange=0; //本趟排序前置exchange为0
		for (j=n-1;j>i;j--) //比较,找出最小关键字的记录
			if(R[j].key<R[j-1].key){
				tmp=R[j]; //R[j]与R[j-1]进行交换,
				R[j]=R[j-1]; //将最小关键字记录前移
				R[j-1]=tmp;
				exchange=1; //本趟排序发生交换置exchange为1
			}
		if (exchange==0) //本趟未发生交换时结束算法
			return;
	}
}

快速排序:找一个记录(例如取第一个记录) ,以它的关键字作为“枢轴”(基准);凡其关键字小于枢轴的记录均移动至该记录之前;凡其关键字大于枢轴的记录均移动至该记录之后。即对无序的记录序列进行“一次划分”,之后分别对分割所得两个子序列“递归”进行快速排序。

代码实现:

int Partition(SqList &L, int low, int high)
{
	// 交换顺序表L中子表r[low..high]的记录,枢轴记录到位,并返回其
	// 所在位置,此时在它之前(后)的记录均不大(小)于它。算法10.6(b)
	KeyType pivotkey;
	L.r[0] = L.r[low]; // 用子表的第一个记录作枢轴记录
	pivotkey = L.r[low].key; // 枢轴记录关键字
	while(low < high) {
		// 从表的两端交替地向中间扫描
		while(low < high && L.r[high].key >= pivotkey)
			--high;
		L.r[low] = L.r[high]; // 将比枢轴记录小的记录移到低端
		while(low < high && L.r[low].key <= pivotkey)
			++low;
		L.r[high] = L.r[low]; // 将比枢轴记录大的记录移到高端
	}
	L.r[low] = L.r[0]; // 枢轴记录到位
	return low; // 返回枢轴位置
}
void QSort(SqList &L, int low, int high)
{
	// 对顺序表L中的子序列L.r[low..high]作快速排序。算法10.7
	int pivotloc;
	if(low < high) { // 长度大于1
		// 将L.r[low..high]一分为二
		pivotloc = Partition(L, low, high);
		// 对低子表递归排序,pivotloc是枢轴位置
		QSort(L, low, pivotloc - 1);
		QSort(L, pivotloc + 1, high); // 对高子表递归排序
	}
}
void QuickSort(SqList &L)
{
	// 对顺序表L作快速排序。算法10.8
	QSort(L, 1, L.length);
}

选择排序

选择排序:每一趟(例如第i 趟, i = 1, …, n-1) 在后面n-i+1 个待排序记录序列中选出关键字值最小的记录,作为有序记录序列的第i 个记录。待到第n-1 趟作完,待排序记录只剩下1 个, 就不用再选了。选择排序的每一趟可把有序区扩大,直到n-1趟后即可把有序区扩大到整个待排序序列。

简单选择排序:在一组记录r[i]~r[n] 中选择具有最小关键字的记录;若它不是这组记录中的第一个记录,则将它与这组记录中的第一个记录对调;在这组记录中剔除这个具有最小关键字值的记录。在剩下的记录r[i+1]~r[n] 中重复执行前两步,直到剩余记录只有一个为止。

代码实现:

int SelectMinKey(SqList L, int i)
{
	// 返回在L.r[i..L.length]中key最小的记录的序号
	KeyType min;
	int j, k;
	k = i; // 设第i个为最小
	min = L.r[i].key;
	for(j = i + 1; j <= L.length; j++)
		if(L.r[j].key < min) { // 找到更小的
			k = j;
			min = L.r[j].key;
		}
	return k;
}
void SelectSort(SqList &L)
{
	// 对顺序表L作简单选择排序。算法10.9
	int i, j;
	RedType t;
	for(i = 1; i < L.length; ++i) { //选择第i小的记录,并交换到位
		// 在L.r[i..L.length]中选择key最小的记录
		j = SelectMinKey(L, i);
		if(i != j) { //与第i个记录交换
			t = L.r[i];
			L.r[i] = L.r[j];
			L.r[j] = t;
		}
	}
}

树型排序:又称锦标赛排序。对n 个记录的关键字进行两两比较,然后再[n/2]个较小者之间再进行两两比较,如此重复,直至选出最小关键字的记录为止。这个过程可用一棵有n 个叶子结点的完全二叉树表示。

堆:若将该记录序列视作完全二叉树,则:r2i 是ri 的左孩子;r2i+1 是ri 的右孩子。

堆排序:对树型排序的进一步改进。是利用堆的特性对记录序列进行排序。堆排序采用堆结构选择最大(最小)元素。如果每个结点的关键字均大于等于其所有孩子结点的关键字,称为大根堆。如果每个结点的关键字均小于等于其所有孩子结点的关键字,称为小根堆。

  • 从最后一个分支结点(编号为n/2)开始到根结点(编号为1)通过多次调用筛选算法建立初始堆。
  • 将R[1](无序区中最大记录)与无序区最后一个记录交换,归位无序区最后一个记录,无序区减少一个记录。
  • 再筛选,重复进行,直到无序区只有一个记录。

代码实现:

typedef SqList HeapType; // 堆采用顺序表存储表示
//调整堆
void HeapAdjust(HeapType &H, int s, int m)
{ 
	// 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义,本函数
	// RedType rc;调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言)。算法10.10
	int j;
	rc = H.r[s];
	for(j = 2 * s; j <= m; j *= 2) {
		// 沿key较大的孩子结点向下筛选
		if(j < m && LT(H.r[j].key, H.r[j + 1].key))
			++j; // j为key较大的记录的下标
		if(!LT(rc.key, H.r[j].key))
			break; // rc应插入在位置s上
		H.r[s] = H.r[j];
		s = j;
	}
	H.r[s] = rc; // 插入
}

void HeapSort(HeapType &H)
{
	// 对顺序表H进行堆排序。算法10.11
	RedType t;
	int i;
	// 把H.r[1..H.length]建成大顶堆
	for(i = H.length / 2; i > 0; --i)
		HeapAdjust(H, i, H.length);
		// 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换
	for(i = H.length; i > 1; --i) {
		t = H.r[1];
		H.r[1] = H.r[i];
		H.r[i] = t;
		HeapAdjust(H, 1, i - 1); // 将H.r[1..i-1]重新调整为大顶堆
	}
}

归并排序

归并排序:通过“归并”两个或两个以上的记录有序子序列,逐步增加记录有序序列的长度。多次将两个或两个以上的有序表合并成一个新的有序表。通常采用的是2-路归并排序。即:将两个位置相邻的记录有序子序列归并为一个记录的有序序列。

代码实现:

void Merge(RedType SR[], RedType TR[], int i, int m, int n)
{
	// 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12
	int j, k, l;
	// 将SR中记录由小到大地并入TR
	for(j = m + 1, k = i; i <= m && j <= n; ++k)
		if LQ(SR[i].key, SR[j].key)
			TR[k] = SR[i++];
		else
			TR[k] = SR[j++];
	if(i <= m)
		for(l = 0; l <= m - i; l++)
			TR[k + l] = SR[i + l]; // 将剩余的SR[i..m]复制到TR
	if(j <= n)
		for(l = 0; l <= n - j; l++)
			TR[k + l] = SR[j + l]; // 将剩余的SR[j..n]复制到TR
}
void MSort(RedType SR[], RedType TR1[], int s, int t)
{
	// 将SR[s..t]归并排序为TR1[s..t]。算法10.13
	int m;
	RedType TR2[MAX_SIZE + 1];
	if(s == t)
		TR1[s] = SR[s];
	else {
		m = (s + t) / 2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t]
	// 递归地将SR[s..m]归并为有序的TR2[s..m]
	MSort(SR, TR2, s, m);
	// 递归地将SR[m+1..t]归并为有序的TR2[m+1..t]
	MSort(SR, TR2, m + 1, t);
	// 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]
	Merge(TR2, TR1, s, m, t);
	}
}
void MergeSort(SqList &L)
{
	// 对顺序表L作归并排序。算法10.14
	MSort(L.r, L.r, 1, L.length);
}

基数排序

基数排序:采用“分配”与“收集”的办法,用对多关键字进行排序的思想实现对单关键字进行排序的方法。

两种常用方法:最高位优先MSD (Most Significant Digit first )、最低位优先LSD (Least Significant Digit first)

最高位优先法:

  • 先根据最高位关键字K1排序, 得到若干元素组,元素组中各元素都有相同关键字K1。
  • 再分别对每组中元素根据关键字K2 进行排序,按K2 值的不同, 再分成若干个更小的子组, 每个子组中的元素具有相同的K1和K2值。
  • 依此重复, 直到对关键字Kd完成排序为止。
  • 最后, 把所有子组中的元素依次连接起来,就得到一个有序的元素序列。

最低位优先法

  • 首先依据最低位关键字Kd对所有元素进行一趟排序;再依据次低位关键字Kd-1对上一趟排序的结果再排序,依次重复,直到依据关键字K1最后一趟排序完成,就可以得到一个有序的序列。
  • 这种排序方法对每个关键字进行排序时,不需要再分组,而是整个元素组都参加排序。

链式基数排序:是典型的LSD排序方法, 利用“分配”和“收集”对单关键字进行排序。在这种方法中,把单关键字Ki 看成是一个d 元组。其中的每一个分量也可看成是一个关键字。分量有radix 种取值, 称radix 为基数。基数排序以静态链表作为它们的存储结构。

代码实现:

typedef struct node{ 
	int key;
	anytype data;
	int *next;
}List_Node;

List_Node *radixsort( List_Node *h,int d,int r)
{ 
	n=10; m=1;
	for(i=1; i<=d;i++){ //共“分配”、“收集”d 次
		for(j=0;j<=9;j++){ //初始化队列
			f[j]=NULL;t[j]=NULL;
		}
		p=h;
		while(p) {
			k=p->key%n/m // “分离”
			if(f[k]==NULL) f[k]=p; //入队
			else t[k]->next=p;
			t[k]=p;
			p=p->next; //从单链表中获取下一个结点
		}
		m=m*10; n=n*10;
		h=NULL; p=NULL; //“收集”
		for(j=0;j<r;j++)
			if (f[j]) {
				if (!h) { 
					h=f[j];
					p =t[j]; 
				}else {
					p->next=f[j];p=t[j];
				}
			}
		}
	return(h);
}
时间复杂度
最好情况最坏情况平均情况空间复杂度稳定性
直接插入排序O(n)O(n2)O(n2)O(1)稳定
折半插入排序O(n)O(n2)O(n2)O(1)稳定
希尔排序O(n3/2)O(1)不稳定
冒泡排序O(n)O(n2)O(n2)O(1)稳定
快速排序O(nlog2n)O(n2)O(nlog2n)O(log2n)不稳定
简单选择排序O(n2)O(n2)O(n2)O(1)不稳定
堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定
归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定
基数排序O(d(n+rd))O(d(n+rd))O(d(n+rd))O(rd)稳定

总结:

  1. 就平均时间性能而言,快速排序最佳。但在最坏情况下不如堆排序和归并排序。(归并排序对n较大时适用)
  2. 当序列中的记录“基本有序”或n 值较小时,直接插入排序是最佳的方法,因此常将它与其他排序方法结合使用,如快速排序、归并排序等。
  3. 基数排序的时间复杂度也可写成O(d*n),因此它最适用于n 值很大而关键字较小的序列。
  4. 稳定的排序方法:基数排序、简单排序。
  5. 不稳定的排序方法:快速排序、堆排序、希尔排序(时间性能较好)。
最后修改日期:2020年3月22日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据