python -- 快速排序


生当复来归,死当长相思


说明

快速排序使 用分治法 策略来把一个序列分为两个子序列 步骤为: 1. 从数列中挑出一个元素,称为"基准"(pivot), 2. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任何一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。 3. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。


伪代码

分区

function partition(a, left, right, pivotIndex)
     pivotValue := a[pivotIndex]
     swap(a[pivotIndex], a[right]) // 把 pivot 移到結尾
     storeIndex := left
     for i from left to right-1
         if a[i] < pivotValue
             swap(a[storeIndex], a[i])
             storeIndex := storeIndex + 1
     swap(a[right], a[storeIndex]) // 把 pivot 移到它最後的地方
     return storeIndex // 返回 pivot 的最终位置

快排

procedure quicksort(a, left, right)
    if right > left
        select a pivot value a[pivotIndex]
        pivotNewIndex := partition(a, left, right, pivotIndex)
        quicksort(a, left, pivotNewIndex-1)
        quicksort(a, pivotNewIndex+1, right)

分区算法详解

拿 wiki 上的一张图解释

详解可查看这里 http://bubkoo.com/2014/01/12/sort-algorithm/quick-sort/


动图 -- wiki


代码实现

def quick(L,left,right):
    if left<right:
        print(L)
        pivot = partition(L,left,right)
        quick(L,left,pivot-1)
        quick(L,pivot+1,right)
    return

'''
left,right 表示列表的起始坐标
'''
def partition(L,left,right):
    pivot = L[right]   # 最后一个元素做基准
    storeIndex = left
    for i in range(left,right):
        if L[i] < pivot:
            L[storeIndex],L[i] = L[i],L[storeIndex]
            storeIndex += 1

    L[storeIndex],L[right] = L[right],L[storeIndex]
    return storeIndex

if __name__ == '__main__':
    L = [23,42,2,34,34,322,5,43,2,3,13,56,32]
    L = quick(L,0,len(L)-1)
    #print(L)