数据结构第五节：排序

 1.常见的排序算法

插入排序：直接插入排序、希尔排序
选择排序：直接选择排序、堆排序
交换排序：冒泡排序、快速排序
归并排序：归并排序

---

排序的接口实现：

// 1. 直接插入排序
void InsertSort(int* a, int n);
// 2. 希尔排序
void ShellSort(int* a, int n);// 3. 直接选择排序
void SelectSort(int* a, int n);
// 4. 堆排序
void HeapSort(int* a, int n);// 5.冒泡排序
void BubbleSort(int* a, int n);
// 6.快速排序
void QuickSort(int* a, int left, int right);// 7.归并排序
void MergeSort(int* a, int n);

注意：以下排序的例子都是将数据进行从小到大的升序排序。

2.插入排序

2.1 直接插入排序（Insert Sort）

2.1.1 例子

初始数组： {12, 11, 13, 5, 6} 

排序过程：

轮次	已排序区间	未排序区间	操作动作
初始	[12]	[11,13,5,6]	—
1	[11,12]	[13,5,6]	插入 11 → 移动 12
2	[11,12,13]	[5,6]	插入 13 → 无需移动
3	[5,11,12,13]	[6]	插入 5 → 移动 13,12,11
4	[5,6,11,12,13]	[]	插入 6 → 移动 13,12,11

---

2.1.2 算法步骤

1. 初始化：假设第一个元素已经是已排序的序列。
2. 遍历未排序部分：从第二个元素开始，依次取出元素。
3. 插入到正确位置：将当前元素与已排序序列从后向前比较，找到合适的插入位置，将其插入。
4. 重复：直到所有元素都被插入到正确位置。

---

2.1.3 代码

// 1. 直接插入排序(最坏的时间复杂度为o（n^2）)
void InsertSort(int* a, int n)
{// 在有序数组 a[0,end] 之间，插入 a[end+1]// 外层循环控制层数for (int i = 0; i < n - 1; i++){// 内层循环控制每一层内部的插入排序int end = i;int tmp = a[end + 1];while (end >= 0){// 当 a[end+1] 小于 a[end] 时，将 a[end] 后移if (a[end] > tmp){a[end + 1] = a[end];end--;}else{break;}}// 找到了本层中插入 a[end+1] 的位置，插入a[end+1]a[end + 1] = tmp;}
}

---

2.1.4 代码关键点解析

外层循环：for (i=0; i < n-1; i++)

        控制处理 a[i+1] 元素（从第2个到最后一个元素）。

内层循环：while (end >= 0)

        从后向前比较，移动比 tmp 大的元素。

插入位置：a[end+1] = tmp

        最终空出的位置即为 tmp 的插入点。

---

2.1.5 特点

特性	说明
时间复杂度	最好 O(n)，最坏 O(n²)
空间复杂度	O(1)
稳定性	稳定（相同元素顺序不变）
适用场景	小规模数据或基本有序的数据

---

2.2 希尔排序（Shell Sort）

希尔排序是插入排序的优化版本，通过分组插入排序逐步缩小间隔（gap），最终使数组基本有序，最后进行一次完整插入排序，提升效率。

2.2.1 例子

初始数组：{9, 5, 7, 3, 1, 6, 2, 4}

       0 1  2 3 4 5 6 7 
排序过程（以 gap = 4 → 2 → 1 为例）：

Gap	分组区间（下标）	排序后子序列	合并结果
4	[0,4], [1,5], [2,6], [3,7]	[1,9], [5,6], [2,7], [3,4]	1,5,2,3,9,6,7,4
2	[0,2,4,6], [1,3,5,7]	[1,2,7,9], [3,4,5,6]	1,3,2,4,7,5,9,6
1	整体数组	完全有序	1,2,3,4,5,6,7,9

2.2.2 算法步骤

2.2.3 代码

// 2. 希尔排序(时间复杂度为o（N^1.3-N^2）)
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;// [0,end] 插入 end+gap [0, end+gap]有序  -- 间隔为gap的数据for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = tmp;}}
}

2.2.4 代码关键点解析

1. 动态调整 gap

   • gap = gap / 3 + 1 保证 gap 逐步缩小，最终为1（例如 n=8 时：8→3→2→1）。

   • 相比固定除以2，此方式更高效（经验公式，时间复杂度接近 O(n^1.3)）。

