排序

• 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 - 外部排序

外部排序是一种处理大量数据的排序方法，尤其是当数据太大而不能完全装入内存时。这种排序方法通常使用分治策略，将大问题分解为小问题，对小问题进行解决，然后再将解决方案组合成大问题的解决方案。

以下是外部排序的基本步骤，其中最典型的方法是多路归并排序：

1. 分阶段 (Split Phase)：
   • 数据被分割成多个小文件。每个小文件的大小基本上与可用内存相匹配。
   • 读取一个小文件大小的数据到内存中，使用传统的排序算法（如快速排序、堆排序等）对数据进行排序。
   • 将排序后的数据写回到磁盘。
2. 归并阶段 (Merge Phase)：
   • 采用多路归并算法，从每个小文件中读取一部分数据到内存。
   • 将这些数据进行合并，并将结果写回到一个新的输出文件中。
   • 当所有小文件都被完全读取并归并后，输出文件就是完全排序好的数据。