内部排序

排序概念

稳定性

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

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

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

元素移动次数

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

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

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

复杂度

趟特征

在排序算法中，一趟（pass） 通常指 完成一次从头到尾（或部分范围）对数组进行处理的过程，这一过程中可能会比较、移动、插入或交换若干元素。 换句话说，一趟就是排序算法中最小的完整“循环工作单元”，通常对应于外层循环的一次执行。

不同的排序算法在每趟排序后，数组中的元素会呈现不同特征，总结为下表：

伪代码

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

BubbleSort(arr)
    n ← arr.length
    for i from 0 to n - 1
        for j from 0 to n - i - 2
            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 - 1
            if arr[j] < arr[minIndex]
                minIndex ← j
        swap arr[i], arr[minIndex]

RadixSort(arr)
    找到数组中最大值，确定最大位数 d
    for i from 1 to d
        对数组按第 i 位进行**稳定排序**

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

Merge(left, right)
    result ← []
    while left ≠ ∅ and right ≠ ∅
        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], arr[j]
    swap arr[i + 1], arr[high]
    return i + 1

HeapSort(arr)
    BuildMaxHeap(arr)
    for i from arr.length - 1 down to 1
        swap arr[0], 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], arr[largest]
        MaxHeapify(arr, largest, n)

冒泡排序

冒泡排序（Bubble Sort）是一种简单的排序算法，通过反复遍历数组，比较相邻元素并交换位置，将较大的（或较小的）元素逐步“冒泡”到数组的一端。过程如下：

1. 从数组开头开始，比较相邻的两个元素，如果顺序不对（例如前者大于后者，假设升序排序），则交换它们。
2. 遍历一遍后，最大（或最小）的元素会被“冒泡”到数组末尾（或开头）。
3. 对剩余的未排序部分重复上述步骤，每次遍历的范围减少一个元素，直到数组完全排序。

在升序排序中，较大的元素像气泡一样逐渐“浮”到数组的末端（或较小的元素“沉”到开头），每次遍历都将一个元素推到正确的位置，形似气泡在水中上升的过程，因此得名“冒泡排序”。

比如，对于数组 5, 1, 4, 2, 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（整数除法）

操作

对于堆，重点掌握 堆化（heapify）、构建初始堆、删除 和 插入 操作。

堆化是从某个结点开始，调整以该结点为根的子树，使其满足堆性质（以最大堆为例说明其过程）：

• 比较 当前结点 与 左右子结点 的值。
• 如果 某个子结点 比 当前结点 大，交换 当前结点 与 较大的子结点。
• 交换后，继续对 被交换的子结点 递归地执行堆化，直到子树满足堆性质。

以大根堆 50,13,40,30,20,22,24,15,11 为例，若我们从结点 13 执行堆化，会发生如下图所示的过程：

注意堆化的过程是递归的，当我们交换父结点和子结点后，需要从子结点进一步执行堆化操作。

构造初始堆有两种方式：

• 方法 1：向一个初始为空的堆中不断 插入 新的元素。
• 方法 2：将无序数组转化为最大堆，核心是从最后一个非叶子结点开始，从后向前逐一对每个子树执行 堆化 操作。

以数组 1,3,5,4,6,13,10,9,8,15,17 为例，假设我们使用方法 2 将其初始化为大根堆，会发生如下图所示的过程：

堆中的删除一般都发生在堆顶，其过程如下：

• 将堆顶元素和堆中最后一个元素互换，然后删除最后一个结点
• 对新的堆顶执行 堆化，调整堆使其重新满足最大堆性质。

在堆中插入新元素后，需维护堆性质。

• 将新元素添加到堆底（数组末尾）。
• 从新元素开始，向上与父结点比较，若大于父结点则交换（上浮）。
• 重复上浮直到满足堆性质或到达堆顶。

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

// 调整 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，依次按照步长对所有子数组排序。