学步园

快速排序算法的思想：

  1. 通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的记录的关键字小

  2. 然后分别对这两部分进行同样的操作 1 的快速排序，以达到整个序列有效

算法的例子如下：

int QuickSort(MergeType* L, int low, int high) 
{
	int nPivotLoc;
	if (!L->elem || low >= high)
	{
		return -1;
	}

	if (low < high)
	{
		nPivotLoc = PartitonEx(L, low, high);
		QuickSort(L, low, nPivotLoc-1);
		QuickSort(L, nPivotLoc+1, high);
	}
	return 0;
}

具体的排序算法：

/*快递排序：核心就是一定要跟轴心进行比较*/
int Partiton(MergeType* L, int low, int high)
{
	int nPivotKey = L->elem[low];
	while (low < high) //low = high 退出while循环
	{
		/*一旦下面的数据发生交换，说明当前的轴心已经位于低端位置；
		  如果大于pivot，high不用移动，继续往下比较；否则high与
		  low位置的数据交换
		 */
		while (low < high && nPivotKey <= L->elem[high]) high--; 
		swap(L->elem[high], L->elem[low]);

		/*一旦上面的数据发生交换，说明当前的轴心已经移动到高端位置；
		  如果小于pivot，low不用移动，继续往上比较；否则low与high
		  位置的数据交换
		 */
		while (low < high && nPivotKey >= L->elem[low]) low++;
		swap(L->elem[low], L->elem[high]);
	}
#ifdef _DEBUG
	printf("low:%d,high:%d \n", low, high);
#endif
	return low;
}

其他数据类型和函数的定义请参考上节：冒泡算法的改进

算法的时间复杂度：大牛数学家计算得到为O（nlogn）（具体可参考有关资料），平均性能较佳，若初始有序或者基本有序则会退化为冒泡算法

上面的算法每次不满足条件时都会交换数据，其实我们每次比较的都是轴心，而且我们在一趟排序完成后，才将轴心复制到坐在位置，因此可以在一趟完成后再将PrivoKey数据赋值到low=high的位置，如下算法：

int PartitonEx(MergeType* L, int low, int high)
{
	int nPivotKey = L->elem[low];
	while (low < high)
	{
		while (low < high && nPivotKey <= L->elem[high]) high--; 
		L->elem[low] = L->elem[high];

		while (low < high && nPivotKey >= L->elem[low]) low++;
		L->elem[high] = L->elem[low];
	}
	//low = high 退出上面while循环
	L->elem[low] = nPivotKey;
	return low;
}

测试用例可以参考上节：冒泡算法的改进 

算法改进的思考：

一 这里采用的递归的模式，一般递归会占用更多的栈空间，首先在第一次划分的时候会将数据压入栈，紧接着的再次递归会压入更多的数据，直至递归终止点。想到的第一就是减少辅助的栈存储空间。

二 就是这里采用的每次都是先从high方向，试想如果同时从high和low两方向同时进行，当然判断会更琐碎

三 每次比较采用的都是最左边的一个元素，如果采用其他元素会不会更好呢

四 能不能利用前次的比较结果，减少下一次的比较次数，那可能就是堆排序了，会有其他的吗？？

其他的方式都是数学家的事了，暂只是思考一下