简单的递归排序算法，了解哪些硬

Question

#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++）。

Answer 1

它是quicksort的修改版本，其第一个元素为pivot。

的算法基本上执行以下操作：

它有两个指针，i开始0，并开始length-1j。

它一直递减j直到a[j] < a[i]。此时它交换了他们的价值。
之后，j停留在该值，i开始再次递增，直到a[j] < a[i]。此时它再次交换了它们的值，现在再次开始递减。

因此，如果你看到，每一个比较正在做的第一个元素。循环结束后，第1个元素会在其正确的位置出现。从快速排序）感谢