专栏首页python3Python3实现快速排序、归并排序、堆

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

# -*- 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()

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python_冒泡排序

    从小到大的排序:(最前面的数和一步步和后面的数比较,如果大于则交换,如果不大于则继续循环)

    py3study
  • python(实操4):录音文件的读取、

    py3study
  • Python 建模步骤

    py3study
  • 一日一技:如何通过迭代器精简你的代码

    假设有一个 Redis 集合,里面有 N 条数据,你不停从里面lpop数据,直到某一条数据的值为'Stop'字符串为止(已知里面必有一条数据为'Stop'字符串...

    青南
  • 数据可视化|二维统计直方图和三维统计分布图

    二维统计直方图的变量x和y的类型必须是数值型。在x和y轴找到各自的最大值和最小值,使得测定的所有数据都包含在【Xmin,Xmax】,【Ymin,Ymax】之间。...

    黑妹的小屋
  • 数据科学家常遇到的10个错误

    数据科学家是“在统计方面比任何软件工程师都要出色,在软件工程方面比任何统计学家都出色的人”。许多数据科学家都有统计学背景,但很少有软件工程经验。我是一位高级数据...

    磐创AI
  • 数据科学家常犯的十大编程错误

    数据科学家是“比任何软件工程师都更擅长统计,比任何软件工程师都更擅长软件工程的的统计学家”。许多数据科学家都有统计学背景却缺乏在软件工程方面的经验。我是资深的数...

    AiTechYun
  • datatables,表格

    windseek
  • 数据科学家易犯的十大编码错误,你中招了吗?

    我是一名高级数据科学家,在 Stackoverflow 的 python 编码中排前 1%,而且还与众多(初级)数据科学家一起工作。下文列出了我常见到的 10 ...

    统计学家
  • 数据科学家易犯的十大编码错误,你中招了吗?

    我是一名高级数据科学家,在 Stackoverflow 的 python 编码中排前 1%,而且还与众多(初级)数据科学家一起工作。下文列出了我常见到的 10 ...

    机器之心

扫码关注云+社区

领取腾讯云代金券