一、排序算法
本文介绍希尔排序(Shell Sort)、归并排序(Merge Sort)、堆排序(Heap Sort)、快速排序(Quick Sort)。
二、排序算法实例
2.1 希尔排序(Shell Sort)原理
希尔排序(Shell Sort)是直接插入排序算法的优化改进版本，或者缩小增量排序。是法因 D.L.Shell 于 1959 年提出而得名的算法。
直接插入排序通常会在基本有序时，效率比较高。再有就是在待排序的记录比较少时，效率也会比较高。这是希尔排序算法出发点。
它属于插入排序的一种，也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。
基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下，效率是很高的，因此希尔排序在时间效率比直接插入排序有较大提高。
算法的基本流程：
1) 将整个有 n 个元素的数组序列分割分成 gap (gap = n/2) 个子序列，第 1 个数据和第 n/2+1 个数据为一组。
2) 一次循环中，在每一个子序列中分别采用直接插入排序。
3) 然后缩小间隔 gap，将 gap = gap/2, 然后变为 gap 个子序列，重复上述的子序列划分和排序工作。
4) 不断重复上述过程，随着序列减少最后变为1个，也就完成了整个排序。
2.2 归并排序(Merge Sort)原理
归并排序(Merge Sort)是一种非常高效的排序方式，它用了分治(Divide and Conquer)的思想，将已有序的子序列合并，得到完全有序的序列。即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序适用于数据量大，并且对稳定性有要求的场景。
算法的基本流程：
分解分割(Divide)：将待排序序列从中间分成两个子序列。
递归解决(Conquer)：对两个子序列分别进行递归，直到子序列的长度为1。
合并序列(Combine)：合并两个有序子序列，得到完整的有序序列。
注：当有 n 个记录时，需进行 logn 轮归并排序，每一轮归并，其比较次数不超过 n，归并排序的时间复杂度为 O(nlogn)。
2.3 堆排序(Heap Sort)原理
堆排序(Heap Sort)是一种高效的排序算法，它利用堆的数据结构来实现排序。
堆排序由Floyd和Williams在1964年共同发明，是对简单选择排序算法的优化，其出发点是：简单选择排序在遍历时，在待排序的n个元素中，需进行n-1次比较，才能选择出最小的元素，但没有将每次遍历时比较的结果保存下来，导致后续遍历时仍需进行重复操作，因此导致元素比较次数较多。
堆排序就是通过堆这种结构，实现了在选择出最小元素的同时，保存了比较结果，用于后续的操作，从而减少比较次数，提高排序效率。
在堆排序中，我们需要使用堆的数据结构。堆是一种近似完全二叉树，它满足以下两条件：
1) 父节点的值大于或等于子节点的值（大根堆）或父节点的值小于或等于子节点的值（小根堆）。
2) 所有叶子节点都在同一层上，或者说深度最多相差1。
算法的基本流程：
1) 构建一个初始堆：将待排序的数据构建成一个堆结构。这一步通常涉及将数组转换为一个堆，需要从最后一个非叶子节点开始，从右到左，逐个将它们“下沉”到合适的位置，以满足堆的性质。
2) 堆排序：从堆中不断移除根节点，并将其放置在已排序的部分。重复此过程，直到堆为空。
3) 结果：排序完成后，数组中的数据已按升序或降序排列，具体取决于堆是大顶堆还是小顶堆。
2.4 快速排序(Quick Sort)原理
快速排序(Quick Sort)，使用分治法(Divide and Conquer)策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
算法的基本流程：
1) 从数列中挑出一个元素，称为"基准"（Pivot），
2) 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（Partition）操作。
3) 通过一趟排序后，将原序列分为两部分，使得前面的比后面的小，然后再依次对前后进行拆分进行快速排序，递归该过程，直到序列中所有记录均有序。
2.5 代码(附详细注释)
#-*- coding:utf-8 -*-
import time
import random
def shell_sort(raw_list:list[int]):
#记录开始时间，用于计算排序时长
start_time = time.time()*1000
print('shell_sort sorting start time: ', start_time)
# print('raw_list : ', raw_list)
shell_sort_length = len(raw_list)
#获取比较步长
gap = shell_sort_length//2
#分解子序列进行分别排序，直到子序列为1个
while gap > 0:
#从步长元素的下一个元素开始比较
for i in range(gap, shell_sort_length):
#临时存储用于比较的元素值
tmp = raw_list[i]
j = i
#针对该元素值进行插入排序，由于前面的数已经是有序的了（从小到大的顺序）
#仅需将当前元素按照直接插入的方式插入有序的位置即可
#raw_list[j - gap]是下标索引小的位置的值，所以如果大于目标值，则交换位置
while j >= gap and raw_list[j - gap] > tmp:
raw_list[j] = raw_list[j - gap]
#仅比较同一个子序列里面的值即可
j -= gap
raw_list[j] = tmp
gap = gap//2
end_time = time.time()*1000
print('shell_sort sorting end time: ', end_time)
# print('sorted_list : ', raw_list)
print('shell_sort耗费时长(MS): ', (end_time - start_time))
print('------------------------------------------------------------')
def merge_sort(raw_list:list[int]):
merge_sort_length = len(raw_list)
#如果仅有一个元素，已经是有序的，则直接返回
if merge_sort_length <= 1:
return raw_list
#将要判断的序列分成两个队列，进行排序和合并
mid = merge_sort_length//2
return merge(merge_sort(raw_list[:mid]), merge_sort(raw_list[mid:]))
#将两个排序的列表合并成一个列表
def merge(raw_list1:list[int], raw_list2:list[int]):
#结果存储列表
merge_result = []
#将两个有序（从小到大）的列表逐个合并
#从只有1个元素的序列开始，就是有序的序列，所以后续的序列都是有序的。
while raw_list1 and raw_list2:
if raw_list1[0] < raw_list2[0]:
merge_result.append(raw_list1.pop(0))
else:
merge_result.append(raw_list2.pop(0))
#处理两个队列不等长的情况
if raw_list1:
merge_result += raw_list1
if raw_list2:
merge_result += raw_list2
#返回合并后的队列
return merge_result
#堆排序
def heap_sort(raw_list:list[int]):
#记录开始时间，用于计算排序时长
start_time = time.time()*1000
print('heap_sort sorting start time: ', start_time)
# print('raw_list : ', raw_list)
merge_sort_length = len(raw_list)
#构建一个大顶锥，从非叶子节点开始，将大值浮出来,确定根节点是最大值
#原理：在二叉树中，如果深度由K，那么整个树最多有2^k - 1个节点(2^k - 1) - (2^(k-1) - 1)) = (2^k - 1)/2
for i in range(merge_sort_length//2 - 1, -1, -1):
heap_tree(raw_list, merge_sort_length, i)
#确保根节点是最大值，然后将根节点依次放在最后一个位置，最终得到有序列表
for i in range(merge_sort_length - 1, 0,- 1):
raw_list[i], raw_list[0] = raw_list[0], raw_list[i]
#不考虑已经排序出来的最值们，所以长度变为i
heap_tree(raw_list, i, 0)
end_time = time.time()*1000
print('heap_sort sorting end time: ', end_time)
# print('sorted_list : ', raw_list)
print('heap_sort耗费时长(MS): ', (end_time - start_time))
print('------------------------------------------------------------')
#二叉树可以使用List来表示,原理：在二叉树中的第i层，最多由2^(i-1)的节点
def heap_tree(raw_list:list[int], merge_sort_length:int, index:int):
#根是最大值, 初始化
lagest_value_index = index
left_child_index = 2 * index + 1
right_child_index = 2 * index + 2
#如果左子节点存在且大于根节点
if left_child_index < merge_sort_length \
and raw_list[left_child_index] > raw_list[lagest_value_index]:
lagest_value_index = left_child_index
#如果右子节点存在且大于根节点
if right_child_index < merge_sort_length \
and raw_list[right_child_index] > raw_list[lagest_value_index]:
lagest_value_index = right_child_index
#如果最大节点不是根节点,做相应节点交换，保证根节点是最大值
if lagest_value_index != index:
raw_list[index], raw_list[lagest_value_index] = raw_list[lagest_value_index], raw_list[index]
#子节点重新排序
heap_tree(raw_list, merge_sort_length, lagest_value_index)
#快速排序算法
def quick_sort(raw_list:list[int], low_partition_index:int, high_partition_index:int):
#如果低值区和高级区重合，则直接返回
if low_partition_index >= high_partition_index:
return raw_list
#取第1个值为基准值
pivot = raw_list[low_partition_index]
#定义指针，用于滑动处理值
low = low_partition_index
high = high_partition_index
while low < high:
#从右向左扫描，获取小于基准值的元素
while low < high and raw_list[high] >= pivot:
high -= 1
raw_list[low] = raw_list[high]
#从左向右扫描吗，获取大于基准值的元素
while low < high and raw_list[low] <= pivot:
low += 1
raw_list[high] = raw_list[low]
#中间值设置，低值区索引和高值取索引相遇，中间值就是基准值的位置
raw_list[high] = pivot
#低值区和高值区分开计算，快速排序
quick_sort(raw_list, low_partition_index, low-1)
quick_sort(raw_list, low + 1, high_partition_index)
return raw_list
if __name__ == '__main__':
#实例
#输入参数生成
raw_list1 = []
raw_list2 = []
raw_list3 = []
raw_list4 = []
for i in range(2000):
raw_list1.append(i)
raw_list2.append(i)
raw_list3.append(i)
raw_list4.append(i)
random.shuffle(raw_list1)
shell_sort(raw_list1)
#记录开始时间，用于计算排序时长
random.shuffle(raw_list2)
start_time = time.time()*1000
print('merge_sort sorting start time: ', start_time)
# print('raw_list : ', raw_list2)
raw_list2 = merge_sort(raw_list2)
end_time = time.time()*1000
print('merge_sort sorting end time: ', end_time)
# print('sorted_list : ', raw_list2)
print('merge_sort耗费时长(MS): ', (end_time - start_time))
print('------------------------------------------------------------')
random.shuffle(raw_list3)
heap_sort(raw_list3)
#记录开始时间，用于计算排序时长
random.shuffle(raw_list4)
start_time = time.time()*1000
print('quick_sort sorting start time: ', start_time)
# print('raw_list : ', raw_list4)
raw_list4 = quick_sort(raw_list4, 0, len(raw_list4) - 1)
end_time = time.time()*1000
print('quick_sort sorting end time: ', end_time)
# print('sorted_list : ', raw_list4)
print('quick_sort耗费时长(MS): ', (end_time - start_time))
print('------------------------------------------------------------')2.6 代码验证
PS D:\Shangouxuehui_Git\PythonAlgorithm-main> & D:/Python312/python.exe d:/Shangouxuehui_Git/PythonAlgorithm-main/sgxh_sort_2.py
shell_sort sorting start time: 1712411652473.4797
shell_sort sorting end time: 1712411652476.2554
shell_sort耗费时长(MS): 2.775634765625
------------------------------------------------------------
merge_sort sorting start time: 1712411652477.0864
merge_sort sorting end time: 1712411652479.6394
merge_sort耗费时长(MS): 2.552978515625
------------------------------------------------------------
heap_sort sorting start time: 1712411652480.3088
heap_sort sorting end time: 1712411652483.284
heap_sort耗费时长(MS): 2.97509765625
------------------------------------------------------------
quick_sort sorting start time: 1712411652483.284
quick_sort sorting end time: 1712411652485.2776
quick_sort耗费时长(MS): 1.99365234375
------------------------------------------------------------##山狗学会 License Start##
转载请注明出处，"今日头条"创作者"山狗学会“ ，注明出处即授权，未注明出处罚款100万元
主页链接：山狗学会主页
##山狗学会 License End##
本文暂时没有评论，来添加一个吧(●'◡'●)