玩蛇(Python) - 排序算法:希尔排序、归并排序、堆排序、快速排序

一、排序算法

本文介绍希尔排序(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##