2. 分组插入排序逻辑

   • 外层循环：for (int i = 0; i < n - gap; i++)
     控制每组起始位置，遍历所有子序列。

   • 内层循环：while (end >= 0)
     在间隔为 gap 的子序列中，将 tmp 插入到正确位置，元素后移由 end -= gap 实现。

3. 边界处理

   • i < n - gap 确保 a[end + gap] 不越界。

   • end >= 0 防止访问负下标。

2.2.5 特点

特性	说明
时间复杂度	平均 O(n^1.3) ~ 最坏 O(n²)
空间复杂度	O(1)（原地排序）
稳定性	不稳定（分组可能破坏相同元素顺序）
适用场景	中等规模数据，对插入排序的优化场景

---

3.选择排序

3.1 直接选择排序（Selection Sort）

直接选择排序通过每次从未排序区间中选出最小和最大元素，分别放置到已排序区间的首尾，逐步缩小未排序范围，直到完全有序。
特点：简单但效率较低（时间复杂度 O(n²)），适合小规模数据。

---

3.1.1 例子

以数组 [5, 2, 9, 3, 6, 1, 8, 7] 为例，排序过程如下：

轮次	操作步骤	数组变化	说明
初始	未排序区间 [0,7]	5,2,9,3,6,1,8,7	初始状态
1	找到 min=1（索引5），max=9（索引2）	1,2,5,3,6,9,8,7  → 1,2,5,3,6,7,8,9	min 交换到 begin=0，max 交换到 end=7
2	未排序区间 [1,6]，找到 min=2，max=8	1,2,5,3,6,7,8,9  → 1,2,5,3,6,7,8,9	无需交换（已有序）
3	未排序区间 [2,5]，找到 min=3，max=6	1,2,3,5,6,7,8,9  → 1,2,3,5,6,7,8,9	min=3 交换到 begin=2
4	未排序区间 [3,4]，找到 min=5，max=6	1,2,3,5,6,7,8,9  → 1,2,3,5,6,7,8,9	完成排序

---

3.1.2 算法步骤

1. 初始化区间：

   begin=0，end=n-1，表示当前未排序的区间。

2. 遍历找极值：

   在 [begin, end] 区间内找到最小值 mini 和最大值 maxi。

3. 交换元素：

   将 a[mini] 与 a[begin] 交换，将 a[maxi] 与 a[end] 交换。

4. 修正 maxi：

   若 maxi == begin，说明最大值被交换到了 mini 的位置，需更新 maxi = mini。

5. 缩小区间：

   begin++，end--，重复直到 begin >= end。

---

3.1.3 代码

// 3. 直接选择排序(时间复杂度为o（n^2）)
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){// 选出最小的放在 begin// 选出最大的放在 endint mini = begin;int maxi = end;for (int i = begin; i <= end; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[begin], &a[mini]);// 修正一下maxiif (maxi == begin)maxi = mini;Swap(&a[end], &a[maxi]);begin++;end--;}
}

---

3.1.4 代码关键点解析

1. 同时找最小和最大值：

   通过一次遍历找到 mini 和 maxi，减少遍历次数（传统选择排序需两次遍历）。

2. 修正 maxi 的逻辑：

   若 maxi == begin，在交换 a[begin] 和 a[mini] 后，原最大值已被移动到 mini 的位置，需更新 maxi。示例：初始数组 [9, 1, 5]，第一次交换后 maxi 需要从 0 修正到 1。

3. 边界处理：

   while (begin < end) 确保区间有效，避免重复交换。

---

3.1.5 特点

特性	说明
时间复杂度	O(n²)（无论数据是否有序）
空间复杂度	O(1)（原地排序）
稳定性	不稳定（交换可能破坏相同元素顺序）
适用场景	小规模数据，或对稳定性无要求的场景

---

3.2 堆排序（Heap Sort）

堆排序是一种基于二叉堆数据结构的排序算法，通过构建大顶堆（升序）或小顶堆（降序），逐步将堆顶元素（极值）交换到数组末尾并调整堆，最终完成排序。

---

3.2.1 例子

初始数组：[4, 10, 3, 5, 1]
排序过程：

建堆阶段（构建大堆）

// 初始完全二叉树：4  /   \  10    3  /  \  
5    1// 向下调整后的堆10  /   \  5     3  /  \  
4    1

排序阶段

// 交换对顶的10 与最后一个数 1  ，重新调整1/   \  5     3  /  \  
4    10

---

