【Python 算法零基础 4.排序 ⑩ 希尔排序】

当左索引小于右索引时，结束递归。

L_cl

908人浏览 · 2025-06-05 16:59:26

L_cl · 2025-06-05 16:59:26 发布

目录

一、算法描述

二、核心思路

三、代码分析

① 初始化间隔（增量）

② 分组与插入排序

③ 缩小间隔

④ 终止条件

四、实战练习

912. 排序数组

算法与思路

① 希尔排序

② 排序数组

原地踏步过多久，在这新的起始点站的是我

—— 25.6.1

选择排序回顾

① 遍历数组：从索引 0 到 n-1（n 为数组长度）。

② 每轮确定最小值：假设当前索引 i 为最小值索引 min_index。从 i+1 到 n-1 遍历，若找到更小元素，则更新 min_index。

③ 交换元素：若 min_index ≠ i，则交换 arr[i] 与 arr[min_index]。

'''
① 遍历数组：从索引 0 到 n-1（n 为数组长度）。

② 每轮确定最小值：假设当前索引 i 为最小值索引 min_index。从 i+1 到 n-1 遍历，若找到更小元素，则更新 min_index。

③ 交换元素：若 min_index ≠ i，则交换 arr[i] 与 arr[min_index]。
'''

def selectionSort(arr: List[int]):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        if min_index != i:
            arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

冒泡排序回顾

① 初始化：设数组长度为 n。

② 外层循环：遍历 i 从 0 到 n-1（共 n 轮）。

③ 内层循环：对于每轮 i，遍历 j 从 0 到 n-i-2。

④ 比较与交换：若 arr[j] > arr[j+1]，则交换两者。

⑤ 结束条件：重复步骤 2-4，直到所有轮次完成。

'''
① 初始化：设数组长度为 n。

② 外层循环：遍历 i 从 0 到 n-1（共 n 轮）。

③ 内层循环：对于每轮 i，遍历 j 从 0 到 n-i-1。

④ 比较与交换：若 arr[j] > arr[j+1]，则交换两者。

⑤ 结束条件：重复步骤 2-4，直到所有轮次完成。
'''
def bubbleSort(arr: List[int]):
    n = len(arr)
    for i in range(n):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

插入排序回顾

① 遍历未排序元素：从索引 1 到 n-1。

② 保存当前元素：将 arr[i] 存入 current。

③ 元素后移：从已排序部分的末尾（索引 j = i-1）向前扫描，将比 current 大的元素后移。直到找到第一个不大于 current 的位置或扫描完所有元素。

④ 插入元素：将 current 放入 j+1 位置。

'''
① 遍历未排序元素：从索引 1 到 n-1。

② 保存当前元素：将 arr[i] 存入 current。

③ 元素后移：从已排序部分的末尾（索引 j = i-1）向前扫描，将比 current 大的元素后移。直到找到第一个不大于 current 的位置或扫描完所有元素。

④ 插入元素：将 current 放入 j+1 位置。
'''
def insertSort(arr: List[int]):
    n = len(arr)
    for i in range(n):
        current = arr[i]
        j = i - 1
        while current < arr[j] and j >0:
            arr[j+1] = arr[j]
            j -= 1
        arr[j + 1] = current
    return arr

计数排序回顾

① 初始化：设数组长度为 n，元素最大值为 r。创建长度为 r+1 的计数数组 count，初始值全为 0。

② 统计元素频率：遍历原数组 arr，对每个元素 x，将 count[x] 加 1。

③ 重构有序数组：初始化索引 index = 0。遍历计数数组 count，索引 v 从 0 到 r，若 count[v] > 0，则将 v 填入原数组 arr[index]，并将 index 加 1。count[v] - 1，重复此步骤直到 count[v] 为 0。

④ 结束条件：当计数数组遍历完成时，排序结束。

'''
输入全为非负整数，且所有元素 ≤ r

① 初始化：设数组长度为 n，元素最大值为 r。创建长度为 r+1 的计数数组 count，初始值全为 0。

② 统计元素频率：遍历原数组 arr，对每个元素 x，将 count[x] 加 1。

③ 重构有序数组：初始化索引 index = 0。遍历计数数组 count，索引 v 从 0 到 r，
若 count[v] > 0，则将 v 填入原数组 arr[index]，并将 index 加 1。
count[v] - 1，重复此步骤直到 count[v] 为 0。

④ 结束条件：当计数数组遍历完成时，排序结束。
'''

