数据结构 —— 手写排序算法

2024-01-10 10:44:08

数据结构 —— 手写排序算法

能手撸堆排序和快速排序,相信你在面试中已经能应付大部分排序问题了。

一、堆排序

建堆算法在面试中非常常见,我曾经就遇到过。因此为避免踩坑,特此开记录帖。堆必须是一棵完全二叉树,分为

  • 大根堆。每个父节点元素 >= 子节点
  • 小根堆。每个父节点元素 <= 子节点
一、参考文章或视频链接
[1] 【【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆】- bilibili
[2] 《算法》(第4版) - chapter 2.4 堆排序 - bilibili
# coding:utf-8
# @Time: 2024/1/5 下午9:10
# @Author: 键盘国治理专家
# @File: quick_sort.py
# @Description:

# 大根堆建堆,然后交换到数组最末尾就是升序排序了
def heapify(arr, n, i):
	largest = i # 初始化最大值为当前位置i
	left = 2*i + 1 # 左子节点
	right = 2*i + 2 # 右子节点
	
	#
	if left < n and arr[i] < arr[left]: # 左子节点存在且比当前位置大
		largest = left # 更新最大值为左子节点的位置
	if right < n and arr[largest] < arr[right] # 右子节点存在且比当前位置大
		largest = right
	if largest != i: # 最大值的位置已经被改动了,不再等于开始时的i了,则需要将最大值上浮
		arr[i], arr[largest] = arr[largest], arr[i]
		heapify(arr, n, largest) # 再递归重复此过程,堆交换后的子树继续堆化
	

def heap_sort(arr):
	n = len(arr)
	# (1)构建最大堆:从最后一个非叶子节点开始,依次进行堆化,也就是自底向上建堆,可以看参考视频[2]。最后一个非叶子节点?这样理解,如果将叶子节点视作一棵树,那么孤零零的一个节点本身就是一个堆。所以不需要建堆,但这不意味着这些叶子节点在随后的建堆过程中不参与交换,只是不以这些叶子节点为中心进行建堆。
	for i in range(n//2 - 1, -1, -1):
		heapify(arr, n, i) # arr为建堆数组,n表示建堆范围为[0,n-1]共n个,i表示堆arr[i]元素进行调整建堆
	for i in range(n-1, -1, -1):
		arr[i], arr[0] = arr[0], arr[i]
		heapify(arr, i, 0) # 对[0,i-1]的元素继续建堆

if __name__ == '__main__':
    # 示例用法
    nums = [10, 80, 30, 90, 40, 50, 70, -123]
    print("排序前的数组为", nums)
    heap_sort(nums)
    print("排序后的数组:", nums)
	

二、快速排序

二、参考文章或视频链接
[1] 《快速排序——hoare版本+挖坑法+双指针法》- CSDN
[2] 【快速排序(双指针法)动画演示】- bilibili

快速排序重在轴点pivot的选择与交换过程上。

# coding:utf-8
# @Time: 2024/1/5 下午9:10
# @Author: 键盘国治理专家
# @File: quick_sort.py
# @Description:


def quick_sort(nums, low, high):
    if low < high:
        # 找到轴的位置。这句话是说轴一旦确定了,就意味着这个元素已经被放置在数组的正确位置了,后面不会再变动,partition函数本身就带有排序性质的交换操作
        pivot = partition(nums, low, high)
        # print(arr)
        quick_sort(nums, low, pivot - 1)
        quick_sort(nums, pivot + 1, high)


def partition(nums, low, high):
    # (1)最左边的元素被选为轴点
    pivot_index = low

    while low < high:
        # (2)high从右往左遍历,直到找到一个比轴点小的数字,并交换
        while nums[high] > nums[pivot_index]:
            high -= 1
        if nums[pivot_index] > nums[high]:
            nums[pivot_index], nums[high] = nums[high], nums[pivot_index]
            pivot_index = high

        # (3)low从左往右遍历,直到找到一个比轴点大的数字,并交换
        while nums[low] < nums[pivot_index]:
            low += 1
        if nums[low] > nums[pivot_index]:
            nums[pivot_index], nums[low] = nums[low], nums[pivot_index]
            pivot_index = low

    # (4)返回轴点的最终位置
    return pivot_index


if __name__ == '__main__':
    nums = [10, 80, 30, 90, 40, 50, 70, -123]
    print("排序前的数组为", nums)
    quick_sort(nums, 0, len(nums) - 1)
    print("排序后的数组为", nums)

文章来源:https://blog.csdn.net/weixin_44327736/article/details/135003304
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。