3.2.2 算法步骤

1. 建堆：

   从最后一个非叶子节点开始，自底向上调用 AdjustDown，构建大顶堆。

2. 排序：

   将堆顶元素（最大值）与末尾元素交换，缩小堆范围。

   对剩余堆调用 AdjustDown 调整，重复直到完全有序。

---

3.2.3 代码

// 4. 堆排序(排升序建大堆)
void AdjustDown(int* a, int n, int root)
{int parent = root;int maxChild = parent * 2 + 1; // 初始化最大的孩子为左孩子while (maxChild < n){// 选出左右孩子中最大的if ( n > maxChild + 1  && a[maxChild + 1] > a[maxChild] ){maxChild++;}if (a[maxChild] > a[parent]){Swap(&a[maxChild], &a[parent]);parent = maxChild;maxChild = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{// 思路：选择排序，依次选数，从后往前排// 升序 -- 大堆// 降序 -- 小堆// 建堆 -- 向下调整建堆 - O(N)// 从最后一个叶子结点开始for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// 选数 N*logNint i = 1;while (i < n){// 将建好的大堆的第一个数（堆中最大的数）与最后一个数交换位置Swap(&a[0], &a[n - i]);// 将交换位置后的新堆重新建大堆AdjustDown(a, n - i, 0);++i;}
}

---

3.2.4 代码关键点解析

1. AdjustDown 函数

   • 参数：a 是待调整数组，n 是堆大小，root 是当前调整的父节点索引。

   • 逻辑：

     • 通过 maxChild 标记较大的子节点，若右孩子存在且更大，则更新 maxChild。

     • 若子节点大于父节点，交换并继续向下调整；否则终止循环。

     • maxChild + 1 < n，确保右孩子不越界。

2. HeapSort 函数

   • 建堆：

          从最后一个非叶子节点 (n-2)/2 开始调整（因为叶子节点无需调整）。

   • 排序：

     • 每次交换堆顶 a[0] 与当前末尾 a[n-i]，缩小堆范围至 n-i。

     • 对剩余堆重新调整，保持大顶堆性质。

---

3.2.5 特点

特性	说明
时间复杂度	建堆 O(n)，排序 O(n log n)，总体 O(n log n)
空间复杂度	O(1)（原地排序）
稳定性	不稳定（交换可能破坏相同元素顺序）
适用场景	大规模数据，对稳定性无要求的场景

---

4.交换排序

4.1 冒泡排序（Bubble Sort）

冒泡排序通过重复遍历数组，依次比较相邻元素并交换逆序对，使较大元素逐步“浮”到数组末尾。每轮遍历会确定一个最大值的最终位置，直到数组完全有序。

---

4.1.1 例子

初始数组：[5, 3, 8, 6, 2]
排序过程：

轮次	操作步骤	数组变化	说明
1	遍历比较并交换逆序对	3,5,6,2,8	确定最大值 8 的位置
2	遍历剩余未排序部分	3,5,2,6,8	确定次大值 6 的位置
3	继续遍历未排序部分	3,2,5,6,8	确定 5 的位置
4	最后一次遍历	2,3,5,6,8	完成排序

---

4.1.2 算法步骤

1. 外层循环控制轮次：

   共需 n-1 轮，每轮确定一个当前未排序部分的最大值。

2. 内层循环比较相邻元素：

   在每轮中，从索引 0 到 n-i-1 比较相邻元素，若逆序则交换。

3. 优化：提前终止：

   若某轮未发生交换，说明数组已有序，直接结束排序。

---

4.1.3 代码

// 5.冒泡排序(o（N-N^2）)
void BubbleSort(int* a, int n)
{// 控制循环层数for (int i = 0; i < n - 1; i++){// 控制每层循环比较int exchange = 0;for (int j = 1; j < n - i; j++){if (a[j - 1] > a[j]){Swap(&a[j - 1], &a[j]);exchange = 1;}}if (exchange == 0){break;}}
}

---

4.1.4 代码关键点解析

1. 外层循环条件：

   i < n - 1：最多需要 n-1 轮遍历（如 5 个元素需 4 轮）。

2. 内层循环范围：

   j < n - i：每轮遍历的未排序部分为 [0, n-i-1]，已排序部分无需处理。

3. 优化逻辑：

   exchange 标记：若某轮无交换，说明数组已有序，直接退出外层循环。

4. 稳定性：

   相等元素不会交换，因此排序是稳定的。