def countingSort(arr: List[int], r: int):
    # count = [0] * len(r + 1)
    count = [0 for i in range(r + 1)]
    for x in arr:
        count[x] += 1
    index = 0
    for v in range(r + 1):
        while count[v] > 0:
            arr[index] = v
            index += 1
            count[v] -= 1
    return arr

归并排序回顾

Ⅰ、递归分解列表

① 终止条件：若链表为空或只有一个节点（head is None 或 head.next is None），直接返回头节点。

② 快慢指针找中点：初始化 slow 和 fast 指针，slow 指向头节点，fast 指向头节点的下一个节点。fast 每次移动两步，slow 每次移动一步。当 fast 到达末尾时，slow 恰好指向链表的中间节点。

③ 分割链表：将链表从中点断开，head2 指向 slow.next（后半部分的头节点）。将 slow.next 置为 None，切断前半部分与后半部分的连接。

④ 递归排序子链表：对前半部分（head）和后半部分（head2）分别递归调用 mergesort 函数。

Ⅱ、合并两个有序列表

① 创建虚拟头节点：创建一个值为 -1 的虚拟节点 zero，用于简化边界处理。使用 current 指针指向 zero，用于构建合并后的链表。

② 比较并合并节点：遍历两个子链表 head1 和 head2，比较当前节点的值：若 head1.val <= head2.val，将 head1 接入合并链表，并移动 head1 指针。否则，将 head2 接入合并链表，并移动 head2 指针。每次接入节点后，移动 current 指针到新接入的节点。

③ 处理剩余节点：当其中一个子链表遍历完后，将另一个子链表的剩余部分直接接入合并链表的末尾。

④ 返回合并后的链表：虚拟节点 zero 的下一个节点即为合并后的有序链表的头节点。

'''
Ⅰ、递归分解列表

① 终止条件：若链表为空或只有一个节点（head is None 或 head.next is None），直接返回头节点。

② 快慢指针找中点：初始化 slow 和 fast 指针，slow 指向头节点，fast 指向头节点的下一个节点。fast 每次移动两步，slow 每次移动一步。当 fast 到达末尾时，slow 恰好指向链表的中间节点。

③ 分割链表：将链表从中点断开，head2 指向 slow.next（后半部分的头节点）。将 slow.next 置为 None，切断前半部分与后半部分的连接。

④ 递归排序子链表：对前半部分（head）和后半部分（head2）分别递归调用 mergesort 函数。

Ⅱ、合并两个有序列表

① 创建虚拟头节点：创建一个值为 -1 的虚拟节点 zero，用于简化边界处理。使用 current 指针指向 zero，用于构建合并后的链表。

② 比较并合并节点：遍历两个子链表 head1 和 head2，比较当前节点的值：若 head1.val <= head2.val，将 head1 接入合并链表，并移动 head1 指针。否则，将 head2 接入合并链表，并移动 head2 指针。每次接入节点后，移动 current 指针到新接入的节点。

③ 处理剩余节点：当其中一个子链表遍历完后，将另一个子链表的剩余部分直接接入合并链表的末尾。

④ 返回合并后的链表：虚拟节点 zero 的下一个节点即为合并后的有序链表的头节点。
'''
def mergesort(self, head: ListNode):
    if head is None or head.next is None:
        return head
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    head2 = slow.next
    slow.next = None
    return self.merge(self.mergesort(head), self.mergesort(head2))

def merge(self, head1: ListNode, head2: ListNode):
    zero = ListNode(-1)
    current = zero
    while head1 and head2:
        if head1.val <= head2.val:
            current.next = head1
            head1 = head1.next
        else:
            current.next = head2
            head2 = head2.next
        current = current.next
    current.next = head1 if head1 else head2
    return zero.next

快速排序回顾

Ⅰ、分区函数 Partition

① 随机选择基准元素：根据左右边界下标随机选择基准元素（选择的是元素并非下标），将基准元素赋值变量进行后续比较

② 交换基准元素：将基准元素移动到最左边，将基准元素存储在变量中，

③ 分区操作：对于基准元素右边的元素，找到第一个小于基准元素的值，移动到最左边；对于基准元素左边的元素，找到第一个大于基准元素的值，移动到最右边

④ 返回基准元素的最终位置：循环执行完毕后，基准元素左边的值都小于它，基准元素右边的值都大于它

