[Python知识库]Python实现基本排序

快速排序 VS 归并排序

区别：归并从最小的子列表排序再合并；快排从大列表按基准点分为子列表

1.?快速排序

基本思想：

i.? ?选取基准点拆分成2个子列表，小于基准点放在左边列表，大于则右边列表；

ii.? 每个子列表重复 i 过程；

iii. 结束点，子列表元素个数少于2

import random
import numpy as np


# 递归实现快速排序
def swap(aim_list, middle, right):
    tem = aim_list[middle]
    aim_list[middle] = aim_list[right]
    aim_list[right] = tem
    return aim_list


def partion(aim_list, left, right):
    """分割为子列表，返回边界点"""
    middle = (left+right)//2
    middle_value = aim_list[middle]
    swap(aim_list, middle, right) # 基准点放在最右端
    boundary = left # 边界点从最左边开始

    for index in range(left, right):
        if aim_list[index] < middle_value:
            swap(aim_list, boundary, index)
            boundary += 1
    swap(aim_list, boundary, right) # 扫描结束时，基准点值最小，再放回中间

    return boundary


def quick_sort_helper(aim_list, left, right):
    # 临界点
    if left < right:
        boundary = partion(aim_list, left, right)
        quick_sort_helper(aim_list, left, boundary-1)
        quick_sort_helper(aim_list, boundary+1, right)


def quick_sort(aim_list):
    return quick_sort_helper(aim_list, 0, len(aim_list)-1)


def generate_list(size):
    aim_list = []
    for i in range(size):
        aim_list.append(random.randint(1,100))

    return aim_list


if __name__ == "__main__":
    # aim_list = generate_list(20)
    aim_list = np.random.randint(100, size=20)
    set_format = ''.join(['*']*40)
    print("%s before sort %s" % (set_format, set_format))
    print(aim_list)
    print("%s after sort %s" % (set_format, set_format))
    quick_sort(aim_list)
    print(aim_list)

?输出：

****************************** before sort ******************************
[52 34 93 23 99 19 86 66 60 40 98 46 84 48 29 40 69 50 38 30]
****************************** after sort ******************************
[19 23 29 30 34 38 40 40 46 48 50 52 60 66 69 84 86 93 98 99]

2. 归并排序

基本思想：

i.? ?选取中间位置，拆分成2个子列表，并分别递归排序；

ii.? 当子列表不能划分时停止。

import random
import numpy as np

# 递归实现归并排序
def merge(aim_list, tmp_list, low, middle, high):
    """将2个已排序的子列表进行合并"""
    # i1为左列表的初始位置；i2为右列表的初始位置
    i1 = low
    i2 = middle+1
    for i in range(low, high+1):
        # 确定右列表比左列表小的边界 eg: [1,2] merge [4,5]
        if i1 > middle:
            tmp_list[i] = aim_list[i2]
            i2 += 1
        # 确定右列表比左列表小的边界 eg: [4,5] merge [1,2]
        elif i2 > high:
            tmp_list[i] = aim_list[i1]
        # 比较左后两个子列表，左<右，则tmp=左
        elif aim_list[i1] < aim_list[i2]:
            tmp_list[i] = aim_list[i1]
            i1 += 1
        else:
            tmp_list[i] = aim_list[i2]
            i2 += 1
    for i in range(low, high+1):
        aim_list[i] = tmp_list[i]


def merge_sort_helper(aim_list, tmp_list, low, high):
    """划分子列表"""
    if low < high:
        middle = (low+high)//2
        merge_sort_helper(aim_list, tmp_list, low, middle)
        merge_sort_helper(aim_list, tmp_list, middle+1, high)
        merge(aim_list, tmp_list, low, middle, high)


def merge_sort(aim_list):
    tmp_list = list([None for i in range(len(aim_list))])
    return merge_sort_helper(aim_list, tmp_list, 0, len(aim_list)-1)


def generate_list(size):
    aim_list = []
    for i in range(size):
        aim_list.append(random.randint(1,100))

    return aim_list


if __name__ == "__main__":
    # aim_list = generate_list(20)
    aim_list = np.random.randint(100, size=20)
    set_format = ''.join(['*']*30)
    print("%s before sort %s" % (set_format, set_format))
    print(aim_list)
    print("%s after sort %s" % (set_format, set_format))
    merge_sort(aim_list)
    print(aim_list)
    

输出：

****************************** before sort ******************************
[66 38  9 59 52 49 20 53  8 16 28 46 58 26 71  5 96 81 16 96]
****************************** after sort ******************************
[ 5  8  9 16 16 20 20 20 26 28 38 38 38 38 46 58 71 81 96 96]

参考书籍：《?数据结构（Python语言描述）》