1、快速排序

1.1、原理

通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列

1.2、實(shí)現(xiàn)

def quick_sort(data):
    if len(data) >= 2:
        mid = data[len(data) // 2] # 選取基準(zhǔn)值，也可以選取第一個(gè)或最后一個(gè)元素
        left, right = [], [] # 定義基準(zhǔn)值左右兩側(cè)的列表
        data.remove(mid) # 從原始數(shù)組中移除基準(zhǔn)值
        for num in data:
            if num >= mid:
                right.append(num)
            else:
                left.append(num)
        return quick_sort(left) + [mid] + quick_sort(right)
    else:
        return data
# 示例：
array = [2, 3, 1, 4, 6, 15, 5,7, 9, 10, 17, 12]
print(quick_sort(array))

輸出：[1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 15, 17]

2、冒泡排序

2.1、原理

冒泡排序（Bubble Sort）也是一種簡(jiǎn)單直觀的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

2.2、實(shí)現(xiàn)

def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr
print(bubbleSort([1,34,5,65,5,5,4,4,34,23]))

輸出：[1, 4, 4, 5, 5, 5, 23, 34, 34, 65]

3、插入排序

3.1、原理

選擇排序是一種簡(jiǎn)單直觀的排序算法，無(wú)論什么數(shù)據(jù)進(jìn)去都是 O(n2) 的時(shí)間復(fù)雜度。所以用到它的時(shí)候，數(shù)據(jù)規(guī)模越小越好。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。

3.2、實(shí)現(xiàn)

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 記錄最小數(shù)的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小數(shù)時(shí)，將 i 和最小數(shù)進(jìn)行交換
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr
print(selectionSort([1,2,3,4,5,6,8786,3]))

輸出：[1, 2, 3, 3, 4, 5, 6, 8786]

4、選擇排序

4.1、原理

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。重復(fù)第二步，直到所有元素均排序完畢。

4.2、實(shí)現(xiàn)

def selectionSort(arr):
    for i in range(len(arr) - 1):
        # 記錄最小數(shù)的索引
        minIndex = i
        for j in range(i + 1, len(arr)):
            if arr[j] < arr[minIndex]:
                minIndex = j
        # i 不是最小數(shù)時(shí)，將 i 和最小數(shù)進(jìn)行交換
        if i != minIndex:
            arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr