seo网站排名优化方案开发一个app多少钱
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 算法步骤
- 初始化：假设第一个元素已经是已排序的序列。
- 遍历未排序部分：从第二个元素开始，依次取出元素。
- 插入到正确位置：将当前元素与已排序序列从后向前比较，找到合适的插入位置，将其插入。
- 重复：直到所有元素都被插入到正确位置。
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 代码关键点解析
-
动态调整
gap-
gap = gap / 3 + 1保证gap逐步缩小，最终为1（例如n=8时：8→3→2→1）。 -
相比固定除以2，此方式更高效（经验公式，时间复杂度接近 O(n^1.3)）。
-
-
分组插入排序逻辑
-
外层循环：
for (int i = 0; i < n - gap; i++)
控制每组起始位置，遍历所有子序列。 -
内层循环：
while (end >= 0)
在间隔为gap的子序列中，将tmp插入到正确位置，元素后移由end -= gap实现。
-
-
边界处理
-
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） |
→ | min 交换到 begin=0，max 交换到 end=7 |
| 2 | 未排序区间 [1,6]，找到 min=2，max=8 |
→ | 无需交换（已有序） |
| 3 | 未排序区间 [2,5]，找到 min=3，max=6 |
→ | min=3 交换到 begin=2 |
| 4 | 未排序区间 [3,4]，找到 min=5，max=6 |
→ | 完成排序 |
3.1.2 算法步骤
-
初始化区间：
begin=0，end=n-1，表示当前未排序的区间。 -
遍历找极值：
在[begin, end]区间内找到最小值mini和最大值maxi。 -
交换元素：
将a[mini]与a[begin]交换，将a[maxi]与a[end]交换。 -
修正
若maxi：maxi == begin，说明最大值被交换到了mini的位置，需更新maxi = mini。 -
缩小区间：
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 代码关键点解析
-
同时找最小和最大值：
通过一次遍历找到mini和maxi，减少遍历次数（传统选择排序需两次遍历）。 -
修正
maxi的逻辑：若
maxi == begin，在交换a[begin]和a[mini]后，原最大值已被移动到mini的位置，需更新maxi。示例：初始数组[9, 1, 5]，第一次交换后maxi需要从0修正到1。 -
边界处理：
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 103.2.2 算法步骤
-
建堆：
从最后一个非叶子节点开始，自底向上调用AdjustDown，构建大顶堆。 -
排序：
将堆顶元素（最大值）与末尾元素交换，缩小堆范围。
对剩余堆调用
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 代码关键点解析
-
AdjustDown 函数
-
参数：
a是待调整数组，n是堆大小，root是当前调整的父节点索引。 -
逻辑：
-
通过
maxChild标记较大的子节点，若右孩子存在且更大，则更新maxChild。 -
若子节点大于父节点，交换并继续向下调整；否则终止循环。
-
maxChild + 1 < n，确保右孩子不越界。
-
-
-
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 算法步骤
-
外层循环控制轮次：
共需n-1轮，每轮确定一个当前未排序部分的最大值。 -
内层循环比较相邻元素：
在每轮中，从索引0到n-i-1比较相邻元素，若逆序则交换。 -
优化：提前终止：
若某轮未发生交换，说明数组已有序，直接结束排序。
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 代码关键点解析
-
外层循环条件：
i < n - 1：最多需要n-1轮遍历（如5个元素需4轮）。 -
内层循环范围：
j < n - i：每轮遍历的未排序部分为[0, n-i-1]，已排序部分无需处理。 -
优化逻辑：
exchange标记：若某轮无交换，说明数组已有序，直接退出外层循环。 -
稳定性：
相等元素不会交换，因此排序是稳定的。
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 算法步骤
-
三数取中法选基准：
-
从
left、mid=(left+right)/2、right中选择中间值的索引作为基准。
-
-
分区操作：
-
将基准交换到
left位置，定义双指针begin=left、end=right。 -
右指针左移：找到第一个小于基准的元素。
-
左指针右移：找到第一个大于基准的元素。
-
交换左右指针元素，直到两指针相遇，将基准交换到相遇点。
-
-
递归排序：
-
对基准左右子数组递归调用快速排序。
-
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 代码关键点解析
-
三数取中法优化：
-
GetMidIndex选择left、mid、right中的中间值索引，避免极端分布（如完全逆序）导致 O(n²) 时间复杂度。
-
-
分区逻辑：
- 将基准值交换到
left位置，确保双指针移动逻辑正确。 - 循环结束后将基准值交换到
begin位置。
- 将基准值交换到
-
双指针移动条件：
-
右指针先走：确保相遇点的值小于等于基准值，避免最后交换时错误。
-
严格比较条件：
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]
排序过程：
-
分割阶段：
[8,3,5,2,7,1] → [8,3,5] 和 [2,7,1] → [8], [3,5], [2], [7,1] → [8], [3], [5], [2], [7], [1] -
合并阶段：
[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 算法步骤
-
分割：
-
递归将数组从中间位置（
mid = (begin+end)/2）分割为左右子数组，直到每个子数组长度为1。
-
-
合并：
-
创建临时数组
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 代码关键点解析
-
递归分割：
-
通过
mid = (begin + end) / 2将数组分为[begin, mid]和[mid+1, end]。 -
递归终止条件
begin >= end确保子数组长度为1时停止分割。
-
-
合并逻辑：
-
双指针遍历：
begin1和begin2分别指向左右子数组的起始位置，选择较小值放入tmp。 -
处理剩余元素：若左或右子数组有剩余元素，直接追加到
tmp。 -
数据拷贝：将
tmp中合并后的数据写回原数组的[begin, end]区间。
-
-
稳定性：
-
合并时判断
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;
}
