一、partition quicksort 分治+递归
快速排序一次划分算法伪代码:
将i和j分别指向待排序列最左记录与最右侧记录;
重复下述过程,直到i = j;
右侧扫描,j--,直到a[j] 表示前面已经排行
左侧扫描,直到a[i]>a[j],交换,j--; 表示前面已经排好
循环结束,i = j,返回i的位置.
二、快速排序可用于求第k个最大值
用O(n)的平均时间复杂度从无序数组中寻找第k大的值.和快排一样,这里也用到了分而治之的思想.思路是,首先对数组进行一次Partition,得到坐标nPos:
如果nPos+1 == k,返回array[nPos];
如果nPos+1 > k,对数组左半部分继续进行Partition;
如果nPos+1 < k, 对数组右半部分继续进行Partition.
// 利用Partition实现复杂度为O(n)的寻找数组中第K大的数
int GetArrayMaxK(int array[], int nStart, int nEnd, int k)
{
if (k <= 0)
{
throw;
}
int nPos = -1;
while (true)
{
nPos = Partition(array, nStart, nEnd);
if ((nPos+1) == k)
{
return array[nPos];
}else if ((nPos+1) > k)
{
nEnd = nPos - 1;
}else
{
nStart = nPos + 1;
}
}
}
三、partition进阶
荷兰国旗问题
（可以以红白蓝为数字代替，统计数字，重新分配）
一种思路
我们可以把数组分成三部分，前部（全部是0），中部（全部是1）和后部（全部是2）三个部分，每一个元素（红白蓝分别对应0、1、2）必属于其中之一。
将前部和后部各排在数组的前边和后边，中部自然就排好了。
设置两个指针begin指向前部（不是按0，1，2的个数区分的前后部）的末尾的下一个元素（相当于）（刚开始默认前部无0，所以指向第一个位置），end指向后部开头的前一个位置（刚开始默认后部无2，所以指向最后一个位置），然后设置一个遍历指针current，从头开始进行遍历。
（1）若遍历到的位置为1，则说明它一定属于中部，根据总思路，中部的我们都不动，然后current向前移动一个位置。
（2）若遍历到的位置为0，则说明它一定属于前部，于是就和begin位置进行交换，然后current向前移动一个位置，begin也向前移动一个位置（表示前边的已经都排好了）。
（3）若遍历到的位置为2，则说明它一定属于后部，于是就和end位置进行交换，由于交换完毕后current指向的可能是属于前部的，若此时current前进则会导致该位置不能被交换到前部，所以此时current不前进。而同1），end向前移动一个位置。
void quick(int a[], int first, int end)
{
int current=first;
int temp;
while (current <= end)
{
if (a[current] == 1)
{
current++;
}
else if (a[current] == 0)
{
temp = a[first];
a[first] = a[current];
a[current] = temp;
first++;
current++;
}
else if (a[current] == 2)
{
temp = a[end];
a[end] = a[current];
a[current] = temp;
end--;
}
}
}
三路快速排序
算法原理：使用三路划分策略对数组进行划分（也就是荷兰国旗问题，dutch national flag problem）。这个实现是对实现二的改进，它添加处理等于划分元素的值的逻辑，将所有等于划分元素的值集中在一起，并且以后都不会再对他们进行划分。本算法中使用四个标示值进行操作。使用left和right同时向中间遍历时，当left遇见等于划分元素时，就与iflag指向的值进行交换（iflag指向的当前值到最左端表示left在过程中遇见的等于划分元素的值部分），同理，右边也使用同样的逻辑完成对等于划分元素的处理。最后分别交换左右部分的相等值（left和iflag对应交换，right和rflag对应交换），由于需要返回两个标记值，所以将partition和quicksort合并成一个方法。
算法代码：
void quickSort_3(int *array, int l, int r) {
/**
* 由于三路划分中有可能有两个不同的划分点，所以不能
* 使用函数直接返回，这里将partition和quickSort驱动
* 程序结合成一个方法；
* */
if(l>=r) return;
/**
* 选择pivot划分元素，并将其与array[r]交换
* */
int pivot, temp;
pivot=l+rand()%(r-l+1);
temp=array[pivot];
array[pivot]=array[r];
array[r]=temp;
/**
* 双向扫描：
* left和right都为主动移动
* lflag和rflag为被动移动
* */
int left=l, lflag=l;
int right=r-1, rflag=r-1;
while(true) {
while(array[left]<=array[r] && left
/**
* 如果array[left]与pivot相等，则将其交换到
* lflag当前指向的元素
* */
if(array[left]==array[r]) {
temp=array[left];
array[left]=array[lflag];
array[lflag]=temp;
lflag++;
}
left++;
}
while(array[right]>=array[r] && right>=l) {
/**
* 如果array[right]与pivot相等，则将其交换到
* rflag当前指向的元素
* */
if(array[right]==array[r]) {
temp=array[right];
array[right]=array[rflag];
array[rflag]=temp;
rflag--;
}
right--;
}
if(left>=right) break;
/**
* 将左边大于pivot的元素与右边小于pivot的元素进行
* 交换
* */
temp=array[left];
array[left]=array[right];
array[right]=temp;
left++;right--;
}
/**
* 由于left和lflag指向的当前元素都是即将需要处理的元素，
* 也就是当处理结束之后，他们都需要左移一步才是已经处理好的
* 元素； 将等于pivot的元素交换到中间
* */
lflag--;left--;
while(lflag>=l) {
temp=array[left];
array[left]=array[lflag];
array[lflag]=temp;
left--;lflag--;
}
/**
* 由于right和rflag指向的当前元素都是即将需要处理的元素，
* 也就是当处理结束之后，他们都需要右移一步才是已经处理好的
* 元素；将等于pivot的元素交换到中间
* 注意：由于pivot本身也需要移动到中间，所以这里的判断条件
* 包含r
* */
rflag++;right++;
while(rflag<=r) {
temp=array[right];
array[right]=array[rflag];
array[rflag]=temp;
right++;rflag++;
}
/**
* 最终递归处理左右子序列部分
* */
quickSort_3(array, l, left);
quickSort_3(array, right, r);
}
int main() {
int array[]={2,5,8,2,1,6};
quickSort_3(array,0,5);
for(int i=0;i<6;i++)
printf("%d,",array[i]);
return 1;
}
存在问题：为什么要移动相等的值，代码未手动实现
四、优化
使用插入排序
在子序列比较小的时候，其实插排是比较快的，因为对于有序的序列，插排可以达到O(n)的复杂度，如果序列比较小，则和大序列比起来会更加有序，这时候使用插排效率要比快排高。其实现方法也很简单：快排是在子序列元素个数变成1是，才停止递归，我们可以设置一个阈值n，假设为5，则大于5个元素，子序列继续递归，否则选用插排。（其实在C++的STL中，归并算法就是采用了这个思路，当子序列小到一定程度的时候，直接选用插排对子序列进行排序）
快排是在待排数列越趋近于有序时变得越慢，复杂度越高，调用插排可以很好的解决这个问题。
