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