设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为主元，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j；
快排的时间复杂度O(nlogn)
快排的非递归实现，主元并没有随机选取。
#include <stdlib.h>
#include <stdio.h>
#include <vector>
#include <stack>
int partition(int a[], int left, int right) //partition函数以第一个元素作为pivot
{
if(a == NULL) //做异常处理
return -1;
if(left >= right)
return -1; int X = a[left];
int i = left;
int j = right; while(i < j)
{
while(i < j && a[j] > X) //从最右边找到第一个小于pivot的元素
j--;
if(i < j) //因为上面的循环出来可能i == j，所以如果i < j再令a[i] = a[j] 且 i = i + 1;
a[i++] = a[j]; //因为第一个元素是pivot已经被记录为X了，所以数组可以看做有一个空位在a[first]（a[i])
while(i < j && a[i] <= X)
i++;
if(i < j)
a[j--] = a[i]; //因为a[j]已经在上面移到了a[first]，所以a[j]是一个空位，可以用a[i]赋值
}
a[i] = X;
return i;
} void stack_implement_quickSort(int a[], int left, int right)
//如果之前看懂了如何非递归先序遍历二叉树，这个程序应该很好理解
{
std::stack<std::pair<int, int> > s;
int mid = partition(a, left, right); if(mid == -1)
return;
if(left < mid-1)
{
s.push(std::make_pair(left, mid-1));
}
if(mid+1 < right)
{
s.push(std::make_pair(mid+1, right));
} while(!s.empty())
{
std::pair<int,int> topPair = s.top();
s.pop(); mid = partition(a, topPair.first, topPair.second); if(mid == -1)
return;
if(topPair.first < mid-1)
{
s.push(std::make_pair(topPair.first, mid-1));
}
if(mid+1 < topPair.second)
{
s.push(std::make_pair(mid+1, topPair.second));
}
}
} int main(){
int a[] = {1,2,9,2,2,2,2,3,10,4,5,7,4};
stack_implement_quickSort(a, 0, 12);
return 0;
} /*采用递归的方法
void quickSort(int a[], int p, int q){
if (p <= q){
int r = partition(a, p, q);
if(r == -1)
return;
quickSort(a, p, r-1);
quickSort(a, r+1,q);
}
} int main(){
int a[] = {1,2,9,2,2,2,2,3,10,4,5,7,4};
quickSort(a, 0, 12);
int i = 0;
}
*/
随机选取主元：
#include <stdlib.h>
#include <stdio.h> int partition(int a[], int p, int q){
int pivot = rand() % (q-p+1) + p;
int i = p;
int j = q;
int key = a[pivot]; while(i < j){ while(i < j && a[i] < key){
i++;
}
if(i < j){
a[pivot] = a[i];
a[i] = key;
pivot = i;
} while(i < j && a[j] >= key){
j--;
}
if(i < j){
a[pivot] = a[j];
a[j] = key;
pivot=j;
}
}
return pivot;
} void quickSort(int a[], int p, int q){
if (p <= q){
int r = partition(a, p, q);
quickSort(a, p, r-1);
quickSort(a, r+1,q);
}
} int main(){
int a[] = {1,2,9,2,2,2,2,3,10,4,5,7,4};
quickSort(a, 0, 12);
int i = 0;
}