概述
快速排序算法是基於交換的高效排序算法, 採用了分治的思想.
其基本思想如下:
- 從數列中取出一個數作為基準數
- 將數組進行劃分, 將比基準數大的元素移至右側, 比基準數小的元素移至左側
- 對左右的子區間重複進行排序, 直至每個子區間只有一個元素
其時間空間複雜度如下:
快速排序就是將小的放左邊, 大的放右邊, 在對左右進行重複執行.
其代碼實現如下:
同時, 快速排序也可以進行三切分, 分為大於、等於、小於三組, 對於重複元素比較多的情況, 如此切分是比較好的, 可以有效避免相等元素的比較, 將相等元素聚集起來, 就可以不必再切分這些元素了.
分享到:
閱讀更多 學習編程 的文章
