常见排序的python实现

import numpy as np
import timeit
import matplotlib.pyplot as plt

## 生成测试序列
def GenerateArray(n, N=1000):
    orginArray = np.random.randint(N, size=n).tolist()
    return orginArray

orginArray = GenerateArray(20)
print(orginArray)

[662, 176, 688, 180, 206, 620, 911, 669, 391, 976, 868, 240, 197, 956, 975, 655, 316, 457, 908, 618]

插入排序

对于序列 \((a_1, a_2, \cdots, a_n)\) 中的每一个数，判断其在已排序好的序列中的位置，并插入。时间复杂度 \(O(n^2)\).

# 插入排序
def InsertSort(arr):
    for j, key in enumerate(arr):
        i = j - 1
        while(i >= 0 and arr[i] > key):
            arr[i+1] = arr[i]
            i -= 1
        arr[i+1] = key
    return arr

t = timeit.timeit(setup="arr = GenerateArray(10000)", stmt="InsertSort(arr)", globals=globals(), number=1)
print("插入排序 10000 个数字 t = {:.3f} s.".format(t))

插入排序 10600 个数字 t = 4.892 s.

选择排序

对于序列 \((a_1, a_2, \cdots, a_n)\)，不断选择剩余列 \(a[i:]\) 中的最小元素并和 \(a_i\) 交换。时间复杂度 \(O(n^2)\).

# 选择排序
def SelectSort(arr):
    for i in range(len(arr)-1):
        min_index = i
        for j, x in enumerate(arr[i+1:]):
            if x < arr[min_index]:
                min_index = j+i+1
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return

t = timeit.timeit(setup="arr = GenerateArray(10000)", stmt="SelectSort(arr)", globals=globals(), number=1)
print("选择排序 10000 个数字 t = {:.3f} s.".format(t))

选择排序 12500 个数字 t = 4.838 s.

归并排序

不断将序列二分，直至最小单元后归并，归并两有序数组，速度快。时间复杂度 \(O(n\log n)\).

# 归并排序
def MergeSort(arr, begin=0, **end):
    def Merge(arr, begin, n, end): # 归并arr[:n]和arr[n:]
        L = arr[begin:n] + [np.inf]
        R = arr[n:end] + [np.inf]
        i, j = 0, 0
        for k in range(begin, end):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
        return
    # 分治
    if not end:
        end = len(arr)
    else:
        end = end['end']
    length = end - begin
    if length <= 1:
        return
    n = length // 2 + begin
    MergeSort(arr, begin=begin, end=n)      # 排序前length/2项
    MergeSort(arr, begin=n, end=end)        # 排序后length/2项
    Merge(arr, begin=begin, n=n, end=end)   # 归并
    return


t = timeit.timeit(setup="arr = GenerateArray(500000)", stmt="MergeSort(arr)", globals=globals(), number=1)
print("归并排序 500000 个数字 t = {:.3f} s.".format(t))

归并排序 500000 个数字 t = 2.253 s.

快速排序

随机（或二分）地将序列划分为两段，将小于基准值的移到左边，大于基准值的移到右边。递归上述过程。

def QuickSort(arr):    
    """快速排序"""    
    if len(arr) >= 2:  # 递归入口及出口        
        mid = arr[len(arr)//2]  # 选取基准值，也可以选取第一个或最后一个元素        
        left, right = [], []  # 定义基准值左右两侧的列表        
        arr.remove(mid)  # 从原始数组中移除基准值        
        for x in arr:            
            if x >= mid:                
                right.append(x)            
            else:                
                left.append(x)        
        return QuickSort(left) + [mid] + QuickSort(right)    
    else:        
        return arr

t = timeit.timeit(setup="arr = GenerateArray(500000)", stmt="QuickSort(arr)", globals=globals(), number=1)
print("快速排序 500000 个数字 t = {:.3f} s.".format(t))

快速排序 100000 个数字 t = 11.367 s.