题目描述
关于此算法有两个争议的点在于:
- 能不能不使用do while,如何转换为 while, 当然也是可以的,主要处理好边界就好。
对应情况:while (a[++i] < x);
- quick_sort(a, l, j) 和 quick_sort(a, j + 1, r),能否替换为 quick_sort(a, l, i) 和 quick_sort(a, i + 1, r) 的样式,其实是可以的。主要是替换好相应的边界情况就好了。
对应的i满足此等式:int bi = (i == j) ? i : (i - 1);
样例
输入
10
49 59 88 37 98 97 68 54 31 3
输出
3 31 37 49 54 59 68 88 97 98
算法1
第一点争议
C++ 代码
#include <algorithm>
#include <iostream>
using namespace std;
const int length = 1000005;
int a[length];
void quick_sort(int a[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = a[(l + r) >> 1];
while (l < r) {
while (a[++i] < x);
// do i++; while (a[i] < x);
while (a[--j] > x);
// do j--; while (a[j] > x);
if (i < j) swap(a[i], a[j]);
else break;
}
quick_sort(a, l, j), quick_sort(a, j + 1, r);
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
quick_sort(a, 0, n - 1);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}
算法2
第二点争议
C++ 代码
#include <algorithm>
#include <iostream>
using namespace std;
const int length = 1000005;
int a[length];
void quick_sort(int a[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = a[(l + r) >> 1];
while (l < r) {
do i++; while (a[i] < x);
do j--; while (a[j] > x);
if (i < j) swap(a[i], a[j]);
else break;
}
int bi = (i == j) ? i : (i - 1);
quick_sort(a, l, bi), quick_sort(a, bi + 1, r);
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
quick_sort(a, 0, n - 1);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}