各种排序算法的复习

先放一张图，来源runoob。

注：对于希尔排序的平均复杂度有一些疑问。

冒泡排序

def bubbleSort(arr):
    for i in range(len(arr)-1, 0, -1):
        flag = True
        for j in range(0, i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag = False
        if flag:
            break
    return arr

每次起泡将最大的元素放到末尾，加速方法是判断一次起泡后是否有变换，如果没有变化则终止。

选择排序

def selectionSort(arr):
    for i in range(len(arr)-1):
        minIndex = i
        for j in range(i, len(arr)):
            if arr[minIndex] > arr[j]:
                arr[minIndex], arr[j] = arr[j], arr[minIndex]
        if i != minIndex:
            arr[minIndex], arr[i] = arr[i], arr[minIndex]
    return arr

每次选择最小的元素放到未排序数组的左边，注定要走完全程。

插入排序

def insertSort(arr):
    if not arr:
        return []
    res = [arr[0]]
    for i in range(1, len(arr)):
        p = arr[i]
        for pos in range(i-1, -1, -1):
            if p > res[pos]:
                break
        if p > res[0]:
            res.insert(pos+1, p)
        else:
            res.insert(0, p)
    return res

每次将未排序的元素插入到已经排好序的数组中。这里偷懒开了空间，同时用了insert()函数插入。

希尔排序

def shellSort(arr):
    if not arr:
        return []
    gap = 1
    while(gap < len(arr)/2):
        gap = gap*2+1
    while gap > 0:
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i-gap
            while j >= 0 and arr[j] > temp:  # insert sort
                arr[j+gap] = arr[j]
                j -= gap
            arr[j+gap] = temp
        gap = gap//2
    return arr

相对复杂，时间复杂度较难分析。每次选择一个gap，将间隔为gap的元素进行排序。最后gap=1完成最后一步。

归并排序

def mergeSort(arr):
    def merge(arr1, arr2):
        res = []
        l1, l2, i, j = len(arr1), len(arr2), 0, 0
        while i < l1 and j < l2:
            if arr1[i] >= arr2[j]:
                res.append(arr2[j])
                j += 1
            elif arr2[j] > arr1[i]:
                res.append(arr1[i])
                i += 1
        while i < l1:
            res.append(arr1[i])
            i += 1
        while j < l2:
            res.append(arr2[j])
            j += 1
        return res
    if len(arr) < 2:
        return arr
    mid = len(arr)//2
    arr1 = mergeSort(arr[0:mid])
    arr2 = mergeSort(arr[mid:])
    return merge(arr1, arr2)

这是我知道的第一个最坏情况为O(nlogn)的排序方法。每次将数组分成两部分，左右分别排序再组合在一起。

快速排序

def quickSort(arr):
    length = len(arr)
    if length < 2:
        return arr

    def partition(arr):
        length = len(arr)
        if length < 2:
            return arr, 0
        pivot, pos = arr[0], 1
        while pos < length and arr[pos] < pivot:
            pos += 1
        for i in range(pos, length):
            if arr[i] < pivot:
                arr[pos], arr[i] = arr[i], arr[pos]
                pos += 1
        arr[0], arr[pos-1] = arr[pos-1], arr[0]
        return arr, pos-1
    arr, pos = partition(arr)
    return quickSort(arr[0:pos])+[arr[pos]]+quickSort(arr[pos+1:])

我对它一直有一些误解，认为最坏情况是平方复杂度的排序方法不是好方法。但是一些文章说排序速度大部分情况是O(nlogn)，而且系数很小，比归并排序快。快速排序主要在于partition()函数，将数组分成两部分。