- 快速排序一般要比其他排序算法快得多；
原理
- 首先，隨機選擇一個分切元素（中間點）（一般是 數(shù)組/子數(shù)組的第一個元素
sample[low]）； - 交換分切元素兩邊的元素，使得分切元素左邊的元素都比它小，右邊元素都比它大（這樣就相當于排序了一個元素 -- 分切元素）；
- 把分切元素左右兩邊當成兩個子數(shù)組，遞歸執(zhí)行以上過程，遞歸結(jié)束，數(shù)組排序完成
代碼
快速排序的代碼分為兩部分：切分函數(shù) 和 遞歸（調(diào)用切分函數(shù)的）函數(shù)
切分函數(shù)
目標
就是要使切分元素，左邊的元素都小于切分元素，右邊的元素都大于切分元素
切分函數(shù)
實現(xiàn)過程
- 切分元素：切分元素選擇數(shù)組（或子數(shù)組）的第一個元素
- 交換：交換需要用到兩個指針
- 左指針初始時為數(shù)組的第二個元素（第一個元素是切分元素），向右移動 ，直到找到一個值大于切分元素時停下。
- 右指針初始為數(shù)組的最后一個元素，不斷向左移動，直到遇到一個比切分元素小或等于（）的，停下
- 等于切分元素按小于處理
- 此時會有兩種情況：
- 兩個指針還未相遇：交換左右指針所指元素，并繼續(xù)前進
- 兩個指針已經(jīng)相遇（左指針的索引 i >= 右指針的索引 j）：屬于已經(jīng)有序的正常情況，退出指針移動操作
- 為了避免所有元素都小于（或大于）切分元素的情況，應(yīng)限制指針的索引 --
i,j避免無限移動，導致越界 - 最后，將 切分元素與索引 j 的元素交換（因為兩指針相遇后，j 已經(jīng)在中間點的左邊，該元素比切分元素?。?/li>
partition 切分函數(shù)
#!/usr/bin/python3
class QuickSort:
def exch(self, sample, i, j):
t = sample[i]
sample[i] = sample[j]
sample[j] = t
def partition(self, sample, low, high):
# 切分元素: v
# 左指針索引：i
# 右指針索引：j
v = sample[low]
i = low + 1
j = high
while True:
while sample[i] <= v:
i += 1
if i > high: break
while sample[j] > v:
j -= 1
if j < (low + 1): break
if i >= j:
break
else:
self.exch(sample, i, j)
self.exch(sample, low, j)
return j
遞歸（調(diào)用切分函數(shù)的）函數(shù)
兩個子數(shù)組
遞歸調(diào)用函數(shù)的作用是不斷的地將根據(jù)切分元素的位置，將大數(shù)組分成兩個小數(shù)組，這個切分元素的位置最后是和右指針的索引 j 交換，所以我們可以通過切分函數(shù)獲得
值得注意的是：并不是新建一個子數(shù)組并傳給切分函數(shù)，而是在本來的大數(shù)組上邏輯（通過索引
low,j,high）地劃分子數(shù)組
代碼
def sort(self, sample, low, high):
# j 為切分元素的位置
if low >= high:
return
j = self.partition(sample, low, high)
self.sort(sample, low, j - 1)
self.sort(sample, j + 1, high)
測試
if __name__ == '__main__':
import random
def show(target, prompt=''):
print(prompt, end='')
for elem in target:
print(elem, end=' ')
print()
sample = input().split()
show(sample, 'Origin: ')
sort = QuickSort()
random.shuffle(sample) # 為了保證切分元素（我們選數(shù)組的第一個元素作為切分元素）是隨機的，我們先將數(shù)組打亂，
sort.sort(sample, 0, len(sample) - 1)
show(sample, 'Result: ')
/mnt/f/python $ ./quickSort.py < data.txt
Origin: D G A B E C F
Result: A B C D E F G
/mnt/f/python $
/mnt/f/python $ ./quickSort.py < bigData.txt
Origin: H M F N A P N G M G Q Y Q V P T Z Z F Z Z U Q W C D Z E X H M Z K D C B K P L E X F O I O A N F X M X U T V I M T W W A P L O L H W Y W J W H C M P K U I D P B O G R K E V G L F W N U C P T J R M Y H
Result: A A A B B C C C C D D D E E E F F F F F G G G G H H H H H I I I J J K K K K L L L L M M M M M M M N N N N O O O O P P P P P P P Q Q Q R R T T T T U U U U V V V W W W W W W W X X X X Y Y Y Z Z Z Z Z Z
/mnt/f/python $
Python 隨機生成字母
In [1]: import string, random
In [2]: for i in range(5):
...: print(random.choice(string.ascii_uppercase), end=' ')
...: else:
...: print()
...:
L R X G W
In [3]: string.ascii_letters
Out[3]: 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
In [4]: string.ascii_uppercase
Out[4]: 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
In [5]: string.ascii_lowercase
Out[5]: 'abcdefghijklmnopqrstuvwxyz'
In [6]:
