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; }
沒有留言:
張貼留言