数据结构中的高级排序算法

希尔排序

你可以将希尔排序理解成——先通过几次分组的、较小的组间插入排序将原数组变得有序，最后再进行一次序列基本有序的完整插入排序。

#include <stdio.h>#define ARR_LEN(arr) (sizeof(arr) / sizeof(arr[0]))void print_arr(int arr[], int len) {for (int i = 0; i < len; i++) {printf("%d ", arr[i]);}printf("\n");
}// 希尔排序: 缩小增量排序, 其实就是多人摸牌, 逐渐减少摸牌人数
// 希尔排序中, 增量序列的设计非常重要,这里采取简单的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存在,所以需要减去gapif (arr[j] > tmp) { // 注意:不能加=,加了就不稳定了arr[j + gap] = arr[j];  // 将旧手牌中大于新手牌的所有牌都向后移}else{break;  // 只要发现一张旧手牌更小或相等, 就说明已经找到新手牌的插入位置了}}arr[j + gap] = tmp;}print_arr(arr, len);    // 每一轮希尔排序后查看数组排序结果gap >>= 1; // 每一轮希尔排序,增量都减半}
}int main(void) {int arr[] = { 16, 1, 45, 23, 99, 2, 18, 67, 42, 10 };int arr_len = ARR_LEN(arr);shell_sort(arr, arr_len);return 0;
}

时间复杂度：

希尔排序的时间复杂度，和选择的增量序列有密切的关联：

若使用希尔本人提出的减半序列，时间复杂度通常会小于O(n2)，但在最坏情况也会接近O(n2)

空间复杂度分析：

希尔排序是一种原地排序算法，不需要占用额外内存空间。空间复杂度是O(1)

稳定性分析：

希尔排序显然不是一种稳定的排序算法，因为它先分组再插入排序的方式，使得相同元素可能会由于分组不同改变位置。很明显这不是稳定的排序算法。

 归并排序

归并排序的分治策略思路大体上如下：

1. 分解大问题：将一个大数组分解成两个或更多的子数组，直到每个子数组足够小，通常是直到每个子数组只包含一个元素或者是空数组。
2. 解决子问题：数组小到只有一个元素或者没有元素，那自然是"有序数组"，所以这些子问题可以视为被解决了。
3. 合并：归并排序的核心在于合并步骤，也可以叫"归并"操作，它会将两个有序的子数组合并成一个大的有序数组。这个过程通常需要反复比较元素，比较复杂。

 递归分解：

递归分解的过程会不停地将大数组分解成两个小的子数组，这个分解的过程会根据大数组的左右界限求一个中间索引，然后将大数组尽量等分为两份。所以，递归分解的函数，至少需要三个参数：

1. 递归分解的数组arr
2. 数组分解的左下标left
3. 数组分解的右下标right

此递归分解的函数会将arr数组的[left, right]区间分解成两个小数组。

于是递归的出口就很明显了是：left >= right，这表示子数组缩小到只包含一个元素或没有元素时，递归将停止。

在计算中索引时，我们将采用一种优化的方案：

1. 一般情况下，可以直接使用 "(left + right) >> 1" 来直接求中间索引。
2. 但C语言中int类型可能只占2个字节，此时int类型取值范围较小，上面的表达式可能会出现数据溢出失真。为避免这种情况发生，我们可以采用表达式"left + (right - left >> 1)"去求中间索引。

合并 操作：

1. 从左到右轮流比较待合并子数组中的元素，把比较过程中的较小元素存入临时数组中，直到某个子数组元素为空。
2. 然后再将存在剩余元素的子数组中的所有元素，轮流放入临时数组中。
3. 最后把临时数组中的元素，复制回原数组。

注：临时数组的长度和原数组是一致的，且合并过程共有同一套下标索引。

#include <stdio.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);
}// 测试归并排序
int main() {int arr[] = { 8, 3, 2, 6, 9, 7, 1, 0, 4, 5 };int arr_size = ARR_SIZE(arr);merge_sort(arr, arr_size);return 0;
}

