void quick_sort(int q[], int l, int r)
{
//如果我们的区间里没有数,或者只有一个数就不用排序了
if (l >= r)
return;
int x = q[l], i = l - 1, j = r + 1;
while (l < r)
{
do i++; while (q[i] < x);
do i--; while (q[j] > x);
if (i < j)
//交换两个数 或c++里直接调用swap(q[i],q[j])
{
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
进一步讨论:
快速排序属于分治算法!
分治算法都有三步:
1.分成子问题。
2.递归处理子问题。
3.子问题合并。
如何证明
while循环结束后下面的式子成立?
注:q[l..j] <= x意为q[l],q[l+1]...q[j-1],q[j]的所有元素都<= x
证明如下
循环不变式:
1.初始化
循环开始之前,两个指针i,j均被初始化,均指向了边界的两侧。
其中
2.保持
执行循环体,所以i和j更新之后,下一次循环开始之前,循环不变式依然成立!
do i++; while (q[i] < x);
//会使得q[l...i-1]<=x,q[i]>=x
do i--; while (q[j] > x);
//会使得q[j+1...r]>=x,q[j]<=x;
if (i < j)
//交换两个数 或c++里直接调用swap(q[i],q[j])
{
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
//会使得q[l...i]<=x,q[j...r]>=x
void quick_sort(int q[], int l, int r)
{
if(l >= r) return;
int i = l - 1, j = r + 1, x = q[l + r + 1 >> 1];//注意是向上取整,因为向下取整可能使得x取到q[l]
while(i < j)
{
do i++; while(q[i] < x);
do j--; while(q[j] > x);
if(i < j) swap(q[i], q[j]);
}
quick_sort(q, l, i - 1), quick_sort(q, i, r);
}
完整代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r)
{
//如果我们的区间里没有数,或者只有一个数就不用排序了
if (l >= r)
return;
int x = q[l], i = l - 1, j = r + 1;
while (l < r)
{
do i++; while (q[i] < x);
do i--; while (q[j] > x);
if (i < j)
//交换两个数 或c++里直接调用swap(q[i],q[j])
{
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &q[i]);
}
quick_sort(q, 0, n-1);
for (int i = 0; i < n; i++)
{
printf("%d ", q[i]);
}
return 0;
}