排序

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

# 排序

## 排序的基本概念

## 内部排序

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

## 外部排序

## 排序算法的分析

1 - 内部排序

排序概念

稳定性

排序算法的 稳定性 是指：在排序过程中，如果两个元素的键值相等，排序后它们的 相对顺序保持不变，那么这个排序算法就是稳定的排序算法。

比如排序前的数组是这样：[... A ... B ...]，并且 A 和 B 的值相同。

如果排序后的数组是这样：[... B A ...]，那么排序算法就是不稳定的，反之排序算法就是稳定的。

元素移动次数

排序算法中的 元素移动次数，指的是在排序过程中对 数组元素进行位置变换的次数。

下表列出了各排序算法的元素移动次数：

可以观察到，选择排序 和 桶排序 的元素移动次数是最少的，不涉及到大量的元素位置交换。

复杂度

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

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）将数组分为未排序部分和已排序部分，每次选取未排序部分的第一个元素作为插入元素，在已排序序列中从后向前扫描，找到相应位置并插入。

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

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

选择排序

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

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

归并排序

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

基本思想：

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

快速排序

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

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

代码实现

快排代码包含两个函数，一个是 partition，用于选择基准元素，并对其进行分区。

其中分区的实现方式有很多种，此处使用双指针法实现分区，该算法比较简短，方便记忆。

// [low, high] 为分区的范围，返回值为分区后 pivot 在数组中的下表
int partition(int a[], int low, int high) {
    int pivot = a[low];     // 设置基准元素为 [low, high] 区间中的第一个元素
    int l = low, r = high;  // 设置双指针
    while (l < r) {
        while (l < r && a[r] >= pivot) r--; // 从右到左寻找小于 pivot 的元素
        while (l < r && a[l] <= pivot) l++; // 从左到右寻找大于 pivot 的元素
        if (l < r) swap(a[l], a[r]);        // 交换两个元素
    }
    swap(a[low], a[r]); // 将 pivot 置换到中间位置
    return r;
}

void quickSort(int a[], int low, int high) {
    // 递归的结束条件，不要遗漏
    if (low < high) {
        int pivotIdx = partition(a, low, high);
        // 递归地对两个
        quickSort(a, low, pivotIdx - 1);
        quickSort(a, pivotIdx + 1, high);
    }
}

快速排序的代码实现需要熟练掌握（能够手写代码），在数据结构的算法解答题中可以作为兜底的方案。

单向递归算法

每一次基于基准元素执行分区操作后，可以基于基准元素的位置将数组分为两个部分，这个时候基准元素的位置与最后有序数组中的位置相同。

基于这一点常常会做一些考察，比如如果我们需要寻找数组中第k大的数（即找到有序数组中下标为k的数），这个时候我们就不需要向两个方向递归，只需要向一个方向递归即可，如果当前基准被确定在第k个位置，即可退出递归。

// 分区算法实现与标准快排相同，这里不赘述
int partition(int a[], int low, int high) { ... }

// 寻找数组中第 k 大的数字，返回值为该元素
int quickSelect(int a[], int low, int high, int k) {
    if (low < high) {
        pivotIdx = partition(a, low, high);
        // 如果 pivotIndex 与 k 相等，那么 a[pivotIdx] 就是我们要找的第k大的数
        if (pivotIdx == k) {
            return a[pivotIdx];
        }
        // 如果 pivotIdx 小于 k，说明第 k 大的数在右边分区
        if (pivotIdx < k) {
            return quickSelect(a, pivotIdx+1, high, k);
        }
        // 否则在左边分区
        return quickSelect(a, low, pivotIdx-1, k);
    }
}

堆排序

堆排序的核心在于利用堆的性质进行排序，在了解堆排序过程之前，需要了解堆的基本概念。

堆

在二叉树一节中我们提到，二叉树的存储方式 包含 链接存储 和 顺序存储 两种。 堆就是采用顺序存储的方式，在这种方式中，我们使用一个数组来模拟一颗二叉树，二叉树中的结点操作被转化为数组元素操作。

概念

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

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

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

实现

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

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

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

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

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

操作

对于堆，重点掌握以下三种操作的过程：

• 构造初始堆：将一个数组初始化为堆，其步骤为从最后一个非叶结点开始，向下堆化每个节点。这种方法也叫做 “下沉法”，因为这种方法会将最小值不断下沉到二叉树的底部。
• 插入：将一个新的元素添加到堆中，并保持堆的性质。
• 删除：删除堆中的最大（或最小）元素，并保持堆的性质。

这三种操作的时间复杂度都为 $O(n)$。

其中堆化（heapify）是实现以上操作的核心，heapify 可以保证某个子树符合堆的性质。

• 构造初始堆
• 堆插入元素
• 堆删除元素