时间复杂度：

无论原始数组处在什么状态，归并排序都会按照既定步骤分解、合并。所以在最好，最坏，平均情况下，归并排序的时间复杂度都是一样的，都是O(nlogn)。

归并排序的时间复杂度分析需要考虑它的两个主要操作，分解和合并：

1. 分解过程也就是递归调用的过程，这个过程大概分解了log2n次（每次都将数组折半，也就是递归的深度）
2. 在合并的过程中，需要遍历并比较子数组的元素，然后将它们按顺序复制回原数组。每次合并操作的时间复杂度都是O(n)，因为它涉及到整个数组的遍历。合并的次数和分解的次数是一样的，都是log2n次，所以对于合并操作，总的时间复杂度是O(nlogn)

 空间复杂度：

归并排序显然不是一个原地算法。它需要额外的内存空间：

1. 需要一个与原始数组大小相同的，长度是n的辅助数组来进行合并操作。
2. 递归调用，占用额外的栈空间。因为每次递归调用都会将数组分为两个大致相等的部分，所以每次都将问题的规模减半。递归深度大致是log2n。

所以空间复杂度是O(n)。

稳定性：

归并排序是稳定的排序算法。这是因为如果两个元素相等，归并排序不会改变它们的相对顺序。

快速排序

单向分区

所谓单向分区，指的是快速排序算法在分区的过程中，元素比较和交换的操作是单向进行的，也就是从数组的一端进行到另外一端。

单向分区快速排序算法，具体而言，它的思路是：

1. 选择一个基准值（pivot），可以是随机选择，也可以是直接选首尾元素。选定基准值后，一般会将pivot交换到数组末尾，这样做可以简化分区操作。
2. 设置一个索引(比如叫idx)来追踪小于基准值的元素应该插入的位置，一开始idx索引指向数组的首元素。

3. 遍历数组进行分区操作：

   1. 从数组首元素开始遍历整个数组
   2. 如果元素小于基准值，则将该元素与idx位置的元素交换，idx索引加1。
   3. 如果元素大于或等于基准值，则不做任何操作，继续遍历下一个元素。

4. 当遍历到最后一个元素，也就是pivot时，遍历结束：

   1. 最后将pivot元素和此时idx索引元素进行交换，完成这一轮分区操作。
   2. 此时pivot左侧的元素一定都是小于基准值的。
   3. pivot右侧的元素一定都是大于等于基准值的。
5. 对基准值左右两边的子数组递归地执行以上步骤，直到每个子数组的大小减少到1或0，此时数组就被完全排序了。

 

#include <stdio.h>
#include <time.h>
#include <stdlib.h>#define ARR_SIZE(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 left, int right) {for (int i = left; i <= right; i++) {printf("%d ", arr[i]);}printf("\n");
}// 分区核心操作实现,返回一轮快排选择的pivot的下标
int partition(int arr[], int left, int right) {// 1.随机选择一个基准值,然后把它先放到数组末尾int pivot_idx = left + rand() % (right - left + 1); // 得到一个[left, right]范围内的随机索引int pivot = arr[pivot_idx];SWAP(arr, pivot_idx, right);// 2.设置一个partition_idx索引,指示小于pivot的元素应该插入的位置// 同时该索引最终表示分区的界限索引,所以命名为partition_idxint partition_idx = left;// 3.遍历整个数组,当元素小于pivot时,将它和partition_idx位置元素交换,partition_idx加1// 希望遍历结束时，i指向数组末尾的pivot，所以i < rightfor (int i = left; i < right; i++) {if (arr[i] < pivot) {SWAP(arr, i, partition_idx);partition_idx++;}}// 4.遍历结束后,将pivot元素(最后一个元素)交换到partition_idx位置SWAP(arr, right, partition_idx);printf("此一轮分区操作,选择的pivot是: %d\n分区结束后的数组是: ", pivot);print_arr(arr, left, right);// 5.返回基准值的位置索引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);
}int main(void) {// 测试单向分区快速排序int arr[] = { 8,3,2,6,9,5 };int len = ARR_SIZE(arr);quick_sort_one_way(arr, len);return 0;
}

