Quick Sort (快速排序法)

概念影片

• Quick Sort-1
• Quick Sort-2
• Quick Sort-3

• Quick Sort-4

  作法

• 從數列中挑出一個元素，稱為"基準"（pivot）

• 重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準後面（相同的數可以到任一邊）。在這個分割結束之後，該基準就處於數列的中間位置。這個稱為分割（partition）

• 遞迴地（recursively）把小於基準值元素的子數列和大於基準值元素的子數列排序。

Pseudo Code

int N = 9;
int students[] = {9, 4, 1, 6, 7, 3, 8, 2, 5};

void swap(int a, int b){
    int temp = students[a];
    students[a] = students[b];
    students[b] = temp;
}

int Partition(int front, int end){
    int pivot = students[end];
    int i = front -1;
    for (int j = front; j < end; j++) {
        if (students[j] < pivot) {
            i++;
            swap(i,j);
        }
    }
    i++;
    swap(i,end);
    return i;
}

void QuickSort(int front, int end){
    if (front < end) {
        int pivot = Partition(front, end);
        QuickSort(front, pivot - 1);
        QuickSort(pivot + 1, end);
    }
}

int main() {
    QuickSort(0, N-1);
    for(int i =0;i<N;i++){
        cout<<students[i]<<" ";
    }
}

補充資料

• 快速排序法