因?yàn)橛幸粋€(gè)先入為主的概念：快速排序最牛。因此剛開始一聽見快速 排序就不敢寫，認(rèn)為其絕對(duì)很復(fù)雜。

事實(shí)證明這種想法不能有！

簡單粗暴地使用遞歸手寫快速排序：

（為了面試時(shí)候能不怯場的直接手撕）

            
              # 簡單粗暴的快速排序
# 存在額外的開銷存放左右
# 要多次遍歷數(shù)組
def quicksort(array):  # 直接遞歸
    if len(array)<2:   # 遞歸出口
        return array
    pivot_index = 0
    pivot = array[pivot_index]
    left_arr = [i for i in array[pivot_index+1:] if i<=pivot]
    right_arr = [i for i in array[pivot_index+1:] if i>pivot]
    return quicksort(left_arr) + [pivot] + quicksort(right_arr)

# 測試
import random
# seq = list(range(10))
# random.shuffle(seq)
seq = [random.randint(1,100) for i in range(10)]
print(seq)
quicksort(seq)
    
            
          

輸出：?

            
              [4, 77, 14, 14, 33, 69, 63, 67, 87, 9]
[4, 9, 14, 14, 33, 63, 67, 69, 77, 87]

            
          

改進(jìn)：

上述算法存在很多問題，已經(jīng)寫在注釋里。因此考慮不創(chuàng)建額外數(shù)組的改進(jìn)：

思路概述：

1. 以第一個(gè)元素作為pivot，left指針指向第二個(gè)元素，right指針指向最后一個(gè)元素。
2. 如果left指向的元素小于pivot，則left指針+1（即后移一個(gè)元素），接著判斷，如果該元素大于pivot，left指針停止移動(dòng)。
3. 如果right指向的元素大于pivot，則right指針-1（即前移一個(gè)元素），接著判斷，如果該元素小于pivot，right指針停止移動(dòng)。
4. 判斷l(xiāng)eft是否大于right，是就跳出
5. 交換left和right所指向的元素。
6. 返回步驟2.
7. 跳出后，交換right所指和pivot所在位置的值。

            
              # 改進(jìn)，不產(chǎn)生多余的開銷
# 在原數(shù)組上用左右指針
def partition(array,beg,end): # pivot左邊的都比pivot小，右邊的都比pivot大
    pivot_index = beg
    pivot = array[pivot_index]
    left = pivot_index+1
    right = end
    
    while True:
        while left<=right and array[left]<=pivot:
            left += 1
        while left<=right and array[right]>pivot:
            right -=1
        if left>right:
            break
        else:
            array[left],array[right] = array[right],array[left]
    array[right],array[pivot_index] = array[pivot_index],array[right]
    return right              # 返回pivot的下標(biāo)
    
def quicksort_pro(array,beg,end):   # 改進(jìn)后的快速排序
    if beg < end :
        pivot = partition(array,beg,end)
        quicksort_pro(array,beg,pivot)
        quicksort_pro(array,pivot+1,end)
        
# 測試
import random
# seq = list(range(10))
# random.shuffle(seq)
seq = [random.randint(1,100) for i in range(6)]
print(seq)
quicksort_pro(seq,0,len(seq)-1)
print(seq)
    
            
          

以上。

參考：

https://www.bilibili.com/video/av26524049

https://www.bilibili.com/video/av26524633/?spm_id_from=trigger_reload

?