【2】数据结构与算法--python语言实现各类排序算法(快排，简单选择，直接插入，堆排序，二路归并，冒泡排序)

水深无声 2022-04-02 07:56 139阅读 0赞

def bubble_sort(a):
        # 冒泡排序
        for i in range(len(a)):
            # 主要是判断当前这一轮过去有没有交换，
            # 如果有交换就将其赋值为True,如果没交换说明这一轮过去顺序都是从小到大，直接跳出循环即可。
            sign = False
            for j in range(0, len(a)-1-i):
                if a[j] > a[j+1]:
                    temp = a[j+1]
                    a[j+1] = a[j]
                    a[j] = temp
                    sign = True
            if sign == False:
                break
        return a
    
    def insert_sort(a):
        # 直接插入排序
        for i in range(len(a)):
            temp = a[i]
            j = i-1
            while a[j] > temp and j >= 0:
                a[j+1] = a[j]
                j -= 1
            a[j+1] = temp
        return a
    
    def select_sort(a):
        # 简单选择排序
        for i in range(len(a)):
            k = i
            min = a[i]
            for j in range(i+1, len(a)):
                if a[j] < min:
                    min = a[j]
                    k = j
    
            temp = a[k]
            a[k] = a[i]
            a[i] = temp
        return a
    
    
    def quick_sort(a, low, high):
        # 快速排序算法
        i = low
        j = high
        if low > high:
            return
        if i < j:
            temp = a[i]
            while i != j:
                while j > i and a[j] > temp:
                    j -= 1
                if j > i:
                    a[i] = a[j]
                    i += 1
                while j > i and a[i] < temp:
                    i += 1
                if j > i:
                    a[j] = a[i]
                    j -= 1
            a[i] = temp
        quick_sort(a, low, i-1)
        quick_sort(a, i+1, high)
        return a
    
    
    # 下面是归并排序的算法  分两步: 1.形成初始化归并段。 2.归并阶段
    def fen_duan(list):
        # 分段
        if len(list) <= 1:
            return list
        zhong = int(len(list) / 2)
        left = fen_duan(list[:zhong])   # 一直递归下去进行分段直到剩下一个数
        right = fen_duan(list[zhong:])
        return merge(left, right)
    def merge(left, right):
        # 合并段+排序
        i, j = 0, 0
        array = []
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                array.append(left[i])
                i += 1
            elif left[i] > right[j]:
                array.append(right[j])
                j += 1
        if i < len(left):
            array += left[i:]
        if j < len(right):
            array += right[j:]
        return array
    
    # 下面是堆排序的算法(本次采用大顶堆)  # 一个是排序  一个是调整堆
    def Sift(a, low, high):
        # 调整堆
        i = low
        j = 2*i   # 当前这个双亲的左孩子开始调整树
        temp = a[i]
        while j <= high:
            if j < high and a[j] < a[j+1]:   # 如果右孩子大,则将j指向右孩子
                j += 1
            if temp < a[j]:    # 此时双亲小于右孩子  则右孩子和双亲换位置
                a[i] = a[j]
                i = j          # 修改i和j的值, 以便继续向下调整
                j = 2*i
            else:
                break
        a[i] = temp
    def heapSort(a):
        for i in range(len(a)//2-1, -1, -1):   # len(a)//2-1 是最后一个双亲节点的索引
            Sift(a, i, len(a)-1)
        for i in range(len(a)-1, -1, -1):
            temp = a[0]    # 将头取出来
            a[0] = a[i]    # 将树的最后一个节点放在头
            a[i] = temp    # 将头放到最后
            Sift(a, 0, i-1)
        return a
    
    
    
    if __name__ == '__main__':
        a = [3, 4, 31, 61, 16, 5, 0, 21, 7]    # 随机给出一些数字
    
        # result_b = bubble_sort(a)
        # print("冒泡排序的结果:", result_b)
    
        # result_i = insert_sort(a)
        # print("直接插入排序的结果:", result_i)
    
        # result_s = select_sort(a)
        # print("简单选择排序的结果:", result_s)
    
        # result_q = quick_sort(a, 0, len(a)-1)
        # print("快速排序的结果:", result_q)
    
        # result_m = fen_duan(a)
        # print("归并排序的结果:", result_m)
    
        result_h = heapSort(a)
        print("堆排序的结果:", result_h)