排序算法-交换排序详解

交换排序基本思想

元素两两比较，如果发生逆序则交换，直到所有记录都排好序为止。

常见的交换排序方法：
冒泡排序：O(n²)
快速排序：O(nlog₂n)

冒泡排序

冒泡排序(Bubble Sort)是一种最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换，从而使关键字小的记录如气泡一般逐渐往上 ＂漂浮＂（左移），或者使关键字大的记录如石块一样逐渐向下 ＂坠落”（右移）。

算法与过程

void BubbleSort(SqList &L) 
{	//对顺序表L做冒泡排序
	m=L.length-1;flag=1; 				// flag用来标记某一趟排序是否发生交换
	while ((m>O) && (flag==1)) 
	{
		flag=O; 						// flag置为0，如果本趟排序没有发生交换，则不会执行下一趟排序
		for(j =1; j<=m; j++) 
			if(L.r[j].key>L.r[j+1].key)
			{
				flag=1;					// flag置为1，表示本趟排序发生了交换
				t=L.r[j];L.r[j]=L.r[j+1];L.r[j+1]=t;	// 交换前后两个记录
			}
		--m;
	}
}

冒泡排序算法分析

最好情况（正序）

• 比较次数：n-1
• 移动次数：0

最坏情况（逆序）

对冒泡算法的评价：

• 冒泡排序最好时间复杂度是O(n)
• 冒泡排序最坏时间复杂度为O(n²)
• 冒泡排序平均时间复杂度为O(n²)
• 冒泡排序算法中增加一个辅助空间temp，辅助空间为S(n)=O(1)
• 冒泡排序是稳定的

快速排序

快速排序 (Quick Sort) 是由冒泡排序改进而得的。 在 冒泡排序过程中， 只对相邻的两个记录进行比较， 因此每次交换两个相邻记录时只能消除一个逆序。 如果能通过两个（不相邻）记录的一次交换，消除多个逆序， 则会大大加快排序的速度。 快速排序方法中的一次交换可能消除多个逆序。

快速排序基本思想

• 任取一个元素（如：第一个）为中心（pivot：枢轴、中心点）；
• 所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；
• 对各子表重新选择中心元素并以此规则调整；
• 直到每个子表的元素只剩一个。

快速排序的过程

选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边。

每一趟的子表的形成是采用从两头向中间交替式逼近法；由于每趟中对各子表的操作都相似，可采用递归算法。

快速排序算法

int Partition(SqList &L, int low, int high) 
{	//对顺序表L中的子表r[low .. high]进行一趟排序，返回枢轴位置
	L.r[O]=L.r[low]; 							// 用子表的第一个记录做枢轴记录
	pivotkey=L.r[low].key; 						// 枢轴记录关键字保存在pivotkey中
	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[O];							// 枢轴记录到位
	return low;									// 返回枢轴位置
}

void QSort(SqList &L,int low,int high) 
{	// 调用前置初值： low=1; high=L.length; 
	// 对顺序表L中的子序列L.r[low .. high]做快速排序
	if(low<high) { 							// 长度大于1
		pivotloc=Partition(L, low, high); 	// 将L.r[low.. high] 一分为二，pivotloc是枢轴位置
		QSort(L, low, pivotloc-1); 			// 对左子表递归排序
		QSort (L, pivotloc+1, high); 		// 对右子表递归排序
	}
}

void QuickSort(SqList &L) 
{	//对顺序表L做快速排序
	QSort(L,1,L.length);
}

快速排序算法分析

时间复杂度：
平均计算时间是O(nlog₂n)；
Qsort()：O(log₂n)
Partition()：O(n)

空间复杂度：
快速排序不是原地排序，由于程序中使用了递归，需要递归调用栈的支持，而栈的长度取决于递归调用的深度。（即使不用递归，也需要用用户栈）。
在平均情况下，需要O(logn)的栈空间。
在最坏情况下：栈空间可达O(n)。

稳定性：
快速排序时一种不稳定的排序方法。

试对（90,85,79,74,68,50,46）进行快速排序的划分，你是否发现什么特殊情况？再对（46,50,68,74,79,85,90）进行快速排序划分呢？
由于每次枢轴记录的关键字都是大于其它所有记录的关键字，致使一次划分之后得到的子序列（1）的长度为0，这时已经退化成为没有改进措施的冒泡排序。

• 快速排序不适于对原本有序或基本有序的记录序列进行排序。
• 划分元素的选取是影响时间性能的关键。
• 输入数据次序越乱，所选划分元素值得随机性越好，排序速度越快，快速排序不是自然排序方法。
• 改变划分元素的选取方法，至多只能改变算法平均情况下的时间性能，无法改变最坏情况下的时间性能。即最坏情况下，快速排序的时间复杂性总是O(n²)。