数据结构与算法之排序

9.1 排序的概念

1. 排序的定义

定义：排序是将表中的记录按关键字递增（或递减）有序排列的过程。
说明：数据中可以存在相同关键字的记录。本章主要考虑递增排序。
扩展：排序是数据处理中的基本操作之一，广泛应用于数据库管理、信息检索等领域。排序可以提高数据的可读性和可操作性，便于后续的查找、统计等操作。

2. 内排序和外排序

内排序：整个表都在内存中处理，不涉及数据的内外存交换。
外排序：排序过程中需要进行数据的内外存交换。
扩展：内排序适用于数据量较小的情况，因为内存访问速度快，效率较高。外排序适用于数据量较大的情况，通常需要将数据分块处理，然后合并排序结果。

3. 内排序的分类

插入排序：通过将元素插入到已排序部分的适当位置来实现排序。
交换排序：通过交换元素的位置来实现排序，如冒泡排序。
选择排序：通过选择未排序部分的最小（或最大）元素与当前元素交换来实现排序。
归并排序：将数据分成多个小部分进行排序，然后将排序好的部分合并。
基于比较的排序算法：如插入排序、交换排序、选择排序、归并排序等。
不基于比较的排序算法：如基数排序。
扩展：不同的排序算法适用于不同的场景，选择合适的排序算法可以提高程序的效率。例如，插入排序适用于部分有序的数据，而归并排序适用于大规模数据的排序.

4.小结

排序的概念定义递增或递减排列
- - 允许相同关键字
- 内排序 vs 外排序内排序：内存中处理
  - 外排序：内外存交换
- 内排序分类插入排序
  - 交换排序
  - 选择排序
  - 归并排序
  - 基数排序

9.2插入排序

9.2.1 直接插入排序

基本思路

有序区和无序区：初始时，有序区只有一个元素（通常是第一个元素），无序区包含其余所有元素。
排序过程：每次从未排序区取出一个元素，插入到有序区的适当位置，使得有序区仍然保持有序。
步骤：将待插入元素与有序区的元素从后向前比较。
- 如果待插入元素小于当前比较的元素，则将当前元素后移一位。
- 重复上述步骤，直到找到待插入元素的正确位置。
- 将待插入元素插入到该位置。

Python实现

def insert_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # 将arr[i]插入到已排序序列arr[0...i-1]中
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 示例
arr = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
print("原始数组:", arr)
insert_sort(arr)
print("排序后的数组:", arr)

算法分析

时间复杂度：最好情况：输入序列已经是正序的，时间复杂度为 O(n)。
- 最坏情况：输入序列是反序的，时间复杂度为 O(n2)。
- 平均情况：时间复杂度为 O(n2)。
空间复杂度：O(1)，因为只需要一个额外的变量来存储待插入的元素。
稳定性：稳定排序算法，因为相同元素的相对顺序不会改变。

eg：设待排序的表有10个元素，其关键字分别为（9，8，7，6，5，4，3，2，1，0）

9.2.2 折半插入排序

基本思路

折半查找：在有序区中使用折半查找方法来确定待插入元素的位置，从而减少比较次数。
步骤：将待插入元素保存在一个临时变量中。
- 使用折半查找在有序区中找到待插入元素的正确位置。
- 将有序区中从插入位置开始的所有元素后移一位，为待插入元素腾出空间。
- 将待插入元素插入到找到的位置。

Python实现

def binary_search(arr, key, low, high):
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < key:
            low = mid + 1
        else:
            high = mid - 1
    return low

def binary_insert_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        # 使用折半查找找到插入位置
        pos = binary_search(arr, key, 0, i - 1)
        # 将元素后移
        for j in range(i, pos, -1):
            arr[j] = arr[j - 1]
        # 插入元素
        arr[pos] = key
    return arr

# 示例
arr = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
print("原始数组:", arr)
binary_insert_sort(arr)
print("排序后的数组:", arr)

算法分析

时间复杂度：比较次数：由于使用了折半查找，比较次数为 O(log⁡n)。
- 移动次数：移动次数仍为 O(n)，因为需要将元素后移。
- 总时间复杂度：O(n2)，虽然比较次数减少，但移动次数仍然较高。
空间复杂度：O(1)，只需要一个额外的变量来存储待插入的元素。
稳定性：稳定排序算法，因为相同元素的相对顺序不会改变.

9.2.3 希尔排序

基本思路

分组插入：希尔排序是一种基于插入排序的改进算法，通过将待排序序列分成若干个子序列，对每个子序列进行直接插入排序。
增量序列：选择一个增量序列 d1,d2,…,dkd1 ,d2 ,…,dk ，其中 d1>d2>…>dk=1d1 >d2 >…>dk =1。增量 dd 通常从 n/2n/2 开始，每次减半，直到增量为1。
步骤：选择一个增量 dd，将待排序序列分成 dd 个子序列。
- 对每个子序列进行直接插入排序。
- 减小增量 dd，重复上述步骤，直到增量为1。

Python实现

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始增量
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # 对每个子序列进行插入排序
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2  # 减小增量
    return arr

# 示例
arr = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
print("原始数组:", arr)
shell_sort(arr)
print("排序后的数组:", arr)

算法分析

时间复杂度：最好情况：O(nlog⁡n)O(nlogn)，当增量序列选择得当且数据接近有序时。
- 最坏情况：O(n2)O(n2)，但通常比直接插入排序要好。
- 平均情况：通常为 O(n1.3)O(n1.3) 或 O(n1.5)O(n1.5)，具体取决于增量序列的选择。
空间复杂度：O(1)O(1)，因为只需要一个额外的变量来存储待插入的元素。
稳定性：不稳定排序算法，因为相同元素的相对顺序可能会改变.

希尔排序过程解释

初始序列：9, 8, 7, 6, 5, 4, 3, 2, 1, 0
第一次排序（d=5）：
1. 增量 d 被设置为数组长度的一半，即 5。
2. 将数组分为 5 组，每组包含相隔 5 个位置的元素：{9, 4}, {8, 3}, {7, 2}, {6, 1}, {5, 0}。
3. 对每组进行直接插入排序。例如，第一组 9, 4 排序后变为 4, 9。
4. 数组变为：4，9，3，8，2，7，1，6，0，5
第二次排序（d=2）：
1. 增量 d 减半，变为 2。
2. 将数组分为 2 组，每组包含相隔 2 个位置的元素：{4, 3, 2, 1}, {9, 8, 7, 6}, {5, 0}。
3. 对每组进行直接插入排序。例如，第一组 4, 3, 2, 1 排序后变为 1, 2, 3, 4。
4. 数组变为：1，2，3，4，6，7，8，9，0，5
第三次排序（d=1）：
1. 增量 d 再次减半，变为 1。因为整一个数组基本有序，最后进行一次直接插入排序时间复杂度就约等于O(n)，在这里除了0和5其它元素都是直接放入有序区。
2. 此时，整个数组作为一个组进行直接插入排序。
3. 由于前两次排序已经将数组中的元素大致排列好了，这次排序将它们排列成完全有序的序列：0, 1, 2, 3, 4, 5, 6, 7, 8, 9。