算法性能分析
时间复杂度描述了算法执行所需指令数量随着输入数据规模增长的变化趋势。它是一个理论概念，用于预测算法在不同规模输入下的性能表现，更好的时间复杂度通常意味着在相同条件下，算法的运行时间更短。
空间复杂度描述了算法执行过程中所需额外内存空间随着输入数据规模增长的变化趋势。它同样是一个理论概念，用于评估算法的内存使用效率，更好的空间复杂度意味着在相同条件下，算法占用的空间更少。
大 O 表示法是一种用来描述算法性能的数学符号，它提供了算法时间或空间需求的上界估计。通过忽略算法复杂度表达式中的低阶项和常数因子，大 O 表示法简化了对算法性能的分析，这种简化使得算法的渐进行为（随着输入规模的增长）更加突出，便于比较不同算法的效率。
例如，如果一个算法的时间复杂度为 O(n^2) ，这意味着在最坏的情况下，算法的执行时间随着输入规模 n 的增长而按二次方增长。同样，如果一个算法的空间复杂度为 O(n)，这意味着算法所需的额外内存空间随着输入规模线性增长。
在讨论算法的时间复杂度时，以下几点是关键：
- 可接受的性能：如果一个算法的时间复杂度不超过 O(n^2)，通常认为其性能是可以接受的。这意味着算法的运行时间随着输入规模的增长而按二次方增长。
- 更优的性能：如果算法的时间复杂度优于 O(n)，即亚线性时间，这通常被认为是非常优秀的。这类算法的运行时间增长慢于线性时间算法。
- 算法适用性：即使算法的时间复杂度不是最优的，这并不意味着算法不可用。它可能在处理大数据集时效率不高，但在小数据集上仍然表现良好。
- 小数据集的适用性：对于小数据集，即使时间复杂度高，指令数量的增加也不会太显著。因此，一些简单但时间复杂度不低的算法，如插入排序，可能仍然是合适的选择。
- 大数据集的挑战：在大数据集的情况下，算法的时间复杂度变得尤为重要。高效的算法可以显著减少处理时间和资源消耗。
- 算法选择：选择算法时，应根据数据集的大小、问题的具体需求和算法的实现复杂度来综合考虑。
排序算法
有七种常见的排序算法：
- 冒泡排序：通过重复遍历待排序的数列，比较每对相邻元素的大小，并在必要时交换它们的位置。它的时间复杂度通常为 O(n^2)。
- 选择排序：反复寻找未排序序列中的最小（或最大）元素，并将其放置在序列的起始位置。它的平均时间复杂度同样为 O(n^2)。
- 插入排序：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。它在小数据集或基本有序的数据集中表现优异。
- 希尔排序：也称为缩小增量排序，是插入排序的一种更高效的改进版本。它通过引入增量的概念来对数组进行分组，然后对每组进行插入排序。
- 快速排序：一种分而治之的排序算法，通过选取一个“基准”元素并将数列分为两部分，一部分包含所有小于基准的元素，另一部分包含所有大于基准的元素。
- 归并排序：通过递归地将数组分成两半，对每一半进行排序，然后将排序好的两半合并在一起。它是一种稳定的排序算法，时间复杂度为 O(n\log n)。
- 堆排序：利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的属性：即子节点的键值或索引总是小于（或者大于）它的父节点。
对于以上排序算法：
- 冒泡排序和选择排序通常仅用于教学目的，因为它们在实际应用中的效率较低。
- 插入排序适用于小数据集或部分有序的数据集，性能较好。
- 希尔排序在某些情况下可能不如插入排序或更高级的排序算法。
- 快速排序、归并排序和堆排序是适用于大数据集的高效排序算法，具有 O(n\log n) 的时间复杂度。
选择排序
选择排序（Selection Sort）是一种直观且易于理解的排序算法，它体现了一种直接且原始的问题解决方法。尽管它简单，但通常不推荐在实际应用中使用，因为它的性能相对较差。
在讲解排序算法时，通常以将一个整数数组从小到大排序为例，这有助于简化算法的实现和理解。当然，排序算法的思想同样适用于其他类型的元素或逆序排序的场景。
以数组 [16, 1, 45, 23, 99, 2, 18, 67, 42, 10] 为例，选择排序的工作原理如下：
- 第一轮选择：初始时，整个数组视为未排序。选择从数组开头到结尾的最小元素，并将其放置在数组的开头位置。
- 第二轮选择：剩余的数组部分（从第二个元素开始）被视为未排序。在这部分中找到最小元素，并将其移动到第二个位置。
- 重复选择：在每一轮选择中，继续在剩余的未排序元素中寻找最小值，并将其放置在未排序序列的开头。
- 最后一轮选择：当未排序序列的开头到达倒数第二个元素时，执行最后一轮选择。此时，数组中只剩下最后一个元素，它自然就是最大值，排序完成。
选择排序的特点是它不使用额外的存储空间（除了临时变量），但时间复杂度为 O(n^2)，这使得它在处理大数据集时效率较低。尽管如此，由于其实现简单，选择排序在教学和理解排序算法的基本概念时非常有用。
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))
#define SWAP(arr, i, j ) { \
int tmp = arr[i]; \
arr[i] = arr[j]; \
arr[j] = tmp; \
}
void print_arr(int arr[], int len) {
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// 选择排序
void selection_sort(int arr[], int len) {
/*
* i表示未排序序列的开头元素
* 最后一轮选择排序时，未排序序列的开头元素是数组倒数第二个元素
* i的每个取值都表示一轮选择排序
* 也就是选择排序一共执行 9 趟
*/
for (int i = 0; i < len - 1; i++) {
// 不妨直接假设未排序序列的开头i位置元素就是最小值
int min_index = i;
// 遍历未排序数组序列，找出真正的最小值下标，此时应遍历最后一个元素
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[min_index]) {
min_index = j; // 记录较小值的下标
}
} // for 循环结束时，未排序序列的最小值下标就是 min_index
// 交换 min_index 和下标 i 的元素
SWAP(arr, min_index, i);
// 选择排序一趟打印一次数组
print_arr(arr, len);
}
}
冒泡排序
冒泡排序（Bubble Sort）是一种基础的排序算法，以其操作形象得名。尽管它简单易懂，但其效率相对较低，因此在实际应用中并不常用，更多地作为教学工具来帮助理解排序算法的基本概念。
以数组 [16, 1, 45, 23, 99, 2, 18, 67, 42, 10] 为例，冒泡排序的工作原理如下：
- 第一轮冒泡：从数组的第一个元素开始，对相邻元素进行比较。如果当前元素大于其相邻的下一个元素，则交换它们。这样，经过一轮比较后，最大的元素会被“冒泡”到它应该在的位置，即数组的末尾。
- 后续轮次：在每一轮中，都将未排序部分的最大元素移动到其应在的位置。随着排序的进行，已排序的元素逐渐增多，需要比较的元素数量逐渐减少。
- 优化：如果在一轮遍历中没有发生任何交换，这意味着数组已经有序，可以提前结束排序过程。
- 结束条件：冒泡排序在最坏的情况下需要进行 n – 1 轮比较，其中 n 是数组的长度。但在优化的情况下，如果数组提前有序，可以减少比较次数。
冒泡排序的时间复杂度在最坏和平均情况下都是 O(n^2)，最好情况下（即数组已经是有序的）时间复杂度为 O(n)。尽管有优化空间，但由于其固有的比较和交换操作，冒泡排序通常不适用于大型数据集的排序任务。
void bubble_sort(int arr[], int len) {
// 外层 for 的 i 表示第几轮冒泡排序，最多需要进行 len - 1 轮
for (int i = 1; i < len; i++) {
// 标记在这一次冒泡排序中有没有交换，false 表示没有交换
bool swapped = false;
/*
* j 表示两两比较元素中的第一个元素的下标
* 第一轮 j 的最大取值是数组倒数第二个元素，并且逐步减小
* 所以 j 的条件是小于 (len - i)
*/
for (int j = 0; j < len - i; j++) {
if (arr[j] > arr[j + 1]) {
SWAP(arr, j, j + 1);
// 发生了交换改变标记
swapped = true;
}
}
// 在一轮冒泡排序中没有任何交换，则排序已经完成，终止循环
if (!swapped) {
break;
}
// 打印一轮冒泡排序后数组的元素排列
print_arr(arr, len);
}
}
插入排序
插入排序（Insertion Sort）是一种直观且易于实现的排序算法，其工作原理与打牌时整理手牌的过程相似。以下是对插入排序工作原理的描述：
- 初始化：将数组的第一个元素视为一个已排序的子序列。
- 遍历数组：从数组的第二个元素开始，对数组进行遍历。
- 比较与交换：
- 取出当前遍历到的元素，与已排序子序列中的元素从后向前逐一比较。
- 如果当前元素小于已排序子序列中的元素，则将后者向后移动，为当前元素腾出位置。
- 重复比较和移动过程，直到找到当前元素在已排序子序列中的合适位置或到达子序列的开头。
- 插入元素：将当前元素插入到已找到的位置。
- 重复过程：继续遍历数组，重复步骤 3 和 4，直到所有元素都被插入到已排序子序列中。
- 完成排序：当遍历到达数组的最后一个元素时，整个数组变为有序。
插入排序的时间复杂度在最坏情况下为 O(n^2)，但如果输入数组已经接近有序，其性能会非常接近线性时间 O(n)。这使得插入排序在小数据集或部分有序的数据集中非常有效。
void insertion_sort(int arr[], int len) {
// 外层 for 循环中的 i 表示每轮选择排序新插入元素的下标，也就是"新摸手牌"的下标
// 从数组第二个元素开始，后面的每一个元素都相当于"你要摸的手牌"
for (int i = 1; i < len; i++) {
// 内层 for 循环的 j 表示新插入元素需要比较元素的下标，也就是每一张"老手牌"的下标
// j 从 i 的前一个位置开始，递减,但不可能成为负数
for (int j = i - 1; j >= 0; j--) {
if (arr[j] > arr[j + 1]) { // 注意:这里如果加等号就不是稳定的排序算法了
// 前面的元素比后面的元素大，交换
SWAP(arr, j, j + 1);
}
else {
// 只需要在某一次比较中，发现前一个元素小于等于后一个元素
// 那么前面的元素就一定都是排序好的，此时这一轮选择排序结束
break;
}
}
// 打印每一轮选择排序后，数组的元素序列
print_arr(arr, len);
}
}
希尔排序
希尔排序（Shell Sort）是由美国计算机科学家唐纳德·希尔（Donald Shell）在 1959 年提出的。这种排序算法是插入排序的一个改进版本，旨在通过引入增量的概念来提高排序效率。
希尔排序的工作原理：
- 增量序列：希尔排序的核心在于增量序列的选择。增量序列决定了排序过程中元素的比较和交换的步长。
- 分组比较：通过增量，算法将数组分成多个组，每组内的元素间隔为增量值。例如，如果增量为 5，那么第一个元素与第五个元素比较，第二个元素与第六个元素比较。
- 组内插入排序：在每组内进行插入排序，这允许较小的元素“跳跃”到前面的位置，从而减少整体的比较和移动次数。
- 增量减小：完成一轮排序后，减小增量（通常是减半），并重复上述步骤。
- 最终插入排序：当增量减小到 1 时，整个数组进行一次标准的插入排序，此时数组已经接近有序，因此排序效率很高。
// 希尔排序: 缩小增量排序，其实就是多人摸牌，逐渐减少摸牌人数
// 希尔排序中，增量序列的设计非常重要,这里采取简单的 gap 序列: 长度减半..一直减半,直到为1
// gap 为 1 时就是一个在数组元素基本有序情况下的,插入排序
void shell_sort(int arr[], int len) {
// 第一个元素是第一个人的初始手牌，一直到第 gap 个元素都是初始手牌
int gap = len >> 1;
while (gap > 0) {
// 外层 for 的 i 仍然代表新摸到的手牌的下标，i 从 gap 开始，直到摸完整个数组元素
for (int i = gap; i < len; i++) {
// 先记录一下新手牌的值，便于后续的插入操作
int tmp = arr[i];
int j = i - gap; // 代表每一个人旧手牌的最后一张牌
for (; j >= 0; j -= gap) {
// 内层 for 代表 每个人每摸到一张新手牌,都会和原本的旧手牌比较，但由于 gap 存在，所以需要减去 gap
if (arr[j] > tmp) { // 注意:不能加 =，加了就不稳定了
arr[j + gap] = arr[j]; // 将旧手牌中大于新手牌的所有牌都向后移
}
else
{
break; // 只要发现一张旧手牌更小或相等，就说明已经找到新手牌的插入位置了
}
}
arr[j + gap] = tmp;
}
print_arr(arr, len); // 每一轮希尔排序后查看数组排序结果
gap >>= 1; // 每一轮希尔排序，增量都减半
}
}
增量序列的选择：
- 希尔本人提出的增量序列是 \dfrac{n}{2}, \dfrac{n}{4},…,1 ，这种序列易于实现，但不是最优解。
时间复杂度：
- 希尔排序的时间复杂度与增量序列的选择密切相关。使用希尔提出的增量序列，时间复杂度通常小于 O(n^2)，但在最坏情况下可能接近 O(n^2)。
空间复杂度：
- 希尔排序是一种原地排序算法，不需要额外的内存空间，因此空间复杂度是 O(1)。
稳定性：
- 希尔排序不是稳定的排序算法。由于其分组和插入排序的特性，相同的元素可能会因为分组的不同而改变相对位置。
- 假设有一个数组
[4a,3,4b,2,1]，如果选择的增量是 3，那么第一轮希尔排序后的结果可能是[2,1,4b,4a,3]，这表明希尔排序可能会改变相同元素的相对顺序。
希尔排序通过减少插入排序中的元素移动次数来提高效率，尤其适合于大规模数据集的初步排序。尽管它不是最高效的排序算法，但其简单性和对部分有序数据集的有效性使其在某些应用场景中仍然有其价值。
归并排序
- 归并排序函数的声明：
void mergesort(int arr[], int len);这个函数声明定义了归并排序的主要接口，其中
arr是要排序的数组，len是数组的长度。 -
递归分解与合并的辅助函数声明：
void dividemerge_recursion(int arr[], int left, int right);这个辅助函数用于递归地分解数组区间，并在适当的时候合并这些区间，以完成排序。
-
dividemerge_recursion函数的实现：
- 分解思路：将数组
arr的[left, right]区间分解为左右两个子区间，然后递归地对这两个子区间进行排序。 - 区间中间索引：区间的中间索引可以通过
((right - left) >> 1) + left计算得到，这是一种避免潜在溢出的高效计算方法。 - 递归分解的出口：当
left大于或等于right时，递归结束，因为这意味着区间内没有元素或只有一个元素，已经有序。 -
合并操作：递归分解后，需要执行合并操作，将排序好的左右子区间合并为一个有序区间。
-
合并两个有序子数组的步骤：
- 使用临时数组：为了简化合并过程，通常使用一个临时数组来存储合并后的结果。
- 选择元素：在合并过程中，当左右子数组中有相同的元素时，应优先选择左子数组中的元素。这样做可以保持相等元素的原始顺序，从而确保归并排序的稳定性。
- 合并结束条件：当任一子数组的索引超出其长度时，即认为该子数组已完全合并，此时合并过程结束。
- 处理剩余元素：合并结束后，如果一个子数组还有剩余元素，应将这些元素复制到临时数组的末尾。
- 复制回原数组：一旦临时数组包含了合并后的全部元素，应将这些元素复制回原数组的相应位置。
- 是否必须使用临时数组进行归并？
归并排序的合并步骤可以通过以下方式实现，而不使用临时数组：
- 原地合并：理论上，可以通过在原数组上进行操作来实现原地合并，但这通常涉及到复杂的元素交换和可能的数组旋转。
- 性能问题：原地合并可能会增加算法的复杂性，导致性能下降。在最坏的情况下，如果每次合并都需要大量交换，时间复杂度可能会接近 O(n^2)。
- 稳定性问题：原地合并可能会破坏排序算法的稳定性，因为相同元素可能需要在数组中移动较远的距离。
选择哪种临时数组？
对于使用临时数组的选择，有以下几种考虑：
- 栈局部变量临时数组：
- 优点：自动内存管理，方便安全，性能较高。
- 缺点：无法动态分配，长度需预先确定，不适合大数组合并。
- 数据段全局变量临时数组：
- 缺点：引入复杂性，维护困难，始终占用内存，无法动态分配。
- 堆动态临时数组：
- 优点：可以动态分配，适合大数组合并，空间大小可预先计算。
- 缺点：需要手动内存管理，存在一定风险，性能可能略低。
结论： 尽管原地合并在理论上可行，但在实践中，使用临时数组进行归并排序的合并步骤更为常见和推荐。这种方法简单、高效，且保持了归并排序的稳定性和 O(n\logn) 的时间复杂度。
-
归并排序是一种经典的排序算法，其特点和性能表现如下：
- 输入质量无关性：归并排序的执行流程是固定的，先分解数组区间，然后逐步合并。因此，数据的初始状态对归并排序的执行没有影响，这使得其性能非常稳定和均衡。
- 时间复杂度：在所有情况下，归并排序的时间复杂度始终保持为 O(nlogn)O(n log n)，其中 n n 是数组的长度。
- 空间复杂度：归并排序是非原地排序算法，需要使用临时数组来辅助合并过程，因此其空间复杂度为 O(n)O(n)。
- 稳定性：归并排序是一种稳定的排序算法，能够保持相等元素的原始顺序，这在需要维持排序稳定性的场景中非常有用。
归并排序的总结：
- 在处理大数据集时，如果需要一个既高效又稳定的排序算法，归并排序是一个非常好的选择。
- 稳定性是归并排序的最大优势，这使得它在实际应用中非常受欢迎。
- 然而，归并排序也有一些缺点：
- 它的性能可能不如快速排序。
- 使用递归实现可能导致栈溢出的风险，尤其是在处理大数据集时。
- 需要占用额外的内存空间来存储临时数组。
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define ARR_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
// 打印数组的函数
void print_arr(int arr[], int left, int right) {
for (int i = left; i <= right; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
/**
* 合并的思路:
* 1. 把左右子数组中元素按照顺序合并到临时数组中，过程类似"穿针引线"
* 2. 将排好序的临时数组元素按照下标赋值给原数组
* 注：临时数组和原数组共有一套下标
* 传入函数逻辑上的左右子数组是有序的，相当于合并两个有序的左右子数组
*/
static void merge(int arr[], int left, int mid, int right, int* tmp) {
/**
* tmp_idx: 用于存放合并结果的临时数组的开始下标
* left_idx: 左子数组的开始下标
* right_idx: 右子数组的开始下标
*/
int tmp_idx = left, left_idx = left, right_idx = mid + 1;
// 只要左右子数组同时还有元素
while (left_idx <= mid && right_idx <= right) {
// 比较左右子数组的元素,按照从小到大放入临时数组
// <= 判断不会改变相同元素的相对位置，是稳定算法。反之则不是稳定算法
if (arr[left_idx] <= arr[right_idx]) {
tmp[tmp_idx++] = arr[left_idx++];
}
else {
tmp[tmp_idx++] = arr[right_idx++];
}
}
// while 结束时，左右子数组必然有一个没有元素了，此时另一个数组必然还有元素
// 也就是说只会有一个数组是空的
// 但我们无法确定是哪个数组没有元素了
// 所以我们都判断一下将左右子数组还剩余的元素取出来
while (left_idx <= mid) {
// 说明左数组还有元素
tmp[tmp_idx++] = arr[left_idx++];
}
while (right_idx <= right) {
// 说明右数组还有元素
tmp[tmp_idx++] = arr[right_idx++];
}
// 将临时数组中已排序好的元素复制到原始数组中
for (int i = left; i <= right; i++) {
arr[i] = tmp[i];
}
// 打印此一轮归并排序的元素
print_arr(arr, left, right);
}
/**
* 辅助函数,实现对 [left, right] 范围内的数组递归分解合并
* left 表示递归分解的区间起点，right 表示递归分解区间的终点，是一个闭区间
* 递归分解的思路是:
* 对 [left, right] 区间元素的排序,可以分解成:
* [left, mid] 区间，和[mid + 1, right]区间的排序合并
* 递归的出口是:
* 如果区间仅有一个元素或没有元素,递归结束
*/
static void divide_merge(int arr[], int left, int right, int* tmp) {
// 递归的出口
if (left >= right) {
return;
}
// 递归体
// 计算中间索引
int mid = left + (right - left >> 1);
// 分解,规定左数组是[left, mid]
// 右数组是[mid + 1, right]
divide_merge(arr, left, mid, tmp);
divide_merge(arr, mid + 1, right, tmp);
/**
* 归并，归并排序的核心操作
* 需要一个临时数组完成此操作
* 这个临时数组至少要和原先的数组一般大
* 有两种方案：
* 1. 用全局变量数组或局部变量，该方式简洁易实现,无需考虑内存回收
* 但缺点是
* a. 必须编译时期确定数组长度，无法运行时期动态分配
* b. 栈区和数据段都无法创建长数组,在大数据集下容易产生溢出错误
* 为了解决这两个缺点，我们可以在堆上动态分配数组
* 但同样也有缺点:
* a. 内存管理风险
* b. 动态分配数组会带来额外性能开销
*/
merge(arr, left, mid, right, tmp);
}
void merge_sort(int arr[], int len) {
// 临时数组
int* tmp = calloc(len, sizeof(int));
if (tmp == NULL){
printf("calloc failed in merge_sort.\n");
return;
}
// 将整个数组进行递归分解合并，即完成归并排序
divide_merge(arr, 0, len - 1, tmp);
// 不要忘记 free 释放资源
free(tmp);
}
快速排序
单向分区
-
单向分区快速排序的实现函数声明：
void quicksortoneway(int arr[], int len);这个函数声明定义了快速排序的主要接口，其中
arr是要排序的数组，len是数组的长度。 -
辅助的递归函数声明：
static void partitionrecursion(int arr[], int left, int right);这个辅助函数用于递归地分解数组区间，并在分解过程中完成排序。
-
分区操作：
- 分区操作是快速排序的核心，它通过选择一个基准值（pivot）来确定其在最终排序数组中的定位。
- 分区过程将数组划分为两个子区间，一个包含所有小于基准值的元素，另一个包含所有大于基准值的元素。
- 递归地对这两个子区间进行分区操作，这个过程称为“分而治之”。
-
分区与合并：分区操作完成后，由于快速排序是原地排序算法，子区间的排序会自动完成整个区间的排序，不需要额外的合并步骤。
// 分区核心操作实现,返回一轮快排选择的 pivot 的下标
int partition(int arr[], int left, int right) {
// 随机选择一个基准值，然后把它先放到数组末尾
int pivot_idx = left + rand() % (right - left + 1); // 得到一个 [left, right] 范围内的随机索引
int pivot = arr[pivot_idx];
SWAP(arr, pivot_idx, right);
// 设置一个 partition_idx 索引，指示小于 pivot 的元素应该插入的位置
// 同时该索引最终表示分区的界限索引，所以命名为 partition_idx
int partition_idx = left;
// 遍历整个数组，当元素小于 pivot 时,将它和 partition_idx 位置元素交换，partition_idx 加 1
// 希望遍历结束时，i 指向数组末尾的 pivot，所以 i < right
for (int i = left; i < right; i++) {
if (arr[i] < pivot) {
SWAP(arr, i, partition_idx);
partition_idx++;
}
}
// 遍历结束后,将 pivot 元素(最后一个元素)交换到 partition_idx 位置
SWAP(arr, right, partition_idx);
// 返回基准值的位置索引
return partition_idx;
}
/**
* 辅助函数
* 用于对对 [left, right] 区间中的元素进行递归分区操作
*/
void partition_recursion(int arr[], int left, int right) {
// 递归出口
if (left >= right) {
return;
}
// 递归体
int idx = partition(arr, left, right); // 分区操作，找到 pivot 元素的下标位置
partition_recursion(arr, left, idx - 1);
partition_recursion(arr, idx + 1, right);
}
void quick_sort_one_way(int arr[], int len) {
// 初始化随机数生成器，time(NULL) 获取当前时间戳
// 用于生成随机索引
srand(time(NULL));
// 调用辅助函数进行递归分解
partition_recursion(arr, 0, len - 1);
}
单向分区： 单向分区快速排序的实现使用一个索引来跟踪小于基准值的元素应该存储的位置。通过这个索引，算法将遍历数组，并将所有小于基准值的元素交换到数组的前部。一轮遍历结束后，基准值被放置在其最终位置，将数组分为左右两个子区间。
单向分区的优化：
- 双向分区：在遍历数组的过程中，可以同时从两边开始，一边将小于基准值的元素向数组开头移动，另一边将大于基准值的元素向数组末尾移动。这种方法称为双向分区。
- 元素赋值：为了避免元素交换，可以使用赋值操作来替代。这种方法减少了交换操作的开销，因为赋值通常比交换操作更高效。
双向分区
双向分区策略实现： 在双向分区中，使用两个索引 low 和 high 来对数组进行分区。
- 初始化：选择数组的第一个元素作为基准值，并将其交换到数组的开头，同时初始化
low为 0，high为数组长度减一。 low索引的作用：- 指示下一个比基准值小的元素应该放置的位置。
- 从左向右遍历数组，寻找比基准值大或相等的元素，并将其覆盖到
low索引的位置。
high索引的作用：- 指示下一个比基准值大或相等的元素应该放置的位置。
- 从右向左遍历数组，寻找比基准值小的元素，并将其覆盖到
high索引的位置。
- 分区过程：
- 初始时，
high向左移动一位，low向右移动一位，开始交替搜索过程。 - 当
low遇到一个大于或等于基准值的元素，或high遇到一个小于基准值的元素时，交换这两个元素。 - 继续移动
low和high，直到它们相遇。相遇点即为基准值的最终位置。
- 初始时，
- 递归排序：一旦基准值就位，递归地对左侧和右侧的子区间执行相同的分区操作。
// 快速排序的核心操作: 双向分区，也就是确定 pivot 的最终位置
// 挑选一个基准值,通过双向分区操作,决定最终的位置,最终位置就是基准值排好序的位置
static int partition(int arr[], int left, int right) {
// 为了简化实现，直接挑选首元素为基准值（因为基准值要交换到开头，所以直接挑选首元素作为基准值，可以减少一步交换）
int pivot = arr[left];
// 初始化两个索引 low 和 high，分别指向数组两端
int low = left, high = right;
// 循环遍历这个数组区间
while (low < high) { // 两个索引没有相遇就继续循环
// 在两个索引没有相遇的情况下，high 索引用于寻找比基准值小的元素
while (low < high && arr[high] >= pivot) {
high--;
} // while 循环结束时,要么两个索引相遇了，要么 high 索引已经找到了一个比基准值小的元素
arr[low] = arr[high]; // 将这个比基准值小的元素覆盖到low位置
//low++; 该行语句不能加，因为若此时两个索引相遇结束 while，low++ 将导致相遇的索引不再相遇
// 在两个索引没有相遇的情况下，low 索引用于寻找比基准值大和相等的元素
while (low < high && arr[low] < pivot) {
low++;
} // while 循环结束时,要么两个索引相遇了，要么 low 索引已经找到了一个比基准值大或相等的元素
arr[high] = arr[low]; // 将这个比基准值大或相等的元素覆盖到 high 位置
//high--; 该行语句不能加，因为若此时两个索引相遇结束 while，high-- 将导致相遇的索引不再相遇
} // while 循环结束时，说明 low 和 high 索引相遇,此时该位置就是 pivot 应该放置的位置
arr[low] = pivot;
return low;
}
// 对 [left, right] 区间进行递归分区操作
void partition_recursion(int arr[], int left, int right) {
// 递归出口
if (left >= right) {
return;
}
// 递归体
int idx = partition(arr, left, right); // 分区操作，找到 pivot 下标位置
partition_recursion(arr, left, idx - 1);
partition_recursion(arr, idx + 1, right);
}
void quick_sort_two_way(int arr[], int len) {
partition_recursion(arr, 0, len - 1);
}
int main(void) {
int arr[] = { 8,3,2,6,9,5 };
int len = ARR_SIZE(arr);
// 测试双向分区-快速排序
quick_sort_two_way(arr, len);
return 0;
}
快速排序算法分析
快速排序算法是一种高效的排序方法，其性能分析如下：
- 性能优势：
- 双向分区策略可以减少不必要的遍历，提高效率。
- 使用元素赋值替代元素交换操作，减少了指令数量。
- 时间复杂度：
- 在最佳和平均情况下，快速排序的时间复杂度为 O(n\log n)。
- 在最坏情况下，如果每次都选择到一个糟糕的基准值，时间复杂度会退化为 O(n^2) 。
- 基准值选择优化：随机选择基准值或采用“多选一”中位数策略，以避免最坏情况。
- 空间复杂度：快速排序是原地算法，但递归实现会占用栈空间，空间复杂度在 O(\log n) 到 O(n) 之间变动。
- 稳定性：快速排序不是稳定的排序算法。
快速排序总结：
- 在大数据集排序场景中，快速排序因其高效性通常是首选。
- 快速排序的缺点包括：
- 不稳定性，可通过其他稳定排序算法弥补。
- 最坏情况下性能退化至 O(n^2)，且递归实现可能导致栈溢出。
堆排序
堆排序的基本概念：
- 堆：在数据结构中，堆是一棵特殊的完全二叉树，它可以在数组中按照特定顺序存储，使得父节点的值总是大于或等于（大顶堆）或小于或等于（小顶堆）其子节点的值。
- 大顶堆：根节点是树中最大元素的堆结构。
- 小顶堆：根节点是树中最小元素的堆结构。
堆排序的实现：
- 在堆排序过程中，通常使用大顶堆来实现。
- 无需创建实际的堆数据结构，而是将待排序数组视为一个大顶堆。
- 通过调整数组元素，使其满足大顶堆的性质，然后逐步将堆顶元素（最大值）移动到数组的末尾，减小堆的大小，并重新调整剩余元素以维持大顶堆的性质。
堆排序的算法特点：
- 堆排序是原地算法，不需要额外的数组空间来进行排序。
- 堆排序不使用递归，因此避免了栈溢出的风险。
要将数组视为一个大顶堆，我们可以按照以下步骤操作：
- 理解数组与完全二叉树的关系：在数组中，对于任意元素（除了最后一个），其索引为
i的父节点的左右子节点索引分别为2i + 1和2i + 2。 - 构建大顶堆：对于给定的数组
int arr[] = {4, 10, 3, 5, 1};，我们需要调整元素的位置，以满足大顶堆的性质，即每个父节点的值都大于其子节点的值。 - 堆排序过程：
- 首先，将数组构建成一个逻辑上的大顶堆。
- 交换堆顶元素（数组首元素，即最大值）与最后一个元素，然后将该最大值视为已排序，从待排序元素中移除。
- 调整剩余元素，重新构建大顶堆。
- 重复上述过程，每次从堆顶移除最大元素，并重新构建大顶堆，直到所有元素都被排序。
- 定义函数：
- 构建大顶堆的函数：从最后一个父节点开始，向上调整每个节点，以满足大顶堆的性质。
- 调整堆的函数：在移除堆顶元素后，将最后一个元素放到堆顶，并调整堆以维持大顶堆结构。