Ⅱ、递归快速排序函数

① 定义递归终止条件：当左索引小于右索引时，结束递归

② 分区操作： 执行第一次分区操作，找到基准元素

③ 递归调用分区函数：将基准元素的左边、右边部分分别传入递归函数进行排序

'''
Ⅰ、分区函数 Partition

① 随机选择基准元素：根据左右边界下标随机选择基准元素（选择的是元素并非下标），将基准元素赋值变量进行后续比较

② 交换基准元素：将基准元素移动到最左边，将基准元素存储在变量中，

③ 分区操作：对于基准元素右边的元素，找到第一个小于基准元素的值，移动到最左边；对于基准元素左边的元素，找到第一个大于基准元素的值，移动到最右边

④ 返回基准元素的最终位置：循环执行完毕后，基准元素左边的值都小于它，基准元素右边的值都大于它

Ⅱ、递归排序函数

① 定义递归终止条件：当左索引小于右索引时，结束递归

② 分区操作： 执行第一次分区操作，找到基准元素

③ 递归调用分区函数：将基准元素的左边、右边部分分别传入递归函数进行排序
'''

def Partition(arr, left, right):
    idx = random.randint(left, right)
    arr[left], arr[idx] = arr[idx], arr[left]
    l = left
    r = right
    x = arr[l]
    while l < r:
        while l < r and x < arr[r]:
            r -= 1
        if l < r:
            arr[l], arr[r] = arr[r], arr[l]
            l += 1

        while l < r and x > arr[l]:
            l += 1
        if l < r:
            arr[l], arr[r] = arr[r], arr[l]
            r -= 1
    return l

def quickSort(arr, l, r):
    if l >= r:
        return
    node = self.quickSort(l, r)
    self.quickSort(arr, l, node-1)
    self.quickSort(arr, node+1, r)
    return arr

桶排序回顾

① 初始化桶和频率数组： 创建字符长度+1的桶bucket，索引 i 表示频率为 i 的字符列表；长度为max的频率数组count，用于记录每个字符的出现次数

② 统计字符频率：通过 ord(char) 获取字符的ASCII码，作为频率数组的索引

③ 将字符按照频率放入桶中：遍历频率数组，将每个字符以频率作为索引放入数组中

④ 返回桶数组：返回桶数组，其中每个桶包含对应频率的字符列表

def bucketSort(arr, max_val):  # 移除 max_val 表示字符编码最大值（如 256）
    n = len(arr)
    # 初始化桶：索引范围 [0, max_val-1]
    bucket = [[] for _ in range(max_val)]
    
    # 分布：按字符编码放入桶
    for char in arr:
        bucket[ord(char)].append(char)  # 索引 = 字符编码值
    
    # 合并桶（索引升序即字符升序）
    sorted_arr = []
    for b in bucket:
        sorted_arr.extend(b)  # 每个桶内元素已按插入顺序排列
    
    return sorted_arr  # 返回排序后的一维数组

基数排序

① 初始化参数和辅助数组：设置最大元素数MAX_N为 50000，最大位数MAX_T为 8，进制BASE为 10；计算并存储基数的各次幂（如 10⁰, 10¹, ..., 10⁷）到数组PowOfBase中

② 预处理数组元素：为每个元素加上BASE^(MAX_T-1)（即 10⁷），确保所有元素变为正数；这一步是为了处理可能的负数输入，将其转换为正数进行排序

③ 按位进行多轮排序：从最低有效位（个位）开始，逐位进行处理（共进行MAX_T轮）

分配阶段：将元素分配到对应的桶（0-9）中对每个元素，计算当前位上的数字（通过整除和取模运算）

收集阶段：按桶的顺序（0 到 9）依次收集元素；将收集的元素依次放回原数组，覆盖原有的顺序

④ 恢复原始数值：排序完成后，从每个元素中减去BASE^(MAX_T-1)（即 10⁷）；恢复元素的原始值，完成排序过程

'''
基数排序

① 初始化参数和辅助数组：设置最大元素数MAX_N为 50000，最大位数MAX_T为 8，进制BASE为 10；计算并存储基数的各次幂（如 10⁰, 10¹, ..., 10⁷）到数组PowOfBase中

② 预处理数组元素：为每个元素加上BASE^(MAX_T-1)（即 10⁷），确保所有元素变为正数；这一步是为了处理可能的负数输入，将其转换为正数进行排序

③ 按位进行多轮排序：从最低有效位（个位）开始，逐位进行处理（共进行MAX_T轮）

        分配阶段：将元素分配到对应的桶（0-9）中对每个元素，计算当前位上的数字（通过整除和取模运算）

        收集阶段：按桶的顺序（0 到 9）依次收集元素；将收集的元素依次放回原数组，覆盖原有的顺序

④ 恢复原始数值：排序完成后，从每个元素中减去BASE^(MAX_T-1)（即 10⁷）；恢复元素的原始值，完成排序过程
'''
    MAX_N = 50000    # 最多的元素数
    MAX_T = 8        # 元素的最大位数
    BASE = 10        # 定义数字的进制

    def RedixSort(self, arr):
        n = len(arr)
        PowOfBase = [1 for i in range(self.MAX_T)]    # 代表BASE的多少次方
        for i in range(1, self.MAX_T):
            PowOfBase[i] = PowOfBase[i - 1] * self.BASE

        for i in range(n):
            arr[i] += PowOfBase[self.MAX_T - 1]

        pos = 0 
        while pos < self.MAX_T:
            RedixBucket = [ [] for i in range(self.BASE)]

            for i in range(n):
                rdx = arr[i] // PowOfBase[pos] % self.BASE
                RedixBucket[rdx].append( arr[i] )
            
            top = 0
            for i in range(self.BASE):
                for rb in RedixBucket[i]:
                    arr[top] = rb
                    top += 1
            
            pos += 1

        for i in range(n):
            arr[i] -= PowOfBase[self.MAX_T - 1]
        return arr

堆排序

辅助函数（节点关系）：

leftSon(idx)：返回节点idx的左子节点索引（2*idx + 1）。

rightSon(idx)：返回节点idx的右子节点索引（2*idx + 2）。

parent(idx)：返回节点idx的父节点索引（(idx-1)//2）。

better(a, b)：比较函数，默认返回a > b，用于定义最大堆的比较规则。

Heapify 函数：

Ⅰ、计算子节点索引

leftSon(curr) 和 rightSon(curr) 分别计算当前节点的左右子节点索引。

optId 初始化为当前节点索引，用于记录最大值的位置。

Ⅱ、找出最大值索引

比较当前节点与左右子节点的值：如果左子节点存在且值更大，则更新 optId 为左子节点索引。同理，对右子节点进行相同比较。better 函数默认实现为 a > b，确保构建最大堆。

Ⅲ、交换并递归调整

如果最大值不在当前节点（curr != optId），则交换当前节点与最大值节点。

递归调用 Heapify 处理被交换的子节点，确保其所有子树仍满足堆性质。

sortArray 函数：

构建最大堆：从最后一个非叶子节点（n//2 -1）开始，向上逐个调用Heapify，确保整个数组成为最大堆。

循环过程：将堆顶元素（最大值）与当前未排序部分的最后一个元素交换；减少堆的大小（size = i），将最大值排除在后续调整范围外；调用 Heapify(0) 重新调整剩余元素为最大堆。

效果：每次循环将当前最大值移至数组末尾，最终形成升序排列。

def leftSon(idx):
    return 2 * idx + 1

def rightSon(idx):
    return 2 * idx + 2

def parent(idx):
    return (idx - 1) // 2

def better(a, b):
    return a > b 

