数据结构：堆排序、冒泡排序与 Hoare 快排实战

数据存储时需进行上浮调整，确保满足最大堆性质：

void Storage(Pile* pilestruct, int data) { 
    assert(pilestruct); 
    if ((pilestruct->size + 1) == pilestruct->max) { 
        int* pc = (int*)realloc(pilestruct->space, sizeof(int) * (pilestruct->max) + MAX); 
        if (pc == NULL) { 
            perror("realloc"); 
            return; 
        } 
        pilestruct->space = pc; 
        pilestruct->max += MAX; 
    } 
    pilestruct->size++; 
    pilestruct->space[pilestruct->size] = data; 
    Adjust(pilestruct->space, pilestruct->size); 
}

void Adjust(int * space, int child) { 
    int parent = child / 2; 
    while (child > 1) { 
        if (space[child] > space[parent]) { 
            Exchange(&space[child], &space[parent]); 
            child = parent; 
            parent = child / 2; 
        } else break; 
    } 
}

存储后效果如下：

排序堆

将堆顶元素与堆的最后一个元素交换，然后 size--，去除堆顶元素。注意这里的去除只是将堆元素个数减一，并不是删除。然后一直重复这样的操作，直到将所有元素调整完。

核心思想是利用多次下沉调整每次将最大值放到末尾，这样就达到了有序数据。

void Pilesort(Pile* pilestruct) { 
    assert(pilestruct); 
    int parent = 1; 
    int child = 2 * parent; 
    Exchange(&pilestruct->space[pilestruct->size], &pilestruct->space[1]); 
    pilestruct->size--; 
    while (child <= pilestruct->size) { 
        if (child < pilestruct->size && pilestruct->space[child] < pilestruct->space[child + 1]) { 
            child++; 
        } 
        if (child <= pilestruct->size && pilestruct->space[child] > pilestruct->space[parent]) { 
            Exchange(&pilestruct->space[child], &pilestruct->space[parent]); 
            parent = child; 
            child = 2 * parent; 
        } else break; 
    } 
}

代码中有几个需要注意的地方：

1. 当堆最后只有 2 个元素的时候，还要发生一次交换，因此可以取等号。
2. 左右孩子比较时需注意索引越界，不能简单取等号。
3. 交换后仍需保持大顶堆性质，因此需要下沉调整。

总结：堆的实现需要两次调整。一次是存储数据时需要满足最大堆的性质，需要做上浮调整；另一次是每次交换根节点元素和尾节点元素之后，还是需要保持大顶堆的性质，因此需要下沉调整。

优缺点分析

堆排序属于原地排序，对大规模数据排序效率较高，并且不会因为数据量增大导致性能急剧下降。但是堆排序同时也是非稳定排序，相同元素的相对顺序可能会改变。最大的挑战在于手动写一个堆，需要对指针、数组之间的逻辑、物理关系的相互转化有清晰理解。

冒泡排序

'冒泡'排序的实现思路很简单，通过重复遍历列表，比较相邻元素并看是否进行交换，将最大的元素逐渐'冒泡'到列表末尾。

核心思路

单趟的实现：通过 for 循环将第一次遍历的最大值通过比较移到末尾即可。单趟实现完后，已经排序完了一个元素，那么只需要将剩余的 n-1 个元素排序完成就行了。

复杂度分析

最好最坏都是遍历，所以时间复杂度都是 O(n^2)。空间复杂度：冒泡属于原地排序，所以为 O(1)。

代码实现

按照实现步骤，我们先实现单趟：

for (int i = 0; i < size - 1; i++) { 
    if (arr[i] > arr[i + 1]) { 
        Exchange(&arr[i], &arr[i + 1]); 
    } 
}

我们已经排序完了一个元素，下面我们再套个循环，排序剩余的 n-1 个元素：

for (int j = 1; j < size - 1; j++) { 
    for (int i = 0; i < size - 1; i++) { 
        if (arr[i] > arr[i + 1]) { 
            Exchange(&arr[i], &arr[i + 1]); 
        } 
    } 
}

代码优化

我们在优化之前不管后面的元素是否已经有序，都需要遍历，导致重复了无用的次数。优化如下：如果我们开始假设整组元素都是有序的，如果发生了交换，那么就表明需要进行下一次的循环判断，否则直接退出循环，因为遍历一遍结束之后，如果标记位未变，就表明数组已经是有序的了。

for (int j = 1; j < size - 1; j++) { 
    int flag = 0; 
    for (int i = 0; i < size - 1; i++) { 
        if (arr[i] > arr[i + 1]) { 
            Exchange(&arr[i], &arr[i + 1]); 
            flag = 1; 
        } 
    } 
    if (flag == 0) break; 
}

优缺点分析

冒泡排序是稳定的排序算法，相等的元素在排序之后依然保持原来的相对顺序。但是时间复杂度原先很高，达到了 O(n^2)，通过优化可以提高一定的算法效率，在处理数据时可以排除有序数据，表现更好。

Hoare 排序

Hoare 排序是快速排序的一种经典实现，由 Tony Hoare 于 1960 年提出，核心思想是基于分治策略，通过 Hoare 分区方法将数组分为两部分，递归地对子数组排序。

