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