Code

2018年2月17日 星期六

Quick Sort

Reference: Comparison Sort: Quick Sort(快速排序法) Posted by Chiu CC (很棒很詳細的解說)

Quick Sort 的想法在於,選定一個元素P,用一些方法讓其他所有元素以P為基準,小於P的元素放到P的左邊,大於P的元素放到P的右邊,直到P的左邊均為小於P的元素,P的右邊均為大於P的元素,P的左右兩邊再以相同的模式處理,直到所有元素完成排列。

實現方法:
  找一個元素當作基準值pivot(方便起見,一般選擇最後一項),使用large變數走訪整個陣列並紀錄大於pivot的數的數量small變數紀錄小於pivot的數的數量
  如果large指向的元素小於pivot,表示小於pivot的數多一個,則將該元素與small指向的下一個元素(即比pivot大的第一個元素)交換(swap),small右移。
  直到large走訪完全部的元素,表示small左邊全為小於pivot的數,small右邊到large左邊均為大於pivot的數,將pivot與small下一個元素交換(達成pivot左邊均小於它,右邊均大於它的目標)
  到此,第一個pivot完成任務,接下來便是使用遞迴,將pivot左邊與右邊的所有元素都做相同的事,最後所有元素便會完成排列。

Code (C++):
#include <iostream>
using namespace std;

void quick_sort(int array[], int b, int e){ // b:begin, e:end
    if (b >= e) return;
    int sm = b-1, la = b, pi = e; // sm:small, la:large, pi:pivot
    for (; la < pi; la++) {
        if (array[la] < array[pi]) {
            swap(array[sm+1], array[la]);
            sm++;
        }
    }
    swap(array[sm+1], array[la]);
    quick_sort(array, b, sm);
    quick_sort(array, sm+2, la);
}

int main(int argc, const char * argv[]) {
    int a[6] = {2, 3, 7, 1, 9, 2}; //example
    quick_sort(a, 0, 5);
    for (int i = 0; i < 6; i++) {
        cout << a[i];
    }
    return 0;
}

沒有留言:

張貼留言