温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

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

发布时间:2020-06-19 11:40:05 来源:网络 阅读:731 作者:Jayce_SYSU 栏目:编程语言
# -*- 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()
向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI