Python3实现快速排序、归并排序、堆

发布时间：2019-09-25 08:26:07编辑：auto阅读（1783）

# -*- coding: utf-8 -*-
# @Time         : 2019-03-26 16:46
# @Author       : Jayce Wong
# @ProjectName  : leetcode
# @FileName     : sorting.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

import random

def quick_sort(data):
    """
    对于每一轮排序，先随机选取范围内的一个下标，该下标对应的值称为主元，然后将小于主元的值挪到主元
    的左边，大于主元的值挪到主元的右边，即确保主元在正确的位置。然后下一轮只需要对主元左边的数组和
    右边的数组分别排序即可，数组大小减为原来的一半。
    每轮排序确定一个主元，该轮排序完成后待排序的两个数组的长度变为原来的一半，可以看做是一个树，
    根节点是原数组，每一轮会分裂一次，每个节点被分裂成2个子节点，直到该节点长度为1，不需再进行排序
    为止，这样就一共需要logN轮，每轮每部需要比较N次，即时间复杂度nlogn
    快排是不稳定排序(相同大小的元素排序后不一定按照原顺序)
    :param data: 待排序的数组
    """
    def sort(start, end):
        pivot = partition(start, end)
        if pivot > start:
            sort(start, pivot - 1)
        if pivot < end:
            sort(pivot + 1, end)

    def partition(start, end):
        idx = random.randint(start, end)  # 随机选择一个idx
        # 先将idx下标所在的值(主元)和末端的值交换
        data[idx], data[end] = data[end], data[idx]
        position = start  # position是下一个小于主元的值应在的位置
        for i in range(start, end):
            # 如果一个值小于主元，则检查它是否在正确的位置，不正确的话则进行调整，使得它落到应在
            # 的位置
            if data[i] < data[end]:
                if i != position:
                    data[position], data[i] = data[i], data[position]
                position += 1
        # 还原主元应在的位置
        data[position], data[end] = data[end], data[position]
        return position

    if not data:
        return
    sort(0, len(data) - 1)

def merge_sort(data):
    """
    先将数组不断进行对半分裂直到不可再分(最长子数组长度为1)，然后进行归并，归并的时候每次从两个
    数组中选择最小的元素。
    归并排序是稳定算法，时间复杂度为nlogn
    :param data: 待排序的数组
    """
    def sort(start, end):
        if start < end:
            mid = (start + end) >> 1
            sort(start, mid)
            sort(mid + 1, end)
            merge(start, mid, end)

    def merge(start, mid, end):
        p1, p2 = start, mid + 1
        while p1 <= mid and p2 <= end:
            if data[p1] < data[p2]:
                temp.append(data[p1])
                p1 += 1
            else:
                temp.append(data[p2])
                p2 += 1
        if p1 <= mid:
            temp.extend(data[p1: mid + 1])
        if p2 <= end:
            temp.extend(data[p2: end + 1])

        # 【需要将辅助数组中的数还原到data中】
        while temp:
            data[start] = temp.pop(0)
            start += 1

    if not data:
        return
    temp = []  # 建立全局辅助数组，避免递归过程不断创建
    sort(0, len(data) - 1)

def heap_sort(data):
    """
    堆排序是不稳定的一种排序算法，其时间复杂度是O(nlogn)

    当需要升序排序的时候，构建最大堆，反之构建最小堆。

    最大堆的定义是对于每一个非叶子节点，它的值大于等于它的子节点。最小堆的定义类似。

    以升序排序为例，堆排首先是从最后一个非叶子节点开始往左往上构建最大堆，目的是减少重复性工作，
    因为如果自顶向下构建最大堆的话难度大，而自底向上构建最大堆的话在对第x层的某个节点构建最大堆的
    时候可以确保第x+1层及以下的树已满足最大堆的定义
    :param data: 待排序的元素
    """
    def adjustHeap(cur_idx, length):
        """

        :param cur_idx: 待调整的子树的根节点位置
        :param length: 树中剩余的元素个数。随着排序的进行，堆顶元素(根节点)会逐个被删除，
                       导致树中元素不断减少
        """
        temp = data[cur_idx]  # 先记录当前位置的元素
        # 由于最大堆的定义是父节点元素大于等于其子节点元素，因此将当前位置的元素和它的子节点元素
        # 进行大小比较,
        k = 2 * cur_idx + 1  # 左子节点的位置
        while k < length:  # 只在树内遍历
            # 如果右子节点的元素更大，则将k定位到右子节点，
            # 因为父节点的值需要不小于最大子节点的值
            if k + 1 < length and data[k] < data[k + 1]:
                k += 1

            # 如果子节点的元素大于根节点，则将子节点的值赋给父节点
            # 如果这里不使用赋值而是交换的话，会有多余的操作(如果这次调整需要不止一次交换的话)
            if data[k] > temp:
                data[cur_idx] = data[k]
                # 这时cur_idx保存的是temp可能要去到的位置，但是由于还有剩余的孙子节点没有比较
                # 所以这里先不用交换，而是记录下temp可能要去到的位置，最后再将其放到正确的位置
                cur_idx = k
            # 如果上层的子节点已经小于父节点，那么孙子节点一定不会大于父节点，因为我们已经构建了
            # 一个最大堆(在初始化构建最大堆时，我们是从最后一个非子节点开始自底向上构建的，所以
            # 在处理上层节点的时候其下层节点已经是符合最大堆定义的了，因此也符合这里的break条件)
            else:
                break
            # 检查剩余的子节点
            k = 2 * k + 1

        data[cur_idx] = temp  # 将temp元素还原到正确的位置

    if not data:
        return

    """ 初始化构建最大堆 """
    # 从最后一个非叶子节点开始，往左遍历，当第x层遍历完之后从第x-1层的最右边开始往左遍历
    # 每次调整该节点使得满足最大堆的要求
    for i in range((len(data) >> 1) - 1, -1, -1):
        adjustHeap(i, len(data))

    # 从构建好的最大堆取出堆顶元素(也就是最大值)，然后放到数组末尾(即将这个节点删除)
    # 删除之后需要重新调整堆的结构以满足最大堆的定义。
    # 由于上一步已经构建了一个最大堆，因此这里只需要对新的根节点的元素进行调整即可
    for j in range(len(data) - 1, 0, -1):
        data[j], data[0] = data[0], data[j]
        adjustHeap(0, j)

def main():
    data = []
    for _ in range(10):
        data.append(random.randint(0, 9))

    print(data)
    quick_sort(data)
    merge_sort(data)
    heap_sort(data)
    print(data)

if __name__ == '__main__':
    main()

关键字：