常见的排序算法（二）

归并排序

归并排序（Merge Sort）是一种基于分治法（Divide and Conquer）的排序算法。它将一个大的问题分解成小的问题，然后递归地解决这些小问题，最后合并（merge）得到最终的排序结果。归并排序的时间复杂度为 ( O(n \log n) )，它是一种稳定的排序算法。由于其稳定性和良好的最坏情况表现，归并排序在许多实际应用中都有着重要的地位。

一、归并排序的基本思想

归并排序的核心思想是将数组分成两个子数组，对这两个子数组分别进行排序，排序完成后再将它们合并成一个有序数组。归并排序的分治过程通常通过递归来实现：

1. 分解：将数组分成两半。
2. 解决：递归地对这两半数组分别进行归并排序。
3. 合并：将两个有序的子数组合并成一个有序数组。

这种方法可以持续分解直到每个子数组只有一个元素，因为一个元素的数组默认是有序的。然后通过合并操作将这些有序的子数组组合成一个大的有序数组。

二、归并排序的具体步骤

1. 递归分解

首先，将一个大的数组分解成两个小数组，再递归地对这两个小数组进行归并排序，直到每个数组只有一个元素。

2. 合并操作

合并是归并排序的核心步骤。将两个已经排好序的数组合并成一个有序数组。对于每对元素，比较它们的大小，把较小的元素放入结果数组中，直到所有元素都合并完成。

3. 递归的终止条件

递归终止的条件是子数组的大小为1，此时该子数组已经是有序的，可以进行合并。

三、归并排序的时间复杂度分析

归并排序的时间复杂度为 ( O(n \log n) )，其中：

• 分解的次数：每次将数组分成两半，直到每个子数组只有一个元素。这个过程是递归的，深度为 ( \log n )。
• 合并的时间复杂度：每次合并操作需要遍历所有的元素，时间复杂度为 ( O(n) )。

因此，归并排序的总时间复杂度是 ( O(n \log n) )。

四、归并排序的空间复杂度分析

归并排序需要额外的空间来存储合并过程中生成的临时数组。每一次合并都需要额外的空间，因此空间复杂度为 ( O(n) )。

五、归并排序的特点

1. 稳定性：归并排序是一个稳定的排序算法，即两个相等的元素在排序后相对位置不变。
2. 时间复杂度：在最坏、最好、平均情况下，归并排序的时间复杂度都是 ( O(n \log n) )。
3. 空间复杂度：归并排序需要额外的 ( O(n) ) 空间来存储临时数据。
4. 适用场景：适用于大规模数据排序，尤其是当数据量很大时，归并排序表现非常稳定。特别适用于外部排序（比如磁盘上的数据排序）。

六、归并排序的C语言实现

下面是归并排序的 代码示例：

#include <stdio.h>// 合并两个子数组 arr[left..mid] 和 arr[mid+1..right]
void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1;  // 左子数组的长度int n2 = right - mid;     // 右子数组的长度// 创建临时数组int leftArr[n1], rightArr[n2];// 将数据复制到临时数组for (int i = 0; i < n1; i++)leftArr[i] = arr[left + i];for (int i = 0; i < n2; i++)rightArr[i] = arr[mid + 1 + i];// 合并临时数组到原始数组int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {arr[k] = leftArr[i];i++;} else {arr[k] = rightArr[j];j++;}k++;}// 将剩余的元素复制到原数组while (i < n1) {arr[k] = leftArr[i];i++;k++;}while (j < n2) {arr[k] = rightArr[j];j++;k++;}
}// 归并排序的递归实现
void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;  // 计算中间位置// 递归排序左半部分mergeSort(arr, left, mid);// 递归排序右半部分mergeSort(arr, mid + 1, right);// 合并已排序的子数组merge(arr, left, mid, right);}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};  // 示例数组int arr_size = sizeof(arr) / sizeof(arr[0]);printf("原始数组: \n");printArray(arr, arr_size);mergeSort(arr, 0, arr_size - 1);  // 调用归并排序printf("排序后的数组: \n");printArray(arr, arr_size);return 0;
}

代码解释：

1. merge函数：合并两个已经排序的子数组。arr[left..mid] 和 arr[mid+1..right]，将它们合并成一个有序数组并放回原数组 arr 中。
2. mergeSort函数：归并排序的递归实现，首先将数组分割成两个子数组，然后递归地对这两个子数组进行排序，最后合并它们。
3. printArray函数：打印数组，用于显示排序前后的数组。

测试结果：

原始数组: 12 11 13 5 6 7 排序后的数组: 5 6 7 11 12 13

七、归并排序的改进

尽管归并排序是一种非常有效的排序算法，但它的空间复杂度 ( O(n) ) 使得它在某些情况下表现不如其他排序算法。例如，对于小规模的数据，快速排序和堆排序可能会有更好的表现。为了优化归并排序的一些空间消耗，有人提出了优化版本：

1. 原地归并排序：将归并过程进行修改，避免使用额外的数组来存储临时数据，减少空间开销。但这会使代码变得更加复杂。

2. 优化合并过程：对于已经部分有序的数组，优化合并过程，减少不必要的操作。

小结：

归并排序作为一种稳定的、时间复杂度为 ( O(n \log n) ) 的排序算法，适用于大规模数据的排序。尽管它需要额外的空间，但其性能非常稳定，在最坏情况下也不会退化。归并排序尤其在外部排序中有重要应用，比如对磁盘中的大量数据进行排序。

堆排序

堆排序（Heap Sort）是一种利用堆（Heap）数据结构的排序算法。它的核心思想是通过构建最大堆或最小堆来排序。堆是一种完全二叉树，满足堆的性质，即每个节点的值都大于或小于其子节点的值。堆排序通过不断地调整堆的结构来实现排序。

