快速排序 O(nlogn)~O(n^2)

前言

快速排序的基本思想是：通过一趟排序将要排序的数据分割成两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。

实现原理

找一个数作为基准数（也叫枢轴），把小于基数的数移到基数左边，大于基数的数移到基数右边。接着对这两个分区的数进行递归分组，直到每个分区只有一个或零个数为止。
基本思想代码实现如下：

void QuickSort(int* array,int left,int right)
{
	if(left >= right)//表示已经完成一个组
	{
		return;
	}
	int index = PartSort(array,left,right);//确定枢轴的位置
	QuickSort(array,left,index - 1);
	QuickSort(array,index + 1,right);
}

那么利用PartSort(array,left,right)函数是如何实现确定枢纽位置的功能的呢？
我们采用左右指针法。

左右指针法

1. 选取一个数组元素作为枢轴，一般取整组记录的第一个数/最后一个，这 里采用选取最后一个。
2. 设置两个变量left = 0;right = N - 1;
3. 从left一直向后走，直到找到一个大于枢轴的值，right从后至前，直至找到一个小于枢轴的值，然后交换这两个数。
4. 重复第三步，直到left和right相遇，这时将枢轴放置left的位置即可。

eg. a[5]={2,-3,9,1,-1}
step1: 取枢轴为**-1**，此时right=4 left=0
step2: left=0 元素2与right=1 元素-3 交换
step3:{-3，2，9，1，-1} 此时left=1 right=0
step4:将枢轴互换到left的位置,结果为{-3，-1，9，1，2}

代码实现如下：

int PartSort(int* array,int left,int right)
{
	int& key = array[right];
	while(left < right)
	{
		while(left < right && array[left] <= key)
		{
			++left;
		}//防止都小导致越界、相等不动
		while(left < right && array[right] >= key)
		{
			--right;
		}
		swap(array[left],array[right]);
	}
	swap(array[left],key);
	return left;
}

后记

参考资料