#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100000;
void sort(int* a, int lo, int hi)
{
int i = lo;
if (lo >= hi)
return;
for (int j = hi, mode = 1; i < j; mode > 0 ? j-- : i++)
if (a[i] > a[j])
{
swap(a[i], a[j]);
mode = -mode;
}
sort(a, lo, i - 1);
sort(a, i + 1, hi);
}
bool check(int* a)
{
for (int i = 1; i < N; i++)
if (a[i] < a[i - 1])
return false;
return true;
}
int main()
{
int a[N];
for (int i = 0; i < N; i++)
a[i] = (i * 17 + 107) % 10;
sort(a, 0, N - 1);
cout << (check(a) ? "correct" : "incorrect") << endl;
return 0;
}
我找到了这种排序算法,但是经过很长时间的尝试却无法理解。它看起来非常简单和简短。我认为可以通过不变量证明
a[lo:i]
的任何元素都小于a[j:hi]
的任何元素,但是我无法证明该语句在每次循环迭代之后都正确(在j--
或i++
之后)。 最佳答案
它是quicksort的修改版本,以1st元素为轴。
该算法基本上执行以下操作:
它有两个指针,从i
开始的0
和从j
开始的length-1
。
它会一直递减j
直到a[j] < a[i]
。此时,它交换它们的值。
此后,j
保持该值,并且i
开始再次递增,直到a[j] < a[i]
为止。此时,它再次交换它们的值,现在j
再次开始递减。
因此,如果您看到的话,每个比较都将与第一个元素进行。循环结束后,第一个元素将在其正确位置着陆。