class Solution:
    def Heapify(self, heap, size, curr):
        leftSonId = leftSon(curr)
        rightSonId = rightSon(curr)
        optId = curr
        if leftSonId < size and better(heap[leftSonId], heap[optId]):
            optId = leftSonId
        if rightSonId < size and better(heap[rightSonId], heap[optId]):
            optId = rightSonId

        if curr != optId:
            heap[curr], heap[optId] = heap[optId], heap[curr]
            self.Heapify(heap, size, optId)

    def sortArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        for i in range(n // 2, -1, -1):
            self.Heapify(nums, n, i)

        for i in range(n-1, -1, -1):
            nums[0], nums[i] = nums[i], nums[0]
            self.Heapify(nums, i, 0)

        return nums

一、算法描述

希尔排序是插入排序的一种改进版本，也称为缩小增量排序。它通过将原始数据分成多个子序列来改善插入排序的性能，每个子序列使用插入排序进行排序，最终完成整个数组的排序。

二、核心思路

希尔排序（Shell Sort）就像给数组 “层层松绑” 的过程，有点像我们平时整理乱序的扑克牌，但不是一张一张插入，而是先分批次 “粗略调整”，最后再精细整理。

分阶段分组：先以较大的间隔（比如每隔 2 人一组），将队列分成若干小组，每组内单独排序。

缩小间隔：逐渐减小分组间隔（比如从间隔 2→1），重复分组排序，直到间隔为 1 时，整个队列基本有序，最后用插入排序收尾。

三、代码分析

① 初始化间隔（增量）

首先计算初始间隔 gap，通常取数组长度的一半（gap = n // 2）。这个间隔决定了子序列的划分方式，后续会逐步缩小。

② 分组与插入排序

外层循环（间隔控制）：当 gap > 0 时，执行循环体。每次循环结束后将间隔缩小一半（gap = gap // 2）。

中层循环（遍历每个子序列）：从 gap 开始遍历到数组末尾，每个元素 arr[i] 属于不同的子序列。

内层循环（子序列插入排序）：保存当前元素 arr[i] 到临时变量 temp。在当前子序列中（间隔为 gap），从后往前比较元素。如果前一个元素 arr[j - gap] 大于 temp，则将其向后移动 gap 个位置。重复上述比较和移动操作，直到找到正确的插入位置，然后将 temp 插入该位置。

③ 缩小间隔

每次完成当前间隔的所有子序列排序后，将间隔缩小一半（例如，从 gap = 4 到 gap = 2，再到 gap = 1）。当间隔最终缩小到 1 时，整个数组被视为一个子序列，此时执行的就是标准的插入排序，但由于前面的分组排序已经使数组接近有序，插入排序的效率会更高。

④ 终止条件

当间隔 gap 减小到 0 时，排序完成，返回排序后的数组。

    def shell_sort(self, arr):
        n = len(arr)
        gap = n // 2  # 初始间隔
        
        while gap > 0:
            # 对每个间隔分组进行插入排序
            for i in range(gap, n):
                # 保存当前元素，作为待插入的值
                temp = arr[i]
                j = i
                # 在间隔为gap的分组内，从后往前找到插入位置
                while j >= gap and arr[j - gap] > temp:
                    arr[j] = arr[j - gap]  # 元素后移
                    j -= gap
                arr[j] = temp  # 插入正确位置
            gap = gap // 2  # 缩小间隔
        return arr

四、实战练习

912. 排序数组

给你一个整数数组 nums，请你将该数组升序排列。

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：

1 <= nums.length <= 5 * 104

-5 * 104 <= nums[i] <= 5 * 104

算法与思路

① 希尔排序

Ⅰ、初始化间隔（增量）

首先计算初始间隔 gap，通常取数组长度的一半（gap = n // 2）。这个间隔决定了子序列的划分方式，后续会逐步缩小。

Ⅱ、分组与插入排序

外层循环（间隔控制）：当 gap > 0 时，执行循环体。每次循环结束后将间隔缩小一半（gap = gap // 2）。

中层循环（遍历每个子序列）：从 gap 开始遍历到数组末尾，每个元素 arr[i] 属于不同的子序列。

Ⅲ、缩小间隔

Ⅳ、终止条件

当间隔 gap 减小到 0 时，排序完成，返回排序后的数组。

② 排序数组

调用希尔排序函数，传入列表（数组）nums

class Solution:
    def shell_sort(self, arr):
        n = len(arr)
        gap = n // 2  # 初始间隔
        
        while gap > 0:
            # 对每个间隔分组进行插入排序
            for i in range(gap, n):
                # 保存当前元素，作为待插入的值
                temp = arr[i]
                j = i
                # 在间隔为gap的分组内，从后往前找到插入位置
                while j >= gap and arr[j - gap] > temp:
                    arr[j] = arr[j - gap]  # 元素后移
                    j -= gap
                arr[j] = temp  # 插入正确位置
            gap = gap // 2  # 缩小间隔
        return arr

    def sortArray(self, nums: List[int]) -> List[int]:
        return self.shell_sort(nums)

天启AI社区

GitCode 天启AI是一款由 GitCode 团队打造的智能助手，基于先进的LLM（大语言模型）与多智能体 Agent 技术构建，致力于为用户提供高效、智能、多模态的创作与开发支持。它不仅支持自然语言对话，还具备处理文件、生成 PPT、撰写分析报告、开发 Web 应用等多项能力，真正做到“一句话，让 Al帮你完成复杂任务”。

更多推荐