核心思路

Hoare 排序的关键在于 Hoare 分区方法，其特点是通过双指针从数组两端向中间扫描，减少冗余交换，尤其擅长处理重复的元素。整体分治思路如下：

划分：选择一个基准值（pivot），将数组分为两部分，左半部分元素 <= pivot，右半部分元素 >= pivot。 递归：对左右两部分分别递归调用 Hoare 排序。

复杂度分析

每次递归将数组分为两部分，递归深度为 log n，每层处理时间为 O(n)，因此平均时间复杂度为 O(n log n)。当每次分区完全逆序，递归深度为 n，最坏情况达到了 O(n^2)。

实现步骤

首先讲解单趟的实现：

1. 假设我们开始有一个数组，将它的最左边的值 6 作为基准值 pivot。
2. 设置这个数组的最左边的值和最右边的值分别为 left 和 right。
3. 通过循环找：左边大于等于基准值的元素（找大），右边小于等于基准值的元素（找小）。注意事项：我们的初衷是大的在右边，小的在左边，因此需要从右边开始移动，只有这样，才能保证小于基准值的移到左边来。
4. 将找到的满足条件的元素进行交换。
5. 继续循环找到满足条件的两个元素，直到两者相遇，然后交换相遇的元素与基准值元素。
6. 现在我们把数组分为了两组，以 6 为分界线，左边的数字小于等于 6，右边的数字大于等于 6。然后采用递归，两端采用分组进行 Hoare 排序。

通俗理解：理解成数，树根就是一整个数组，它会分为很多个子数组。

代码实现

按照上面的思路，我们先实现单趟，也就是先排序一个元素：

1. pivot 作为下标开始是 left 的位置，这里不要写死为 0，因为我们递归是需要灵活变化的，pivot 的开始位置应该是 left 的位置。
2. 基准值在左边，就从右边开始找；基准值在右边，就从左边开始找。
3. 大循环条件就是它们相遇停止；下面的两个子循环：首先判断大小，加上 left < right，是因为避免 left 与 right 一直走，出界。
4. 记得更新相遇位置为新的 pivot。

int pivot = left; 
while (left < right) { 
    while (left < right && arr[right] >= arr[pivot]) { 
        right--; 
    } 
    while (left < right && arr[left] <= arr[pivot]) { 
        left++; 
    } 
    Exchange(&arr[left], &arr[right]); 
} 
Exchange(&arr[left], &arr[pivot]); 
pivot = left;

上面我们已经实现了单趟，下面我们来实现递归，这里有 2 个注意要点：

1. 我们的 left-- right++ 每次排序已经移到了一起，但是我们每次递归需要从原先的位置开始。所以咱们需要记录 left right 的初始位置，每次调用函数可以初始化。
2. 我们递归需要有结束条件，这个结束条件就是 left >= right，我们循环的条件刚好是 left > right，反过来就行！

递归的实现，我们知道第一组结束之后，我们左边的分组起始地点是 left，末尾是 pivot-1；我们右边的分组初始为 pivot+1，末尾是 right。

void Hoare(int* arr, int left, int right) { 
    assert(arr); 
    if (left >= right) { 
        return; 
    } 
    int begin = left; 
    int end = right; 
    int pivot = left; 
    // 单趟逻辑同上 ...
    // 调用递归
    Hoare(arr, begin, pivot - 1); 
    Hoare(arr, pivot + 1, end); 
}

代码优化

首先看下面这个问题：每次选 pivot 都是选的数组的初始位置，然后不论有序还是无序，每次分区只能减少一个元素，导致递归深度为 O(n)，时间复杂度写死了为 O(n^2)。

优化方式：如果我们随机选择 pivot，那么可以使得最坏情况发生的概率降低，从而保证平均时间复杂度为 O(n log n)。

解释：为什么选择随机位置之后需要交换 pivot 处的数据与数据开始的位置？

1. 简化逻辑分区，我们是将基准值的位置作为分区的起点，左分区从【left，pivot-1】开始移动，寻找大于等于基准值的元素；右分区从【pivot+1，right】开始移动，找小于等于基准值的元素。
2. 避免额外判断，如果基准值保留在原位置，分区时需要处理 pivot 跨越数组界限的问题，交换到初始位置后，分区逻辑只需要关注左右 left right 的移动。

int begin = left; 
int end = right; 
int randIndex = left + rand() % (right - left + 1); 
Exchange(&arr[left], &arr[randIndex]); 
int pivot = left;

优缺点分析

Hoare 排序是一种高效的平均 O(n log n) 排序算法，原地排序，适合大数据。但是它属于不稳定排序，未优化之前可能出现 O(n^2) 的时间复杂度。总的来说优化性能更佳，处理重复元素表现更好。

总结

数据排序的精妙在于根据场景选择合适的算法。堆排序适合大规模数据且对稳定性无要求；冒泡排序易于理解但效率较低；Hoare 快排在平均性能上表现优异，是工程实践中常用的排序方案之一。随着难度的升级，后续还可以探索更多如归并排序、计数排序等高级算法。