C++中級演算法第四天(快速排序)
大家好!今天給大家講的是快速排序
解釋:
快速排序(Quicksort)是對氣泡排序的一種改進。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通過一趟排序將要排序的資料分割成獨立的兩部分,其中一部分的所有資料都比另外一部分的所有資料都要小,然後再按此方法對這兩部分資料分別進行快速排序,整個排序過程可以遞迴進行,以此達到整個資料變成有序序列
以上就是官方的解釋,就小編的理解是我們找一個數字當作參照物,然後講資料比這個參照物小的放在序列的左邊,大的放右邊
程式碼原圖於下:
#include<iostream> using namespace std; void print(int a[], int n) { for (int j = 0; j < n; j++) { cout << a[j] << ""; } cout << endl; return; } void swap(int* a, int* b) { int tmp = *a; *a = *b; *b = tmp; return; } int partition(int a[], int low, int high) { //基準元素 int k = a[low]; //從表的兩端交替地向中間掃描 while (low < high) { //從high 所指位置向前搜尋,至多到low+1 位置。將比基準元素小的交換到低端 while (low < high && a[high] > k) --high; while (a[low] < k) ++low; swap(&a[low], &a[high]); } a[low] = a[high]; a[high] = k; print(a, 10); return low; } void quickSort(int a[], int low, int high) { if (low < high) { //將表一分為二 int privotLoc = partition(a, low, high); //遞迴對低子表遞迴排序 quickSort(a, low, privotLoc - 1); //遞迴對高子表遞迴排序 quickSort(a, privotLoc + 1, high); } return; } int main() { int a[10] = { 3,1,5,7,2,4,9,6,10,8 }; cout << "初始值:"; print(a, 10); quickSort(a, 0, 9); cout << "結果:"; print(a, 10); return 0; }