第10章-内部排序-10.3-快速排序（由起泡排序衍生的）

利用关键字（key）对获取数据进行按某一规律列队，通常而言采用非递减顺序进行，快速排序是一种速度稍快的排序算法

起泡排序：

• 根据关键字，实现邻近的记录比较，并将关键字较大记录后移
• 重复若干次，直到一次中无后移操作

如何分析理解冒泡排序：

• 第一次将关键字最大的记录移到最后一个
• 第二次将关键字次大的记录移至倒数第二个
• 以此类推

时间复杂度：

• 最坏的情况下，需要重复排序（n-1）次
• 最坏的情况下，需要比较（n-1）+（n-2）+……+1=n*（n-1）/2
• 综上所述，时间复杂度为O（n*n）

相比较于“直接插入排序”、“折半插入排序”、并没有优化，<希尔排序>（没说，有兴趣可以看看），它的时间复杂度较优

快速排序：

采用枢轴（支点）进行递归排序的操作

• 建立枢轴，并将大于其值的记录移到右边，小于的移到左边
• 在上一次的基础上，改变枢轴，重复操作
• 直到完全有序

一次排序算法如下：

int Partition(OrderSqList& L, int low, int high)
{
	OrderKeyType pivotkey;
	L.r[0] = L.r[low];
	
	pivotkey = L.r[0].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;
}

画一个图，自己体会一下，就知道，只是个可行的方法，尽管这个算法比较不那么的直观，但是想法确实经典！

需要注意的是：

• 注意增加L.r[0]为暂存枢轴单元（）不计入长度length
• 循环操作注意length的取值是：包含有效数据位的长度

初始化一个既成记录序列：

OrderSqList L;
L.r[0] = { NULL,NULL };
L.r[1] = { 49,'7'};
L.r[2] = { 38,'1' };
L.r[3] = { 65,'2' };
L.r[4] = { 97,'3' };
L.r[5] = { 76,'4' };
L.r[6] = { 13,'5' };
L.r[7] = { 27,'6' };
L.length = 7;

排序与访问正确性：