# 快速排序
## 示意圖
## 運作步驟
1. 挑選基準值：從數列中挑出一個元素，稱為“基準”（pivot）
2. 分割：重新排序數列，所有比基準值小的元素擺放在基準前面，所有比基準值大的元素擺在基準后面（與基準值相等的數可以到任何一邊）。在這個分割結束之后，對基準值的排序就已經完成
3. 遞歸排序子序列：遞歸地將小于基準值元素的子序列和大于基準值元素的子序列排序。
## 算法分析
* 最壞時間復雜度 O(n^2)
* 最優時間復雜度 O(nlogn)
* 平均時間復雜度 O(nlogn)
## 實現
```Python
def quick_sort(list):
'''Python中的快速排序算法簡單實現
:param list: 需要排序的數字列表
:return: 排序結果
'''
if len(list) <= 1:
return list
less, greater, pivot = [], [], list.pop()
for item in list:
if item < pivot:
less.append(item)
else:
greater.append(item)
list.append(pivot)
return quick_sort(less) + [pivot] + quick_sort(greater)
def quick_sort_in_place(list):
'''Python中的快速排序算法原地排序版本實現
:param list: 需要排序的數字列表
:return: 排序結果
'''
def partition(list, start, end):
pivot = list[end]
for j in range(start, end):
if list[j] < pivot:
list[start], list[j] = list[j], list[start]
start += 1
list[start], list[end] = list[end], list[start]
return start
def sort(list, start, end):
if start >= end:
return
p = partition(list, start, end)
sort(list, start, p - 1)
sort(list, p + 1, end)
sort(list, 0, len(list) - 1)
return list
```
## 測試
```
$ python quick_sort.py
快速排序>>>
請輸入需要排序的數字，用英文半角逗號隔開，直接回車則使用默認數據：
需要排序的數字為：
8,-5,10,6,-23,15,45,20,16
quick_sort排序結果：
-23,-5,6,8,10,15,16,20,45
quick_sort_in_place排序結果：
-23,-5,6,8,10,15,16,20,45
```
# 代碼庫地址
[https://github.com/liuzhen153/play-algorithm-python](https://github.com/liuzhen153/play-algorithm-python)
