上一回，在前面已經對冒泡排序、直接插入排序、希爾排序、選擇排序做了說明分析（具體詳情可點擊下方的鏈接查看）。這回，將對快速排序進行相關說明分析。
前幾篇鏈接列表：
排序算法系列目錄說明
冒泡排序（Bubble Sort）
插入排序（Insertion Sort）
希爾排序（Shell Sort）
選擇排序（Selection Sort）
快速排序（Quick Sort）
歸併排序（Merge Sort）
堆排序（Heap Sort）
計數排序（Counting Sort）
桶排序（Bucket Sort）
基數排序（Radix Sort）
快速排序（Quick Sort）
快速排序，又稱劃分交換排序（partition-exchange sort）
1.基本思想
通過一趟排序將待排記錄分隔成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。
2. 實現邏輯
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
從數列中挑出一個元素，稱為 "基準"（pivot），
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分區退出之後，該基準就處於數列的中間位置。這個稱為分區（partition）操作。
遞歸地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。
遞歸到最底部時，數列的大小是零或一，也就是已經排序好了。這個算法一定會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。
3. 動圖演示
快速排序演示
4. 複雜度
平均時間複雜度：O(NlogN)
最佳時間複雜度：O(NlogN)
最差時間複雜度：O(N^2)
空間複雜度：根據實現方式的不同而不同
5. 代碼實現
C版本（遞歸法）：
快速排序（C版本-遞歸法）
C++版本（遞歸法）：
快速排序（C++版本-遞歸法）
Java版本：
快速排序（Java版本-遞歸法）
6. 優化改進
場景分析：
遞歸是一種使用相同的方法，通過解決問題的子集以達到解決整個問題的方法，是一種使用有限代碼解決“無限”計算的方法。在C/C++語言中遞歸表現在函數對自身的直接/間接的調用上，在實現上，遞歸依賴於語言的運行時調用堆棧，使用堆棧來保存每一次遞歸調用返回時所需要的條件。遞歸通常具有簡潔的編碼和清晰的思路，但這種簡潔是有代價的。一方面，是函數調用的負擔；另一方面，是堆棧佔用的負擔（堆棧的大小是有限的）。
改進思路：
遞歸轉化為迭代。迭代的思想主要在於，在同一棧幀中不斷使用現有數據計算出新的數據，然後使用新的數據來替換原有數據。
改進代碼
C版本（迭代法）：
快速排序（C版本-迭代法）
C++版（迭代法）：
快速排序（C++版本-迭代法）
總結
快速排序在排序算法中具有排序速度快，而且是就地排序等優點，使得在許多編程語言的內部元素排序實現中採用的就是快速排序，很多面試題中也經常遇到。對於其算法的改進，除了剛剛上文中提到的意外，根據實際場景還有諸多改進方法，包括對小序列採用插入排序替代，三平均劃分，三分區劃分等改進方法（相關的改進方法就不一一說明，有興趣的讀者可上網查閱瞭解）。
源碼地址：https://github.com/7-sevens/algorithm
下一篇預告：歸併排序（Merge Sort）。欲知詳情，且聽下回分解。
微信公眾號
想要獲取更多精品技術乾貨，歡迎關注微信公眾號：開發者小黑屋