1缝裤、插入排序

工作原理：通過構(gòu)建有序序列颊郎，對于未排序數(shù)據(jù)，在已排序序列中榛做，從后向前掃描，找到相應(yīng)位置并插入检眯。
插入排序是最重要的簡單排序方法昆淡，原因：

• 實(shí)現(xiàn)簡單
• 自然的穩(wěn)定性和適應(yīng)性

def insert_sort(L):
    for i in range(1, len(L)):
        # 從第i個(gè)元素開始向前比較，如果小于前一個(gè)元素昂灵，交換位置
        for j in range(i, 0, -1):
            if L[j] < L[j-1]:
                L[j], L[j-1] = L[j-1], L[j]
    return L

2、選擇排序

工作原理：在未排序序列中找到最小元素管削，放到排序序列的起始位置撑螺，然后再從剩余未排序元素中繼續(xù)尋找最小元素，放到已排序序列的末尾甘晤。
選擇排序比較低效，因?yàn)槊看芜x擇一個(gè)元素，都是從頭開始做一遍完全的比較艇炎，在整個(gè)排序中做了很多重復(fù)的工作。

def select_sort(L):
    for i in range(len(L)-1):
        k = i
        for j in range(i, len(L)):  # k是已知最小元素的位置
            if L[j] < L[k]:
                k = j
            if i != k:  # L[k]是確定的最小元素缀踪，檢查是否需要交換
                L[i], L[k] = L[k], L[i]
    return L

3、冒泡排序

冒泡排序是一種典型的通過交換元素消除逆序?qū)崿F(xiàn)排序的方法奏候，基本操作是反復(fù)比較和交換。

def bubble_sort(L):
    for i in range(len(L)):
        for j in range(1, len(L)):
            if L[j-1] > L[j]:
                L[j-1], L[j] = L[j], L[j-1]
    return L

改進(jìn)版本：
增加了一個(gè)Nfound來標(biāo)記是否存在逆序蔗草，如果不存在立即結(jié)束循環(huán)，可能提高效率

def bubble_sort(L):
    for i in range(len(L)):
        Nfound = True
        for j in range(1, len(L)):
            if L[j-1] > L[j]:
                L[j], L[j-1] = L[j-1], L[j]
                Nfound = False
        if Nfound:
            break
    return L

4咒精、快速排序

快速排序是一種著名的排序算法，采用了遞歸方式歇拆，是實(shí)踐中平均速度最快的算法之一。

def quick_sort(L, l, r):
    # l即left故觅，左索引渠啊，r即right，右索引
    if l >= r:
        return
    i = l
    j = r
    pivot = L[i]
    # while將大于中樞值pivot的元素放在其右邊昭抒，小于其的放在左邊
    while i < j:
        while i < j and L[j] >= pivot:
            j -= 1
        if i < j:
            L[i] = L[j]
            i += 1
        while i < j and L[i] <= pivot:
            i += 1
        if i < j:
            L[j] = L[i]
    L[i] = pivot
    # 劃分的區(qū)域繼續(xù)進(jìn)行此邏輯，直到所有的區(qū)域i=j
    quick_sort(L, l, i-1)
    quick_sort(L, i+1, r)
    return L

5盗迟、希爾排序

希爾排序是直接插入排序算法的一種更高效的改進(jìn)版本熙含，原理是不斷將序列劃切分，直到步長為1時(shí)使用簡單的插入排序怎静。

def shell_sort(L):
    n = len(L)
    step = int(n/2)
    while step > 0:
        for i in range(step, n):
            j = i
            while j >= step and L[j - step] > L[j]:
                L[j - step], L[j] = L[j], L[j - step]
                j -= step
        step = int(step/2)
    return L

6、并歸排序

歸并排序的思想就是先遞歸分解數(shù)組腌乡，再合并數(shù)組。將數(shù)組分解最小之后与纽，然后合并兩個(gè)有序數(shù)組塘装，基本思路是比較兩個(gè)數(shù)組的最前面的數(shù)，誰小就先取誰蹦肴，取了后相應(yīng)的指針就往后移一位。然后再比較阴幌，直至一個(gè)數(shù)組為空卷中，最后把另一個(gè)數(shù)組的剩余部分復(fù)制過來即可仓坞。

def merge_sort(L):
    if len(L) <= 1:
        return L
    # 二分分解
    num = int(len(L) / 2)
    left = merge_sort(L[:num])
    right = merge_sort(L[num:])
    # 合并
    return merge(left, right)


def merge(left, right):
    """合并操作，將兩個(gè)有序數(shù)組left[]和right[]合并成一個(gè)大的有序數(shù)組"""
    # left與right的下標(biāo)指針
    l, r = 0, 0
    result = []
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1
    result += left[l:]
    result += right[r:]
    return result