【46期】盘点那些必问的数据结构算法题之快速排序
阅读本文大概需要 5 分钟。
来自：juejin.im/post/5bae28e35188255c6f1e2bb1
0 概述
划分：数组 A[p…r] 被划分为两个子数组 A[p…q-1] 和 A[q+1…r]，使得 A[p…q-1] 中每个元素都小于等于 A[q]，而 A[q+1…r] 每个元素都大于 A[q]。划分流程见下图。
解决：通过递归调用快速排序，对子数组分别排序即可。
合并：因为两个子数组都已经排好序了，且已经有大小关系了，不需要做任何操作。
https://github.com/shishujuan/dsalg/tree/master/code/alg/sort
1 朴素的快速排序
/**
* 快速排序-朴素版本
*/
void quickSort(int a[], int l, int u)
{
if (l >= u) return;
int q = partition(a, l, u);
quickSort(a, l, q-1);
quickSort(a, q+1, u);
}
/**
* 快速排序-划分函数
*/
int partition(int a[], int l, int u)
{
int i, q=l;
for (i = l+1; i <= u; i++) {
if (a[i] < a[l])
swapInt(a, i, ++q);
}
swapInt(a, l, q);
return q;
}
2 改进-双向划分的快速排序
/**
* 快速排序-双向划分函数
*/
int partitionLR(int a[], int l, int u, int pivot)
{
int i = l;
int j = u+1;
while (1) {
do {
i++;
} while (a[i] < pivot && i <= u); //注意i<=u这个判断条件，不能越界。
do {
j--;
} while (a[j] > pivot);
if (i > j) break;
swapInt(a, i, j);
}
// 注意这里是交换l和j，而不是l和i，因为i与j交叉后，a[i...u]都大于等于枢纽元t，
// 而枢纽元又在最左边，所以不能与i交换。只能与j交换。
swapInt(a, l, j);
return j;
}
/**
* 快速排序-双向划分法
*/
void quickSortLR(int a[], int l, int u)
{
if (l >= u) return;
int pivot = a[l];
int q = partitionLR(a, l, u, pivot);
quickSortLR(a, l, q-1);
quickSortLR(a, q+1, u);
}
3 继续改进—随机法和三数取中法取枢纽元
/**
* 随机选择枢纽元
*/
int pivotRandom(int a[], int l, int u)
{
int rand = randInt(l, u);
swapInt(a, l, rand); // 交换枢纽元到位置l
return a[l];
}
/**
* 三数取中选择枢纽元
*/
int pivotMedian3(int a[], int l, int u)
{
int m = l + (u-l)/2;
/*
* 三数排序
*/
if( a[l] > a[m] )
swapInt(a, l, m);
if( a[l] > a[u] )
swapInt(a, l, u);
if( a[m] > a[u] )
swapInt(a, m, u);
/* assert: a[l] <= a[m] <= a[u] */
swapInt(a, m, l); // 交换枢纽元到位置l
return a[l];
}
4 非递归写快速排序
/**
* 快速排序-非递归版本
*/
void quickSortIter(int a[], int n)
{
Stack *stack = stackNew(n);
int l = 0, u = n-1;
int p = partition(a, l, u);
if (p-1 > l) { //左半部分两个边界值入栈
push(stack, p-1);
push(stack, l);
}
if (p+1 < u) { //右半部分两个边界值入栈
push(stack, u);
push(stack, p+1);
}
while (!IS_EMPTY(stack)) { //栈不为空，则循环划分过程
l = pop(stack);
u = pop(stack);
p = partition(a, l, u);
if (p-1 > l) {
push(stack, p-1);
push(stack, l);
}
if (p+1 < u) {
push(stack, u);
push(stack, p+1);
}
}
}
推荐阅读：
微信扫描二维码，关注我的公众号
朕已阅 
评论