gpt4 book ai didi

c++ - 难以理解的简单递归排序算法

转载 作者:太空狗 更新时间:2023-10-29 20:13:34 25 4
gpt4 key购买 nike

#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的修改版本以第一个元素为基准。

该算法主要执行以下操作:

它有两个指针,i0 开始, 和 jlength-1 开始.

它一直递减j直到a[j] < a[i] .此时它交换它们的值。
在此之后,j保持在那个值,i再次开始递增,直到 a[j] < a[i] .此时它再次交换它们的值,现在再次交换 j开始递减。

因此,如果您看到,每次比较都是针对第一个元素进行的。循环结束后,第一个元素出现在正确的位置。

关于c++ - 难以理解的简单递归排序算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20548996/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com