时间复杂度分析：平均时间复杂度就是O(nlogn)

空间复杂度分析：在最佳和平均情况下，递归深度大约是log2n，空间复杂度是O(logn)。但如果是在最坏情况下，递归深度接近n，此时空间复杂度为O(n)

稳定性：快速排序是一种不稳定的排序算法

双向分区

比起单向分区，双向分区是更常用的快排分区策略，一般而言当我们提起快速排序，指的都是双向分区策略的快速排序。

所谓双向分区，指的是在分区过程中，元素比较和交换操作的方向是，同时从数组的两端向中间逼近的。

双向分区快速排序算法，具体而言，它的思路是：

1. 选择基准值pivot，基准值可以是一个随机元素，也可以选择一个固定元素。然后将基准值元素和首元素交换，这样做的目的是为了将交换元素操作优化成一个赋值操作。并且要将基准值存储起来。

2. 设置两个索引 low 和 high ：

   1. 索引 low 一开始指向数组首元素，它的含义是指示小于基准值的元素应该置于的位置。
   2. 索引 high 一开始指向数组尾元素，它的含义是指示大于等于基准值的元素应该置于的位置。

3. 率先移动索引high，它从尾元素开始向左移动，目标是找到第一个小于基准值的元素：

   1. 找到该元素后，直接将该元素赋值给low索引位置，也就是覆盖掉基准值。
   2. 赋值结束后，low索引和high索引都不需要移动。

4. 然后向右移动索引 low，找到第一个大于等于基准值的元素：

   1. 找到该元素后，直接将该元素赋值给high索引位置
   2. 赋值结束后，low索引和high索引都不需要移动。
5. 重复过程3和4，直到索引high和low相遇。最后将基准值放入它们相遇的位置。
6. 于是分区就结束了，基准值到达了排序的最终位置，基准值左边都是小于基准值的元素，右边都是大于等于基准值的元素。
7. 对基准值左右两边的子数组递归地执行以上步骤，直到每个子数组的大小减少到1或0，此时数组就被完全排序了。