一、堆的定义与性质

堆是一个完全二叉树，并且满足以下两个性质之一：

• 最大堆：对于树中的任意节点 ( i )，有 ( A[i] \geq A[2i+1] ) 和 ( A[i] \geq A[2i+2] )，即父节点的值大于或等于子节点的值。
• 最小堆：对于树中的任意节点 ( i )，有 ( A[i] \leq A[2i+1] ) 和 ( A[i] \leq A[2i+2] )，即父节点的值小于或等于子节点的值。

二、堆排序的基本步骤

堆排序的过程可以分为两大部分：

1. 构建堆：将无序数组构建成一个堆。堆可以是最大堆或最小堆，通常我们使用最大堆来实现升序排序。
2. 堆调整：将堆顶元素（最大值）与堆的最后一个元素交换，然后减少堆的大小（忽略最后一个元素），重新调整堆，使其恢复堆的性质。重复这个过程直到堆的大小为1。

堆排序的时间复杂度为 ( O(n \log n) )，其中 ( n ) 是待排序数组的元素个数。

三、 堆排序的工作原理

构建最大堆：

1. 从最后一个非叶子节点开始，逐个向上调整每个节点的位置，使其满足最大堆的性质。
2. 调整过程涉及比较父节点与子节点的值，若父节点小于任何一个子节点，就交换它们的位置，并递归地对交换后的子树进行调整。

堆排序的具体过程：

1. 构建最大堆：从数组的最后一个非叶子节点开始，调整堆，直到根节点。
2. 交换根节点与最后一个节点：将堆顶元素（最大元素）与数组最后一个元素交换。
3. 减少堆的大小：忽略最后一个元素（它已经是排好序的），调整剩下的元素，使其重新成为最大堆。
4. 重复上述步骤：直到堆中只剩下一个元素为止。

四、 堆排序的代码实现

接下来，通过C语言实现堆排序的具体过程。我们首先需要实现最大堆的调整操作，然后通过交换堆顶元素与堆的最后一个元素来实现排序。

#include <stdio.h>// 调整堆的函数，确保根节点满足最大堆性质
void heapify(int arr[], int n, int i) {int largest = i;  // 根节点int left = 2 * i + 1;  // 左子节点int right = 2 * i + 2;  // 右子节点// 比较根节点、左子节点和右子节点，找出最大值if (left < n && arr[left] > arr[largest]) {largest = left;}if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大值不是根节点，交换它们并递归调整if (largest != i) {int temp = arr[i];arr[i] = arr[largest];arr[largest] = temp;// 递归地调整被交换位置的子树heapify(arr, n, largest);}
}// 堆排序的主函数
void heapSort(int arr[], int n) {// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 逐步将最大元素放到数组的末尾for (int i = n - 1; i >= 1; i--) {// 交换根节点（最大值）与当前最后一个元素int temp = arr[0];arr[0] = arr[i];arr[i] = temp;// 调整堆的大小heapify(arr, i, 0);}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {printf("%d ", arr[i]);}printf("\n");
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组：\n");printArray(arr, n);heapSort(arr, n);printf("排序后的数组：\n");printArray(arr, n);return 0;
}

代码解析：

1. heapify函数：该函数用于调整堆的性质。它接收数组 arr，数组大小 n，和当前节点的索引 i。通过比较当前节点与左右子节点的值，决定是否交换它们，并递归地调整子树，直到整个子树满足堆的性质。

2. heapSort函数：该函数实现堆排序的主逻辑。首先通过 heapify 构建一个最大堆，然后将堆顶的最大元素与堆的最后一个元素交换，减少堆的大小，再次调用 heapify 调整堆。重复这一过程，直到所有元素都被排好序。

3. printArray函数：打印数组，用于查看排序前后的结果。

4. main函数：主函数中，我们定义了一个待排序的数组，调用堆排序函数，并输出排序结果。

五、堆排序的时间复杂度分析

堆排序的时间复杂度是 ( O(n \log n) )，下面是详细分析：

• 构建最大堆：从最后一个非叶子节点开始，调整堆。调整每个节点的时间复杂度是 ( O(\log n) )，总的构建堆的时间复杂度是 ( O(n) )。

• 交换与堆调整：在堆排序过程中，每次将堆顶元素交换到数组末尾，然后减少堆的大小并调整堆。每次调整堆的时间复杂度是 ( O(\log n) )，总共需要进行 ( n-1 ) 次交换，因此总体时间复杂度是 ( O(n \log n) )。

综上所述，堆排序的时间复杂度为 ( O(n \log n) )。

六、 堆排序的空间复杂度

堆排序的空间复杂度是 ( O(1) )，因为它是原地排序算法，不需要额外的空间来存储数据，只需要常数空间来存储一些辅助变量。

七、堆排序的优缺点

优点：

• 时间复杂度稳定：无论数据的初始状态如何，堆排序的时间复杂度始终是 ( O(n \log n) )，不像快速排序那样最坏情况下退化到 ( O(n^2) )。
• 原地排序：堆排序不需要额外的存储空间，只需要常数空间。

缺点：

• 不稳定排序：堆排序是一个不稳定的排序算法，即相等的元素可能会改变相对顺序。
• 常数因子较大：与快速排序相比，堆排序常数因子较大，通常在实际应用中速度较慢。

八、总结

堆排序是一种基于堆数据结构的高效排序算法，它通过构建最大堆（或最小堆）来实现排序。堆排序具有 ( O(n \log n) ) 的时间复杂度，并且是原地排序算法，不需要额外的空间。然而，堆排序的主要缺点是它是一种不稳定排序，因此在一些需要稳定排序的场合，可能需要选择其他排序算法。