快速排序

快速排序是一個(gè)非常高效的排序算法戈稿，目前的應(yīng)用非常廣泛， 同時(shí)也是面試的逞冉ⅲ客鞍盗。學(xué)好快速排序需了，能夠?qū)φ业焦ぷ饔泻艽蟮膸椭Ｍ瑫r(shí)般甲，也有很多面試題也會(huì)用到這種思想肋乍。

快速排序也是一種分治的思想，但是它于歸并算法更加好是因?yàn)闅w并算法會(huì)用到輔助數(shù)組敷存，其空間復(fù)雜度是O(n). 而快速排序不需要用到新的數(shù)組空間墓造，它的空間復(fù)雜度是O(1).

快速排序的核心是：選定一個(gè)值作為軸心值，然后將數(shù)組分成兩個(gè)部分锚烦，一部分是大于這個(gè)軸心值觅闽，另一部分是小于這個(gè)軸心值的。然后將這個(gè)軸心值前的部分繼續(xù)使用快速排序涮俄，將這個(gè)軸心值的后半部分繼續(xù)使用快速排序蛉拙。直到指剩下了一個(gè)元素的時(shí)候是不需要交換的〕骨祝快速排序非常適用于大數(shù)據(jù)量的排序孕锄，因?yàn)樗炔徽加枚嘤嗟目臻g，又能達(dá)到時(shí)間復(fù)雜度是O(nlogn).

下面睹栖，快速排序的步驟：

image

第一步：選擇最大的index作為軸心

第二步：選擇兩個(gè)指分別指向最左邊左邊和除了軸心的最右邊硫惕。

第三步：兩個(gè)指針?lè)謩e是left和right。左邊的只想低索引野来。右邊的指向高索引恼除。

第四步：當(dāng)左邊的索引的值小于軸心，那就向右移動(dòng)索引曼氛。

第五步：當(dāng)右邊的索引的值大于軸心豁辉，那就向左移動(dòng)索引。

第六步：當(dāng)?shù)谒牟胶偷谖宀蕉疾环蠒r(shí)舀患，交換彼此徽级。

第七步：如果 left >= right, 那么left就是新的軸心的位置，將軸心與之交換聊浅。

代碼示例

def QuickSort(array, left=0, right=None):
    arrayLen = len(array)
    if arrayLen <= 1:
        return array
    if right == None:
        right = arrayLen - 1
    if left < right:
        pivot = partition(array, left, right)
        QuickSort(array, left, pivot - 1)
        QuickSort(array, pivot + 1, right)

def partition(array, left, right):
    pivotValue = array[right]
    i = left
    j = right - 1
    while i < j:
        while j > left and array[j] > pivotValue:
            j -= 1
        while i < right and array[i] <= pivotValue:
            i += 1
        if i < j:
            array[i], array[j] = array[j], array[i]
            i += 1
            j -= 1
    if array[i] > array[right]:
        array[i], array[right] = array[right], array[i]
    return i

if __name__ == '__main__':
    testList = [2, 7, 6, 1, 5, 4, 9, 3]
    QuickSort(testList)
    print(testList)

另一種實(shí)現(xiàn)方式理解會(huì)有偏差餐抢，所以給出大家下面參考，如果能理解下面的代碼低匙，請(qǐng)使用下面的方式編寫快速排序：

image.png

1.選取一個(gè)數(shù)字作為基準(zhǔn)旷痕，可選取末位數(shù)字

2.將數(shù)列第一位開(kāi)始，依次與此數(shù)字比較顽冶，如果小于此數(shù)欺抗，將小數(shù)交換到左邊，最后達(dá)到小于基準(zhǔn)數(shù)的在左邊强重，大于基準(zhǔn)數(shù)的在右邊绞呈，分為兩個(gè)數(shù)組

3.分別對(duì)兩個(gè)數(shù)組重復(fù)上述步驟

代碼示例

def QuickSort(array, left=0, right=None):
    arrayLen = len(array)
    if arrayLen <= 1:
        return array
    if right == None:
        right = arrayLen - 1
    if left < right:
        pivot = partition(array, left, right)
        QuickSort(array, left, pivot - 1)
        QuickSort(array, pivot + 1, right)

def partition(array,left,right):
    i = left-1
    for j in range(left,right):
        if array[j] <= array[right]:
            i += 1
            array[j],array[i] = array[i],array[j]
    array[i+1],array[right] = array[right],array[i+1]
    return i+1

if __name__ == '__main__':
    testList = [2, 7, 6, 1, 5, 4, 9, 3]
    QuickSort(testList)
    print(testList)