幾種排序算法及 Python 實(shí)現(xiàn)

cod7ce 發(fā)布于2019-07-31 11:05 / 3049人閱讀

摘要：因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下接近最好情況，效率是很高的，因此希爾排序在時(shí)間效率上比前兩種方法有較大提高。

插入排序

def insert_sort(list):
    n = len(list)
    for i in range(1, n):
        key = list[i]
        for j in range(i-1, -1, -1):
            if list[j] > key:
                list[j+1], list[j] = list[j], key
            else:
                break
    return list
   
print(insert_sort([3, 2, 5, 1, 4]))

希爾(縮小增量)排序

算法課沒(méi)有講希爾排序，所以記錄一下其思想和復(fù)雜度分析

該方法的基本思想是：先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序，待整個(gè)序列中的元素基本有序（增量足夠小）時(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序。因?yàn)橹苯硬迦肱判蛟谠鼗居行虻那闆r下（接近最好情況），效率是很高的，因此希爾排序在時(shí)間效率上比前兩種方法有較大提高。

時(shí)間復(fù)雜度與步長(zhǎng)選擇有關(guān)，最壞情況下 $$ O(n^2) $$
不穩(wěn)定

以 gap 替換插入排序中的 1

def shell_sort(list):
    n = len(list)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n, gap):
            key = list[i]
            for j in range(i-gap, -1, -gap):
                if key < list[j]:
                    list[j+gap], list[j] = list[j], key
                else:
                    break
        gap //= 2
    return list

快排

def quick_sort(list, left, right):
    if left >= right:
        return list
    key = list[right]
    high = right - 1
    low = left
    while low <= high:
        if list[low] > key:
            list[low], list[high] = list[high], list[low]
            high -= 1
        else:
            low += 1
    list[low], list[right] = list[right], list[low]
    quick_sort(list, left, low-1)
    quick_sort(list, low+1, right)
    return list
print(quick_sort([3, 2, 5, 1, 4, 6, 8, 7], 0, 7))

堆排序

def adjust_heap(list, i, n):
    lchild = 2 * i + 1
    rchild = 2 * i + 2
    max = i
    if lchild < n and list[lchild] > list[max]:
        max = lchild
    if rchild < n and list[rchild] > list[max]:
        max = rchild
    if max != i:
        list[i], list[max] = list[max], list[i]
        adjust_heap(list, max, n)
        
def build_heap(list, n):
    for i in range(int(n/2)-1, -1, -1):
        adjust_heap(list, i, n)

def heap_sort(list):
    build_heap(list, len(list))
    for i in range(len(list)-1, -1, -1):
        list[0], list[i] = list[i], list[0]
        adjust_heap(list, 0, i)
    return list
list = [3, 2, 5, 1, 4, 6, 8, 7]
print(heap_sort(list))

歸并排序

自頂向下的遞歸實(shí)現(xiàn)：
$$T(n)=2Tleft(frac{n}{2} ight)+O(n)$$
$$Rightarrow T(n)=O(nlog n)$$

def merge(list1, list2):
    res = []
    n, m = len(list1), len(list2)
    i, j = 0, 0
    while i < n and j < m:
        if list1[i] < list2[j]:
            res.append(list1[i])
            i += 1
        else:
            res.append(list2[j])
            j += 1
    res += list1[i:]
    res += list2[j:]
    return res

def merge_sort(list):
    n = len(list)
    if n <= 1:
        return list
    left = merge_sort(list[:n//2])
    right = merge_sort(list[n//2:])
    return merge(left, right)