排序

• 1: 内部排序
• 2: 外部排序

# 排序

## 排序的基本概念

## 内部排序

- 直接插入排序
- 折半插入排序
- 冒泡排序
- 简单选择排序
- 希尔排序
- 快速排序
- 堆排序
- 二路归并排序
- 基数排序

## 外部排序

## 排序算法的分析

1 - 内部排序

排序总结

• 冒泡排序
• 插入排序
• 选择排序
• 基数排序
• 归并排序
• 希尔排序
• 快速排序
• 堆排序

BubbleSort(arr)
    n = arr.length
    for i from 0 to n-1
        for j from 0 to n-i-1
            if arr[j] > arr[j+1]
                swap(arr[j], arr[j+1])

InsertionSort(arr)
    n = arr.length
    for i from 1 to n-1
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key
            arr[j+1] = arr[j]
            j = j - 1
        arr[j+1] = key

SelectionSort(arr)
    n = arr.length
    for i from 0 to n-1
        minIndex = i
        for j from i+1 to n
            if arr[j] < arr[minIndex]
                minIndex = j
        swap(arr[i], arr[minIndex])

RadixSort(arr)
    Find the maximum number in arr, determine the number of digits in it, denoted as d
    for i from 1 to d
        Using a stable sort (e.g., counting sort) to sort arr based on the i-th digit

MergeSort(arr)
    if arr.length <= 1
        return arr
    mid = arr.length / 2
    left = arr[0 to mid-1]
    right = arr[mid to end]
    left = MergeSort(left)
    right = MergeSort(right)
    result = Merge(left, right)
    return result

Merge(left, right)
    result = []
    while left is not empty and right is not empty
        if left[0] <= right[0]
            append left[0] to result
            remove left[0] from left
        else
            append right[0] to result
            remove right[0] from right
    append remaining elements of left and right to result
    return result

ShellSort(arr)
    n = arr.length
    gap = n / 2
    while gap > 0
        for i from gap to n-1
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp
                arr[j] = arr[j - gap]
                j = j - gap
            arr[j] = temp
        gap = gap / 2

QuickSort(arr, low, high)
    if low < high
        pivotIndex = Partition(arr, low, high)
        QuickSort(arr, low, pivotIndex - 1)
        QuickSort(arr, pivotIndex + 1, high)

Partition(arr, low, high)
    pivot = arr[high]
    i = low - 1
    for j from low to high-1
        if arr[j] <= pivot
            i = i + 1
            swap arr[i] and arr[j]
    swap arr[i + 1] and arr[high]
    return i + 1

HeapSort(arr)
    BuildMaxHeap(arr) // 构建最大堆
    for i from n-1 down to 1
        swap arr[0] and arr[i] // 将最大值移到末尾
        MaxHeapify(arr, 0, i) // 修复剩余的堆

BuildMaxHeap(arr)
    n = arr.length
    for i from n/2 - 1 down to 0
        MaxHeapify(arr, i, n)

MaxHeapify(arr, i, n)
    largest = i
    left = 2*i + 1
    right = 2*i + 2

    if left < n and arr[left] > arr[largest]
        largest = left

    if right < n and arr[right] > arr[largest]
        largest = right

    if largest != i
        swap arr[i] and arr[largest]
        MaxHeapify(arr, largest, n)

冒泡排序

冒泡排序（Bubble Sort）的名称来源于它的操作方式：重复地遍历要排序的序列，比较每对相邻的项，若它们的顺序错误就交换过来，就像“小泡泡”从底部冒向顶部一样。

比如，对于数组 5, 1, 4, 2, 8的前两次冒泡过程如下：

• 第一次（效果相当于将最大的数放到最后一个位置）：

( 5 1 4 2 8 ) → ( 1 5 4 2 8 )

( 1 5 4 2 8 ) → ( 1 4 5 2 8 )

( 1 4 5 2 8 ) → ( 1 4 2 5 8 )

( 1 4 2 5 8 ) → ( 1 4 2 5 8 )

• 第二次（效果相当于将第二大的数放在倒数第二个位置）：

( 1 4 2 5 8 ) → ( 1 4 2 5 8 )

( 1 4 2 5 8 ) → ( 1 2 4 5 8 )

( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

插入排序

插入排序（Insertion Sort）将数组分为未排序部分和已排序部分，每次选取未排序部分的第一个元素作为插入元素，在已排序序列中从后向前扫描，找到相应位置并插入。

对于数组3, 7, 4, 9, 5, 2, 6, 1执行插入排序的过程：

3  7  4  9  5  2  6  1
3* 7  4  9  5  2  6  1
3  7* 4  9  5  2  6  1
3  4* 7  9  5  2  6  1
3  4  7  9* 5  2  6  1
3  4  5* 7  9  2  6  1
2* 3  4  5  7  9  6  1
2  3  4  5  6* 7  9  1
1* 2  3  4  5  6  7  9

插入排序可以分为直接插入排序和折半插入排序，其不同点在于 寻找插入位置时 使用的是顺序查找还是折半查找。

选择排序

选择排序（Selection Sort）的思想是 从未排序的部分中找到最小（或最大）的元素，然后与未排序部分的第一个元素交换位置。这样，每一次选择操作后，未排序部分减少一个元素，而有序部分则增加一个元素。

以排序数组11, 25, 12, 22, 64为例：

归并排序

归并排序（Merge Sort）是一个典型的“分而治之”策略的应用。它将一个大问题分解成若干小问题分别解决，然后将这些小问题的解合并为大问题的解。归并排序的主要思想是将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

基本思想：

1. 分解：分解待排序的数据数组为两个长度相等（或几乎相等）的子数组。
2. 递归：递归地排序两个子数组。
3. 合并：合并（归并）两个已排序的子数组以产生排序好的数据数组。

快速排序

快速排序（Quick Sort）的核心思想是分而治之 (Divide and Conquer)：

1. 选择一个“基准”元素：从数组中选择一个元素作为基准。
2. 分区 (Partitioning)：重新排列数组，使得所有小于基准的元素都在其左侧，所有大于基准的元素都在其右侧。在这个分区结束之后，该基准就处于数组的最终排序位置。
3. 递归地排序子序列：递归地对基准左侧和右侧的子数组进行快速排序。

// 寻找数组中第k大的数字
QuickSelect(arr, low, high, k)
    if low <= high
        pivotIndex = Partition(arr, low, high)
        
        // 如果pivotIndex与k相等，那么arr[pivotIndex]就是我们要找的第k大的数
        if pivotIndex == k
            return arr[pivotIndex]
        
        // 如果pivotIndex小于k，说明第k大的数在右子数组
        if pivotIndex < k
            return QuickSelect(arr, pivotIndex + 1, high, k)
        
        // 否则，第k大的数在左子数组
        return QuickSelect(arr, low, pivotIndex - 1, k)

// 分区操作，返回分区下标
Partition(arr, low, high)
    pivot = arr[high]
    i = low - 1
    for j from low to high-1
        if arr[j] <= pivot
            i = i + 1
            swap arr[i] and arr[j]
    swap arr[i + 1] and arr[high]
    return i + 1

堆排序

堆的概念

堆的概念

满足以下性质的树 被成为 堆（Heap）：

1. 结构性质：堆总是一颗 完全二叉树，即除了最后一层之外的其他每一层都被元素填满，且最后一层的元素都尽可能地靠左排列。
2. 有序性质：树中的每个结点 相对于 孩子结点都保证有序关系，要么父结点的值都 大于等于 子结点，要么都 小于等于 子结点，按照这种有序关系堆可以分为两种类型：
   • 大根堆 (Max-Heap)：堆中的任意节点，其值都不小于其子节点的值。这意味着根节点是最大值。
   • 小根堆 (Min-Heap)：堆中的任意节点，其值都不大于其子节点的值。这意味着根节点是最小值。

基于这些性质，堆常常被用于实现优先队列。对于大根堆，我们总是可以在 O(1) 的时间内得到最大的元素（即根节点），而对于小根堆，我们总是可以在 O(1) 的时间内得到最小的元素。

堆的操作

• 插入 (Insertion)：将一个新的元素添加到堆中，并保持堆的性质。这个操作的时间复杂度为 O(logn)。
• 删除 (Deletion)：删除堆中的最大（或最小）元素，并保持堆的性质。这个操作的时间复杂度也为 O(logn)。

堆的实现

堆通常使用数组来实现，而不需要使用真正的树或链表结构。利用数组实现堆时，每个元素都有一个固定的位置，而该位置与元素在树中的位置有关。

假设数组的起始索引为1，若某元素的索引为 i，则它的：

• 左孩子的索引为 2i
• 右孩子的索引为 2i + 1
• 父节点的索引为 i/2 （整数除法）

如果数组的起始索引为0，若某元素的索引为 i，则它的：

• 左孩子的索引为 2i + 1
• 右孩子的索引为 2i + 2
• 父节点的索引为 (i-1)/2（整数除法）

推排序流程

堆排序（Heap Sort）其主要思想是将待排序的序列构造成一个大顶堆或小顶堆，然后交换堆顶和最后一个元素的位置，使最大或最小的元素放到序列的末尾。这样，就得到一个部分有序的序列。接下来，再对剩下的部分重新调整为大顶堆或小顶堆，并重复上述过程，直到整个序列有序。

堆排序的主要步骤：

1. 构造初始堆：将给定无序序列构造成一个大顶堆（对于升序排序）或小顶堆（对于降序排序）。
2. 交换数据：将堆顶元素与末尾元素交换，这样最大元素就位于序列的末尾。然后，将未排序的序列的长度减1，因为最后一个元素已经排序好了。
3. 重建堆：对于剩下的未排序的序列，重新调整为大顶堆。
4. 重复步骤2和3，直到整个序列有序。

调整堆过程：

1. 选择一个节点 i，它的左子节点为 2i，右子节点为 2i+1。
2. 如果节点 i 的值小于其子节点的值，则找到最大的子节点。
3. 将节点 i 与最大的子节点交换。
4. 交换后可能会破坏下一层的堆结构，所以需要对换到的子节点重复步骤1-3的调整，直到整个子树满足堆的性质。

希尔排序

希尔排序（Shell Sort）是一种基于插入排序的算法，通过比较较远距离的元素来工作，然后逐渐减少这种距离。它的核心思想是使数组中的任何给定部分变得有序，这样在最后的排序阶段，整个数组都将近似排序，使插入排序可以更快地完成工作。

基本思想：

1. 选择一个增量序列：通常开始于数组长度的一半，并逐渐减至1。这个增量称为“间隔”或“步长”。
2. 按增量进行插入排序：对于每个增量值，用此增量将数据分成几个子序列，然后对每个子序列进行插入排序。
3. 减少增量并重复：增量减少（通常减半），然后重复上述过程，直到增量为1，此时执行一次标准的插入排序。

基数排序

基数排序（Radix Sort）其核心思想是将整数分解为单独的数字，然后根据每个位的数字对整数进行排序。基数排序的速度很快，但它有特定的应用场景：当你知道要排序的整数的范围时，它特别有用。

过程：

1. 分解数字：从最低位（如个位）开始，逐个考虑整数的每一位。
2. 使用稳定排序算法：对每一位使用稳定的排序算法（如计数排序或桶排序）将数字排序。稳定性在这里很重要，因为我们要保证在前一个位置上的排序顺序不会因后一个位置上的排序而被打乱。
3. 逐位排序：处理完一位后，再处理下一位，直到处理完所有的位。

2 - 外部排序

外部排序

当待排序的数据量非常大，以至于无法一次性全部加载到内存中时，就需要使用外部排序。

外部排序通常分为两个主要阶段：

• 初始归并段生成： 使用置换选择排序，根据原始无序文件生成若干个尽量长的的有序文件，这些有序文件叫做初始归并段。
• 多路归并： 将这些初始归并段逐步合并，最终得到完全有序的文件。

置换选择排序

置换选择排序（Replacement Selection Sort）是外部排序的一个步骤，用于生成初始归并段， 其核心思想是在内存缓冲区有限的情况下，尽可能地生成较长的初始归并段。

置换选择排序通过维护一个工作区来实现这一目标，工作区是一个小根堆。

其算法步骤如下：

1. 初始化：
   • 将待排序文件中的前 M 个记录读入工作区，建立一个最小堆（M 为工作区的大小）。
2. 生成归并段：
   • 判断是否有初始归并段
     • 如果不存在任何初始归并段的话，创建一个初始归并段，并添加工作区中的最小元素加入其中。
     • 否则将工作区中的元素与上一个初始归并段的最大值 MAXV 进行比较。
       • 如果工作区中的所有元素都 ≤ MAXV 的话，创建一个新的初始归并段，并添加工作区中的最小元素加入其中。
       • 否则找到第一个 > MAV 的元素，将其添加到上一个初始归并段的末尾。
   • 从输入文件中读取下一个值加入工作区。

举一个实际的例子，假设一个输入文件 FI 的内容为 51, 94, 37, 92, 14, 63, 15, 99, 48, 56, 23, 60, 31, 17, 43, 8, 90, 166, 100。

我们可以通过置换选择排序生成 3 个初始归并段，分别为 {37, 51, 63, 92, 94, 99} ，{14, 15, 23, 31, 48, 56, 60, 90, 166} ，{8, 17, 43, 100} 。

算法执行的过程如下表所示：

多路归并

多路归并的目标是将多个已经排序的初始归并段（子文件）合并成一个更大的有序文件。

其核心思想是从若干归并段中每次选取一个最小的元素加入工作区（小根堆），然后从工作区中选取最小的元素添加到输出文件中，通过这种方式可以保证每次添加到输出文件中的值是当前的最小值。

多路归并的具体过程如下：

1. 初始化：
   • 打开所有参与归并的初始归并段，并读取每个归并段的第一个元素。
   • 将这些元素放入一个数据结构中，以便快速找到最小值（例如，最小堆）。
2. 归并：
   • 从数据结构中取出最小的元素，将其输出到结果文件中。
   • 找到该元素所属的归并段，并从该归并段中读取下一个元素。
   • 将新读取的元素放入数据结构中，并调整数据结构，以保持有序。
   • 重复上述步骤，直到所有归并段都被处理完毕。
3. 结束：
   • 当所有归并段都为空时，归并过程结束，结果文件即为完全有序的文件。

继续用上文中通过置换选择算法生成的三个初始归并段 {37, 51, 63, 92, 94, 99} ，{14, 15, 23, 31, 48, 56, 60, 90, 166} ，{8, 17, 43, 100} 作为例子。 对于这三个初始归并段，多路归并的过程如下（假设采用三路归并的话）：