之前有同學提出想要復習一下排序算法,那我們今天就挑一個難度中等的,快速排序。
先搞清楚快速排序原理,然后再寫代碼。
快速排序的原理不難,先找到一個數字,我們把它稱作基準,然后通過一系列的比較交換,能讓基準達到一個合適的位置,保證基準前面的數字都比他小,后面的數字都比他大。
這個過程需要兩個指針 x 和 y,其實就是數組的下標,x指向數組第一個數字,y指向數組最后一個數字。
為了操作方便,我們一般以第一個數字為基準。
先把他記下來。
?
然后從 y 開始,4比3大,不用管,y 向前移動。
?
2比 3 小,比基準小的數字應該放在左邊,所以把 2 移動到前面,同時 x 向后移動。
?
6比 3 大,放在后面,y 向前移動。
?
0比3小,放在前面,x向后移動。
?
7比3大,放在后面,y 向前移動。
?
最后,x 和 y 相等,把3放到這個位置上。
第一輪移動結束。現象就是,3的前面都是比3小的,3的后面都是比3大的。
接下來就是對3的前面和3的后面做同樣的操作,我們應該立馬能想到遞歸。
搞清楚了原理還不夠,作為求職者把代碼寫出來才是王道。
#include快速排序是不是真的很快? 我們可以和冒泡排序做個對比,修改下代碼,隨機產生5萬個數據,使用冒泡排序和快速排序,時間上的差別確實很大。void quick_sort(int *a, int start, int end) { if (start >= end) return; int x = start; int y = end; int base = a[start]; while (x < y) { while (a[y] > base && x < y) { y--; } if (x < y) { a[x++] = a[y]; } while (a[x] < base && x < y) { x++; } if (x < y) { a[y--] = a[x]; } } a[x] = base; quick_sort(a, start, x - 1); quick_sort(a, x + 1, end); } int main() { int array[] = {3, 6, 7, 0, 2, 4}; quick_sort(array, 0, 6); for (int i = 0; i < 6; i++) { printf("%d ", array[i]); } return 0; }
冒泡排序:
real 0m8.255s user 0m8.098s sys 0m0.008s快速排序:
real 0m0.078s user 0m0.010s sys 0m0.000s要說原因的話,冒泡排序只能相鄰位置上比較移動,但是快速排序卻可以跳著來,所以大部分情況下,快速排序效率都要高于冒泡排序。
審核編輯:劉清
-
排序算法
+關注
關注
0文章
52瀏覽量
10056 -
Array
+關注
關注
99文章
18瀏覽量
17828
原文標題:2分鐘看懂快速排序
文章出處:【微信號:學益得智能硬件,微信公眾號:學益得智能硬件】歡迎添加關注!文章轉載請注明出處。
發布評論請先 登錄
相關推薦
評論