快速排序

算法思想

快速排序算法首先會在序列中隨機選擇一個基準(zhǔn)值（pivot），然后將除了基準(zhǔn)值以外的數(shù)分為“比基準(zhǔn)值小的數(shù)”和“比基準(zhǔn)值大的數(shù)”這兩個類別，再將其排列成以下形式：

[ 比基準(zhǔn)值小] 基準(zhǔn)值 [比基準(zhǔn)值大]

接著，對兩個“[ ]”中的數(shù)據(jù)進行排序之后，整體的排序便完成了。對“[ ]”里面的數(shù)據(jù)進行排序時同樣也會使用快速排序，即使用遞歸的思想。

時間復(fù)雜度

時間復(fù)雜度
不穩(wěn)定

https://www.cnblogs.com/onepixel/articles/7674659.html

代碼實現(xiàn)

def quick_sort(data):    
    """快速排序"""    
    if len(data) >= 2:  # 遞歸入口及出口        
        mid = data[len(data)//2]  # 選取基準(zhǔn)值，也可以選取第一個或最后一個元素        
        left, right = [], []  # 定義基準(zhǔn)值左右兩側(cè)的列表        
        data.remove(mid)  # 從原始數(shù)組中移除基準(zhǔn)值        
        for num in data:
            # 關(guān)于data中的數(shù)據(jù)，大于mid的放在left中，小于mid的放在right            
            if num >= mid:                
                right.append(num)            
            else:                
                left.append(num) 
        # 返回值中對left和right兩個子列表分別遞歸調(diào)用函數(shù)       
        return quick_sort(left) + [mid] + quick_sort(right)    
    else:        
        return data

def quick_sort(alist, first ,last):
    # 快速排序 
    if first >= last:
        return
    
    # 先選擇基準(zhǔn)值，即第一個元素
    mid_value = alist[first]
    # 通過兩個游標(biāo)的從頭部和尾部的移動來確定基準(zhǔn)值的位置
    # 滿足左邊的比基準(zhǔn)值小，右邊的比基準(zhǔn)值大
    low = first
    high = last
    
    while low < high:
        # 下面兩個循環(huán)交替執(zhí)行，不斷的左右移動
        
        # 如果high指向的元素比基準(zhǔn)值大，說明該值應(yīng)該留在右邊
        while low < high and alist[high] >= mid_value:
            # 同時high的指針往左移動
            high -= 1
        # 如果不滿足循環(huán)條件，則說明high指向的值比基準(zhǔn)值小，和前面low指向的值交換位置
        alist[low] = alist[high]

        # 對于左邊的low指向的值小于基準(zhǔn)值，放在左邊
        while low < high and alist[low] < mid_value:
            low += 1
        # 不滿足while循環(huán)則交換位置
        alist[high] = alist[low]
    # 從循環(huán)退出，low == high
    alist[low] = mid_value
    
    # 遞歸調(diào)用函數(shù)自身：傳入下標(biāo)的起始值不同，還是原來的列表
    
    # 基準(zhǔn)值左邊的列表進行快排
    quick_sort(alist,first, low-1)
    
    # 基準(zhǔn)值右邊的列表進行快排
    quick_sort(alist,low+1, last)
    
if __name__ == "__main__":
    li = [1, 9, 6, 3, 8, 4, 7, 5, 2]
    print(li)
    quick_sort(li, 0, len(li)-1)
    print(li)

《算法圖解》這本書上的代碼很好理解

def quicksort(array):
    # 判斷只有一個元素的情況
    if len(array) < 2:
        return array
    else:
        # 指定基數(shù)
        pivot = array[0]
        # 基準(zhǔn)數(shù)左邊：從原有列表中選擇出 <= 基準(zhǔn)值的元素
        less = [i for i in array[1:] if i <= pivot]
        # 基準(zhǔn)數(shù)右邊
        greater = [i for i in array[1:] if i > pivot]
        # 調(diào)用函數(shù)自身，遞歸思想
        return quicksort(less) + [pivot] + quicksort(greater)
print (quicksort([10, 5, 2, 9, 3, 8, 5]))