---

4.1.5 特点

特性	说明
时间复杂度	最好 O(n)，最坏/平均 O(n²)
空间复杂度	O(1)（原地排序）
稳定性	稳定（相同元素顺序不变）
适用场景	小规模数据或基本有序的数据

---

4.2 快速排序（Quick Sort）

快速排序是一种基于分治思想的高效排序算法，通过选定基准元素将数组划分为左右两部分，递归排序子数组，最终合并成有序序列。优化后的快速排序通常采用三数取中法选择基准，避免最坏时间复杂度。

---

4.2.1 例子

初始数组：[6, 1, 3, 9, 8, 5, 2, 7]
排序过程（以三数取中法选基准为例）：

初始数组: [6,1,3,9,8,5,2,7]  ↓ 三数取中选基准7  分区后: [5,1,3,2,7,8,9,6]  |←左递归→| |←右递归→|  左递归: [5,1,3,2] → 选基准3 → [2,1,3,5]  
右递归: [8,9,6]   → 选基准8 → [6,8,9]  最终结果: [1,2,3,5,6,7,8,9]

---

4.2.2 算法步骤

1. 三数取中法选基准：

   • 从 left、mid=(left+right)/2、right 中选择中间值的索引作为基准。

2. 分区操作：

   • 将基准交换到 left 位置，定义双指针 begin=left、end=right。

   • 右指针左移：找到第一个小于基准的元素。

   • 左指针右移：找到第一个大于基准的元素。

   • 交换左右指针元素，直到两指针相遇，将基准交换到相遇点。

3. 递归排序：

   • 对基准左右子数组递归调用快速排序。

---

4.2.3 代码

// 6.快速排序// 三数取中法选择基准索引
int GetMidIndex(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]) {if (a[mid] < a[right]) return mid;else return (a[left] > a[right]) ? left : right;}else {if (a[mid] > a[right]) return mid;else return (a[left] < a[right]) ? left : right;}
}// 分区函数
int PartQSort(int* a, int left, int right) 
{assert(a);// 三数取中法选基准，并交换到 left 位置int mid = GetMidIndex(a, left, right);Swap(&a[left], &a[mid]); // 基准置于 leftint key = a[left];int begin = left, end = right;while (begin < end) {// 右指针找小while (begin < end && a[end] >= key) end--;// 左指针找大while (begin < end && a[begin] <= key) begin++;Swap(&a[begin], &a[end]);}Swap(&a[left], &a[begin]); // 基准归位return begin;
}// 快速排序主函数
void QuickSort(int* a, int left, int right) 
{if (left >= right) return;int div = PartQSort(a, left, right);QuickSort(a, left, div - 1);QuickSort(a, div + 1, right);
}

---

4.2.4 代码关键点解析

1. 三数取中法优化：

   • GetMidIndex 选择 left、mid、right 中的中间值索引，避免极端分布（如完全逆序）导致 O(n²) 时间复杂度。

2. 分区逻辑：

   • 将基准值交换到 left 位置，确保双指针移动逻辑正确。
   • 循环结束后将基准值交换到 begin 位置。

3. 双指针移动条件：

   • 右指针先走：确保相遇点的值小于等于基准值，避免最后交换时错误。

   • 严格比较条件：a[end] >= key 和 a[begin] <= key 保证相等元素均匀分布。

---

4.2.5 特点

特性	说明
时间复杂度	平均 O(n log n)，最坏 O(n²)（可优化）
空间复杂度	O(log n)（递归栈深度）
稳定性	不稳定（交换可能破坏顺序）
适用场景	大规模数据，对缓存友好的场景

5. 归并排序（Merge Sort）

归并排序是一种基于分治思想的稳定排序算法，通过递归将数组分割为最小单元（单个元素），再两两合并有序子数组，最终得到完全有序的数组。

---

5.1 例子

初始数组：[8, 3, 5, 2, 7, 1]
排序过程：

1. 分割阶段：

   [8,3,5,2,7,1]  
   → [8,3,5] 和 [2,7,1]  
   → [8], [3,5], [2], [7,1]  
   → [8], [3], [5], [2], [7], [1]  

2. 合并阶段：

   [3,8] ←合并 [8] 和 [3]  
   [3,5,8] ←合并 [3,8] 和 [5]  
   [1,7] ←合并 [7] 和 [1]  
   [1,2,7] ←合并 [2] 和 [1,7]  
   → 最终合并 [3,5,8] 和 [1,2,7] → [1,2,3,5,7,8]  