#include <stdio.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");
}// 快速排序的核心操作: 双向分区, 也就是确定pivot的最终位置
// 挑选一个基准值,通过双向分区操作,决定最终的位置,最终位置就是基准值排好序的位置
static int partition(int arr[], int left, int right) {// 1.为了简化实现,直接挑选首元素为基准值(因为基准值要交换到开头,所以直接挑选首元素作为基准值,可以减少一步交换)int pivot = arr[left];// 2.初始化两个索引low和high,分别指向数组两端int low = left, high = right;// 3.循环遍历这个数组区间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;printf("此一轮分区操作选择的pivot = %d\n", pivot);print_arr(arr, left, right);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(nlogn)

空间复杂度分析：在最佳和平均情况下，递归深度大约是log2n，空间复杂度是O(logn)。但如果是在最坏情况下，递归深度接近n，此时空间复杂度为O(n)

稳定性：快速排序是一种不稳定的排序算法

 堆排序

上述堆排序算法在具体实现时，要分为两个步骤：

1. 将待排序的原始数组，在逻辑上进行第一次堆化的操作
2. 将大顶堆的根结点元素移到数组末尾，交换首尾元素，逻辑上堆大小减1，以新的根结点进行堆化操作。

这两个步骤中的核心操作逻辑都是——堆化。

堆化的过程，其实就是自父结点开始，向下检查左右子树和这个父结点大小关系的过程：

1. 如果左子树大于父结点，那么交换左子树和父结点
2. 如果右子树大于父结点，那么交换右子树和父结点
3. 如果出现了交换，那么被交换的左子树或右子树就要重新进行堆化操作。
4. 如果根结点已经是最大值(相等的最大值也算)，没有交换，那么堆化结束。

 

#include <stdio.h>
#define ARR_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define SWAP_ELEMENT(arr, i, j){    \int tmp = arr[i];       \arr[i] = arr[j];        \arr[j] = tmp;       \
}void print_arr(int arr[], int n) {for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");
}// 该函数会把以root_idx索引元素为根结点的
// 逻辑长度是tree_len的一棵完全二叉树arr，构建成一个大顶堆
static void heapify(int arr[], int tree_len, int root_idx) {/*堆化操作必然是需要循环来完成的如果对于某个循环,既不清楚循环的次数,循环结束的条件也不太好找到那么可以先写一个死循环, 然后具体到代码中再用break,return等结束循环*/while (1) {// 根据根节点的下标,先计算出左右子树的下标int lchild_idx = (root_idx << 1) + 1;int rchild_idx = (root_idx << 1) + 2;int max_idx = root_idx;     // 先假设根节点就是最大值if (lchild_idx < tree_len && arr[lchild_idx] > arr[max_idx]) {// 如果左子树存在且左子树值比假设的最大值要大,那么左子树下标就是新的最大值下标max_idx = lchild_idx;}if (rchild_idx < tree_len && arr[rchild_idx] > arr[max_idx]) {// 如果右子树存在且右子树值比假设的最大值要大,那么右子树下标就是新的最大值下标max_idx = rchild_idx;}if (max_idx != root_idx) {// 交换左右子树较大者和根节点的值SWAP_ELEMENT(arr, max_idx, root_idx);// 此时max_idx结点的值就是以前根节点的值,此时由于数据发生了改变,max_idx结点的树就不一定是大顶堆了// 所以接下来要以max_idx为根节点,继续构建大顶堆root_idx = max_idx;}else {// 不需要交换了,说明以root_idx为根节点的树已经是大顶堆了break;}}
}// 第一次将数组构建成大顶堆，自下而上将每一个非叶子结点构建大顶堆
static void first_build_heap(int arr[], int len) {int last_idx = len - 2 >> 1;    //最后一个非叶子结点的下标for (int i = last_idx; i >= 0; i--) {heapify(arr, len, i);}printf("第一次堆化后数组为: \n");print_arr(arr, len);
}
void heap_sort(int arr[], int len) {// 1.将原arr数组构建成大顶堆，第一次构建大顶堆first_build_heap(arr, len);// 2.反复移除根结点元素，然后再重建大顶堆int heap_len = len; // 堆逻辑上的长度，一开始就是数组长度，随着反复移除重建大顶堆，这个长度会一直减少1while (heap_len > 1) {  // 只要堆还有两个元素就需要继续构建移除SWAP_ELEMENT(arr, 0, heap_len - 1);heap_len--;/*堆排序的核心操作：重新构建大顶堆*/heapify(arr, heap_len, 0);  // 堆排序核心操作：堆化printf("重新构建大顶堆后: \n");print_arr(arr, heap_len);}
}int main(void) {int arr[] = { 4, 10, 3, 5, 1 };int len = ARR_SIZE(arr);heap_sort(arr, len);return 0;
}

时间复杂度：堆排序在任何情况下，时间复杂度都是O(nlogn)。

空间复杂度：堆排序显然是一个原地算法，不需要任何额外内存空间，空间复杂度是O(1)

稳定性：堆排序也是一种不稳定的排序算法，在堆化的过程需要交换父节点和左右子树结点，这个过程非常容易出现改变相同元素位置的情况。

几种排序算法的应用场景

1. 选择排序：建议任何情况都不用。
2. 冒泡排序：建议任何情况都不用。
3. 插入排序：适合小数据集，尤其当数据已基本有序时非常好用。
4. 希尔排序：一般不使用。
5. 归并排序：大数据集的场景下，需要稳定排序算法时使用。
6. 快速排序：大数据集的场景下，通用的排序算法，效率高，但不稳定。
7. 堆排序：大数据集的场景下，性能均衡的不稳定排序算法，优点是不占用额外内存空间。