qsort如何工作？

Question

有人可以解釋什麼這種排序算法呢？我無法遵循邏輯，它使用遞歸。看起來很奇怪，把中期和第一條（從第8條開始）交換。此外，在第一次迭代中，++last = i，因此調用swap會浪費。

代碼集last = left，i = left + 1，然後調用swap（）與++last。這使得last等於i！

/* qsort: sort v[left]...v[right] into increasing order */ 
void qsort(int v[], int left, int right) 
{ 
    int i, last; 

    if (left >= right) /* do nothing if array contains */ 
     return; /* fewer than two elements */ 

    swap(v, left, (left + right)/2); /* move partition elem */ 
    last = left;      /* to v[0] */ 

    for (i = left + 1; i <= right; i++) /* partition */ 
     if (v[i] < v[left]) 
      swap(v, ++last, i); 
    swap(v, left, last); /* restore partition elem */ 
    qsort(v, left, last-1); 
    qsort(v, last+1, right); 
} 

/* swap: interchange v[i] and v[j] */ 
void swap(int v[], int i, int j) 
{ 
    int temp; 
    temp = v[i]; 
    v[i] = v[j]; 
    v[j] = temp; 
} 

Answer 1

代碼中的註釋很好解釋。在開始時，選擇一個「分區」元素並將其移動到數組的開頭，以便隨後的交換不會觸及它。然後所有剩餘的元素被部分排序，這樣'分區'元素可以被插入排序數組的最後位置，這就是最後一個交換所做的事情（就在調用遞歸部分到左邊和右邊到分區元素）。

有關算法的詳細信息，請閱讀Quick sort。