// 调整 i 结点为根的子树，使其满足堆的性质
void heapify(int heap[], int size, int i) {
    int largest = i;       // 假设当前节点是最大的
    int left = 2 * i + 1;  // 左结点下标
    int right = 2 * i + 2; // 右结点下标
    if (left < size && heap[left] > heap[largest]) {
        largest = left;
    }
    if (right < size && heap[right] > heap[largest]) {
        largest = right;
    }
    // 如果最大值不是根结点
    if (largest != i) {
        swap(heap[i], heap[largest]);
        heapify(heap, size, largest);  // 递归堆化受影响的子树
    }
}

// 建立最大堆
void buildHeap(int heap[], int size) {
    // 从最后一个非叶节点开始，向前堆化每个节点
    for (int i = (size / 2) - 1; i >= 0; i--) {
        heapify(heap, size, i);
    }
}

// 向大小为 size 的堆中插入元素 value
void heapInsert(int heap[], int *size, int value) {
    heap[*size] = value;
    int current = *size;
    int parent = (current - 1) / 2;
    
    // 如果新插入的元素比父结点的元素大，需要将其向上移动
    while (current > 0 && heap[current] > heap[parent]) {
        swap(heap[current], heap[current]); // 交换当前节点和父节点
        current = parent;
        parent = (current - 1) / 2; // 重新计算当前结点和其父结点的位置
    }
  
    (*size)++;  // 增加堆的大小
}

// 删除堆根结点
void heapDelete(int heap[], int *size) {
    if (*size <= 0) {
        return;
    }
    heap[0] = heap[*size - 1]; // 将堆顶元素替换为最后一个元素
    (*size)--;   // 将堆大小减1
    heapify(heap, *size, 0);   // 调整堆
}

过程

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

堆排序的主要步骤：

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

调整堆过程：

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

堆排序的代码实现如下所示：

void heapSort(int heap[], int size) {
    // 构建最大堆 buildHeap
    for (int i = (size / 2) - 1; i >= 0; i--) {
        heapify(heap, size, i);
    }
    
    // 一个个从堆中取出元素
    for (int i = size - 1; i >= 0; i--) {
        swap(heap[0], heap[i]); // 将当前最大元素（堆顶）移到数组末尾
        heapify(heap, i, 0);    // 调整堆以维护最大堆性质
    }
}

希尔排序

希尔排序（Shell Sort）是一种 基于插入排序 的改进算法，通过分组和逐步减小步长来提高效率。

希尔排序的过程如下所示：

1. 确定初始步长（增量）：
   • 选择一个初始步长（gap），通常可以 取数组长度的一半（例如 gap = n/2）。
2. 分组插入排序：
   • 将数组按步长 gap 分成若干组，每组内的元素相距 gap 个位置。
   • 对每组进行插入排序。例如，若 gap=4，比较和排序索引为 0,4,8… 的元素，1,5,9… 的元素，依此类推。
3. 减小步长：
   • 将步长缩小（通常除以 2 或按增量序列递减），例如 gap = gap/2。
   • 重复步骤 2，对新的分组进行插入排序。
4. 重复直到步长为 1：
   • 当步长减小到 1 时，相当于对整个数组进行一次标准插入排序。
   • 此时数组已接近有序，插入排序的效率较高。
5. 排序完成：
   • 步长为 1 的插入排序完成后，数组完全有序。

以数组 32, 95, 16, 82, 24, 66, 35, 19, 75, 54, 40, 43, 93, 68 为例进行选择希尔排序，数组长度为 14， 初始步长为 7，然后选择步长 3、1，依次按照步长对所有子数组排序。

桶排序

桶排序（bucket sort）核心思想是将数据映射到不同的桶中，然后对每个桶内部排序，最后合并所有桶中的数据。

桶排序的步骤如下：

1. 选择合适桶数，并将数据放入桶中
2. 桶内数据排序
3. 合并所有桶

比如对 0.78, 0.17, 0.39, 0.26, 0.72 进行排序：

1. 划分桶：
   • 0.0 - 0.2: [0.17]
   • 0.2 - 0.4: [0.26, 0.39]
   • 0.4 - 0.6: []
   • 0.6 - 0.8: [0.72, 0.78]
   • 0.8 - 1.0: []
2. 对每个桶排序：
   • [0.17]
   • [0.26, 0.39] → [0.26, 0.39]
   • [0.72, 0.78] → [0.72, 0.78]
3. 合并所有桶：[0.17, 0.26, 0.39, 0.72, 0.78]

基数排序

基数排序（Radix Sort）的核心思想是 将整数分解为单独的数字，然后进行多轮排序，最终使数据有序。

基数排序分为低位优先（LSD，Least Significant Digit first）和高位优先（MSD，Most Significant Digit first）两种方案。 这里重点掌握 LSD 的方案，MSD 的方式了解即可。

低位优先

1. 先按照最低位进行桶排序（或计数排序）。
2. 然后按照次低位进行桶排序，但保持上一轮的相对顺序（稳定排序）。
3. 依次进行，直到最高位排序完成。

以上排序的效果如下：