内部排序

排序总结

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

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. 选择一个 “基准” 元素（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. 选择一个增量序列：通常开始于数组长度的一半，并逐渐减至1。这个增量称为“间隔”或“步长”。
2. 按增量进行插入排序：对于每个增量值，用此增量将数据分成几个子序列，然后对每个子序列进行插入排序。
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. 依次进行，直到最高位排序完成。

以上排序的效果如下：

首先对最低位排序，然后对次低位排序，最后对最高位排序。通过三轮排序，可以保证结果序列是有序的。

高位优先

MSD（高位优先）基数排序的核心思想是从最高位开始，对数据进行递归分类，直到所有数字或字符串都排好序。

如上图所示，MSD 首先根据最高位对数据进行分组，然后再根据次高位对数据进行分组，以此类推，递归直到每组中只有一个元素。

MSD 基数排序适用于字符串或变长数据，因为它先处理最高位，可以提前分组。 适合字典序排序，如IP 地址、文件名、长整型数值等。