---

5.2 算法步骤

1. 分割：

   • 递归将数组从中间位置（mid = (begin+end)/2）分割为左右子数组，直到每个子数组长度为1。

2. 合并：

   • 创建临时数组 tmp，依次比较左右子数组的元素，将较小者放入 tmp。

   • 将剩余未遍历的元素直接追加到 tmp。

   • 将 tmp 中的数据拷贝回原数组的对应区间。

---

5.3 代码

// 7.归并排序// 递归分割与合并
void _MergeSort(int* a, int begin, int end, int* tmp) {if (begin >= end) return;int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);     // 递归左半部分_MergeSort(a, mid + 1, end, tmp);   // 递归右半部分// 合并左右子数组int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] <= a[begin2]) tmp[i++] = a[begin1++];else tmp[i++] = a[begin2++];}// 处理剩余元素while (begin1 <= end1) tmp[i++] = a[begin1++];while (begin2 <= end2) tmp[i++] = a[begin2++];// 拷贝回原数组for (i = begin; i <= end; i++) a[i] = tmp[i];
}// 入口函数
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){printf("malloc fail\n");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

---

5.4 代码关键点解析

1. 递归分割：

   • 通过 mid = (begin + end) / 2 将数组分为 [begin, mid] 和 [mid+1, end]。

   • 递归终止条件 begin >= end 确保子数组长度为1时停止分割。

2. 合并逻辑：

   • 双指针遍历：begin1 和 begin2 分别指向左右子数组的起始位置，选择较小值放入 tmp。

   • 处理剩余元素：若左或右子数组有剩余元素，直接追加到 tmp。

   • 数据拷贝：将 tmp 中合并后的数据写回原数组的 [begin, end] 区间。

3. 稳定性：

   • 合并时判断 a[begin1] <= a[begin2]，保留相等元素的原始顺序。

---

5.5 特点

特性	说明
时间复杂度	O(n log n)（所有情况）
空间复杂度	O(n)（需额外临时数组）
稳定性	稳定（合并时保留相同元素顺序）
适用场景	大规模数据、需稳定性的场景

---

6.完整代码

6.1 Sort.h

#pragma once
#define _CRT_SECURE_NO_WARNING
/*排升序*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>// 插入排序：直接插入排序、希尔排序
// 选择排序：直接选择排序、堆排序
// 交换排序：冒泡排序、快速排序
// 归并排序：归并排序// 1. 直接插入排序
void InsertSort(int* a, int n);
// 2. 希尔排序
void ShellSort(int* a, int n);// 3. 直接选择排序
void SelectSort(int* a, int n);
// 4. 堆排序
void HeapSort(int* a, int n);// 5.冒泡排序
void BubbleSort(int* a, int n);
// 6.快速排序
void QuickSort(int* a, int left, int right);// 7.归并排序
void MergeSort(int* a, int n);

6.2 Sort.c

#include "Sort.h"// 1. 直接插入排序(最坏的时间复杂度为o（n^2）)
void InsertSort(int* a, int n) 
{for (int i = 0; i < n - 1; i++) {      // 外层循环：处理 a[1] 到 a[n-1]int end = i;                        // 已排序部分的末尾索引int tmp = a[end + 1];               // 当前待插入元素while (end >= 0) {                  // 内层循环：从后向前比较if (a[end] > tmp) {             // 若前一个元素更大，后移a[end + 1] = a[end];end--;}else break;}a[end + 1] = tmp;                   // 插入到正确位置}
}// 2. 希尔排序(时间复杂度为o（N^1.3-N^2）)
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1) {gap = gap / 3 + 1;  // 动态调整间隔for (int i = 0; i < n - gap; i++) {int end = i;int tmp = a[end + gap];// 间隔为gap的插入排序while (end >= 0){if (a[end] > tmp){a[end + gap] = a[end];end -= gap;}else break;}a[end + gap] = tmp;}}
}// 3. 直接选择排序(时间复杂度为o（n^2）)
void Swap(int* p1, int* p2) 
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void SelectSort(int* a, int n) 
{int begin = 0, end = n - 1;while (begin < end) {int mini = begin, maxi = end;for (int i = begin; i <= end; i++) {if (a[i] < a[mini]) mini = i;  // 找最小值if (a[i] > a[maxi]) maxi = i;  // 找最大值}Swap(&a[begin], &a[mini]);         // 交换最小值到头部if (maxi == begin) maxi = mini;    // 修正最大值位置Swap(&a[end], &a[maxi]);           // 交换最大值到尾部begin++;end--;}
}// 4. 堆排序(排升序建大堆)
// 向下调整（大堆）
void AdjustDown(int* a, int n, int root) 
{int parent = root;int maxChild = parent * 2 + 1; // 初始为左孩子while (maxChild < n) {// 选出左右孩子中较大的（需确保右孩子存在）if (maxChild + 1 < n && a[maxChild + 1] > a[maxChild]) {maxChild++;}if (a[maxChild] > a[parent]) {Swap(&a[maxChild], &a[parent]);parent = maxChild;maxChild = parent * 2 + 1;}else {break;}}
}// 堆排序
void HeapSort(int* a, int n) 
{// 建堆：从最后一个非叶子节点开始调整for (int i = (n - 1 - 1) / 2; i >= 0; --i) {AdjustDown(a, n, i);}// 排序：交换堆顶与末尾元素并调整堆int i = 1;while (i < n) {Swap(&a[0], &a[n - i]);AdjustDown(a, n - i, 0);++i;}
}// 5.冒泡排序(o（N-N^2）)
void BubbleSort(int* a, int n) 
{for (int i = 0; i < n - 1; i++) {    // 控制遍历轮次int exchange = 0;                // 标记是否发生交换for (int j = 1; j < n - i; j++) { // 遍历未排序部分if (a[j - 1] > a[j]) {       // 比较相邻元素Swap(&a[j - 1], &a[j]);exchange = 1;            // 标记有交换}}if (exchange == 0) break;        // 未交换则提前终止}
}// 6.快速排序// 三数取中法选择基准索引
int GetMidIndex(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]) {if (a[mid] < a[right]) return mid;else return (a[left] > a[right]) ? left : right;}else {if (a[mid] > a[right]) return mid;else return (a[left] < a[right]) ? left : right;}
}// 分区函数
int PartQSort(int* a, int left, int right) 
{assert(a);// 三数取中法选基准，并交换到 left 位置int mid = GetMidIndex(a, left, right);Swap(&a[left], &a[mid]); // 基准置于 leftint key = a[left];int begin = left, end = right;while (begin < end) {// 右指针找小while (begin < end && a[end] >= key) end--;// 左指针找大while (begin < end && a[begin] <= key) begin++;Swap(&a[begin], &a[end]);}Swap(&a[left], &a[begin]); // 基准归位return begin;
}// 快速排序主函数
void QuickSort(int* a, int left, int right) 
{if (left >= right) return;int div = PartQSort(a, left, right);QuickSort(a, left, div - 1);QuickSort(a, div + 1, right);
}// 7.归并排序// 递归分割与合并
void _MergeSort(int* a, int begin, int end, int* tmp) {if (begin >= end) return;int mid = (begin + end) / 2;_MergeSort(a, begin, mid, tmp);     // 递归左半部分_MergeSort(a, mid + 1, end, tmp);   // 递归右半部分// 合并左右子数组int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2) {if (a[begin1] <= a[begin2]) tmp[i++] = a[begin1++];else tmp[i++] = a[begin2++];}// 处理剩余元素while (begin1 <= end1) tmp[i++] = a[begin1++];while (begin2 <= end2) tmp[i++] = a[begin2++];// 拷贝回原数组for (i = begin; i <= end; i++) a[i] = tmp[i];
}// 入口函数
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){printf("malloc fail\n");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

6.3 Test.c

6.3.1 直接插入排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,10};InsertSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}

6.3.2 希尔排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,0};ShellSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}

 6.3.3 直接选择排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,10};SelectSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}

6.3.4 堆排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,0};HeapSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}

6.3.5 冒泡排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,10};BubbleSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}

6.3.6 快速排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,10};QuickSort(a, 0, sizeof(a) / sizeof(int) - 1); // 这里的减一是因为传参的是数组的下标for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}

6.3.7 归并排序

#include "Sort.h"void TestSort()
{int a[] = {9,7,8,6,5,1,3,2,4,10};MergeSort(a, sizeof(a) / sizeof(int));for (int i = 0; i < sizeof(a) / sizeof(int); ++i){printf("%d ", a[i]);}
}int main()
{TestSort();return 0;
}