簡單的遞歸排序算法，瞭解哪些硬

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個元素會在其正確的位置出現。從快速排序）感謝