C++ QuickSort not clear

Question

我想了解quicksort機制，但到目前爲止我無法弄清楚。根據維基百科，步驟如下：

1.從列表中選取一個稱爲數據透視表的元素。

2.重新排序列表，以便其值小於樞軸的所有元素的支點來之前，同時與價值比支點來後，更大的所有元素（等於值可以去任何一種方式）。分區之後，樞軸處於最終位置。這被稱爲分區操作。

3.將上述步驟遞歸地應用於具有較小值的元素的子列表，以及分別具有較大值的元素的子列表。

這是代碼：

int partition(int arr[], int left, int right) 
    { 
      int i = left, j = right; 
      int tmp; 
      int pivot = arr[(left + right)/2]; 

      while (i <= j) { 

       while (arr[i] < pivot) 
         i++; 
       while (arr[j] > pivot) 
         j--; 
       if (i <= j) { 
         tmp = arr[i]; 
         arr[i] = arr[j]; 
         arr[j] = tmp; 
         i++; 
         j--; 
       } 
      } 
      return i; 
    } 
    void quickSort(int arr[], int left, int right) { 
      int index = partition(arr, left, right); 
      if (left < index - 1) 
       quickSort(arr, left, index - 1); 
      if (index < right) 
       quickSort(arr, index, right); 
    } 

所有，除了一件事不知何故我清楚。爲什麼分區函數返回i而不是j？

Answer 1

我發現這個程序（和輸出）here。看看，

#include <iostream> 
using namespace std; 

const int INPUT_SIZE = 10; 

// A simple print function 
void print(int *input) 
{ 
    for (int i = 0; i < INPUT_SIZE; i++) 
     cout << input[i] << " "; 
    cout << endl; 
} 

// The partition function 
int partition(int* input, int p, int r) 
{ 
    int pivot = input[r]; 

    while (p < r) 
    { 
     while (input[p] < pivot) 
      p++; 

     while (input[r] > pivot) 
      r--; 

     if (input[p] == input[r]) 
      p++; 
     else if (p < r) 
     { 
      int tmp = input[p]; 
      input[p] = input[r]; 
      input[r] = tmp; 
     } 
    } 

    return r; 
} 

// The quicksort recursive function 
void quicksort(int* input, int p, int r) 
{ 
    if (p < r) 
    { 
     int j = partition(input, p, r);   
     quicksort(input, p, j-1); 
     quicksort(input, j+1, r); 
    } 
} 

int main() 
{ 
    int input[INPUT_SIZE] = {500, 700, 800, 100, 300, 200, 900, 400, 1000, 600}; 
    cout << "Input: "; 
    print(input); 
    quicksort(input, 0, 9); 
    cout << "Output: "; 
    print(input); 
    return 0; 
} 

OUTPUT:- 
Input: 500 700 800 100 300 200 900 400 1000 600 
Output: 100 200 300 400 500 600 700 800 900 1000