【数据结构】-----排序的艺术画卷
目录
- 排序的概念及其运用的讲解
- 1.排序的概念
- 2.排序的应用
- 3.常见的排序算法
- 常见排序算法的实现
- 1.插入排序
- 1.直接插入排序基本思想
- 2.希尔排序( 缩小增量排序 )
- 2.选择排序
- 1.直接选择排序
- 2. 堆排序
- 3.交换排序
- 1.冒泡排序
- 2. 快速排序
- 2.快速排序非递归
- 4.归并排序
- 5.非比较排序
- ❤️总结
排序的概念及其运用的讲解
1.排序的概念
排序：将记录按关键字大小递增或递减排列。
稳定性：相同关键字记录排序后相对次序不变，变了则不稳定，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据全在内存的排序。
外部排序：因数据多需在内外存间移动数据。
2.排序的应用
在数据处理领域，对数据记录按特定关键字排序，能提高数据检索和分析效率。
在成绩管理方面，可按分数对学生成绩排序，便于统计和分析成绩分布等情况。
在商业中，可按价格对商品排序，方便顾客比较。
3.常见的排序算法
常见排序算法有冒泡、选择、插入、快速、归并排序等。
冒泡排序通过相邻元素比较交换排序。
选择排序每次选最小或最大元素放已排序末尾。
插入排序将元素插入已排序部分合适位置。
快速排序选基准元素划分左右再递归排序。
归并排序先分离子序列排序再合并 。
常见排序算法的实现
1.插入排序
1.直接插入排序基本思想
是将待排序记录依据关键码（元素）值大小，逐个插入到已排好序的序列中，直至全部记录插入完毕，像玩扑克时整理牌序，形成新有序序列。
直接插入排序时，在插入第 i（i≥1）个元素时，将其排序码与前面已排序的元素排序码比较，找到合适位置插入，原位置元素依次后移 。
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i-1;int tmp = a[i];// 将tmp插入到[0,end]区间中，保持有序while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}
代码：从数组第 2 个元素（下标 1）开始，把当前元素当成 待插入的新牌，和前面已排序区间（下标 0 到 i-1） 比较，找到它该插入的位置，让已排序区间始终有序，直到遍历完所有元素。
i：循环变量，从 1 开始遍历数组，代表当前要处理的 新元素下标（把 a[i] 插入前面的有序区间）。
end：指向已排序区间的末尾下标（初始是 i-1，也就是前一个元素），用来逐个往前找 “插入位置”。
tmp：暂存当前要插入的元素 a[i]，避免后移元素时被覆盖。
精髓：end 的 动态收缩
end 不仅标记了 已排序区间末尾，还在循环里一边往前找位置、一边缩小范围 。每次发现 tmp 更小，就让 a[end] 后移，end 减一继续比较，直到找到 tmp 能 站住的位置。这种用下标动态调整的方式，既完成了 元素后移，又找到了插入点，把 找位置 和 挪元素 融合在一起，是插入排序的巧妙之处。
直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
2.希尔排序( 缩小增量排序 )
希尔排序法，别称缩小增量法 。其核心思想为：先选定一个整数作为增量，依据该增量，把待排序序列里的元素划分成若干组，规则是元素下标距离为该增量的归为同一组；接着，对每组内的元素开展排序操作（一般用直接插入排序 ）。之后，逐步缩小增量值，重复分组与组内排序流程。当增量最终变为 1 时，所有元素处于同一组，再进行一次排序，就能让整个序列有序 。
void ShellSort(int* a, int n)
{// gap > 1 预排序// gap == 1 直接插入排序int gap = n;while (gap > 1){//gap /= 2;gap = gap / 3 + 1;//让 gap 逐渐缩小，gap / 3 + 1 是一种经典的 “缩小策略”（比简单的 gap /= 2 更科学，能让 gap 更合理地逼近 1 ）for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[i + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}
}
代码：简单来说，就是直接插入排序的升级版，通过分组，进行每组的直接插入排序，不过它不是将数组里面的元素直接把数放在一起，而是通过下标来确定组。你可以去类比直接插入排序的代码进行理解。
精髓：gap 的作用 :
大 gap 时，元素移动 跨度大，能快速把整体无序的数组变得 大概有序；小 gap 时，数组已经接近有序，插入排序的效率会很高（插入排序对 “近乎有序” 的数组，时间复杂度接近 O(n) ）。
希尔排序的特性总结：
- 希尔排序是对直接插入排序的优化。
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。
- 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定。
- 稳定性：不稳定。
2.选择排序
从待排序序列中，逐轮选出最小（或最大）元素，将其放到序列 起始端（或末尾端），逐步缩小待排序范围，直到所有元素有序。
简单说：每一轮找一个 最值，放到对应位置，让有序区间从两端向中间收缩。
1.直接选择排序
1.选最值：在当前未排序区间 array[i]~array[n-1] 里，找出关键码最大 / 小的元素（升序选最小，降序选最大 ）。
2.交换归位：若最值元素不在区间的== 端点位置==升序时是 array[i]，降序时是 array[n-1] ），就和端点元素交换，让最值元素归位到有序区间。
3.缩小区间：处理完当前区间后，剩余未排序区间缩小为 array[i]~array[n-2]（升序，下一轮从 i+1 开始 ）或 array[i+1]~array[n-1]（降序 ），重复选最值 → 交换，直到区间只剩 1 个元素，排序结束。
简单说：每轮固定一个最值元素的位置，逐步缩小未排序范围，最终让数组全局有序 ，像 逐个确定冠军（最值）位置的比赛流程。
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void SelectSort(int* a, int n)
{int left = 0, right = n - 1;while (left < right){int mini = left, maxi = left;for (int i = left + 1; i <= right; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[left], &a[mini]);// 如果left和maxi重叠，交换后修正一下if (left == maxi){maxi = mini;}Swap(&a[right], &a[maxi]);++left;--right;}
}
代码解释：这个是直接优化版代码（双向选择）通过maxi与mini两个变量记录由循环再数组里面找最大的和最小的，再进行交换，有可能会出现第一个元素是最大的，但进行交换后第一个变了，我们这时就要将maxi修改了等于mini了。
直接选择排序的特性总结：
- 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：不稳定
2. 堆排序
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。
// 左右子树都是大堆/小堆
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 选出左右孩子中大的那一个if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 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);}// 自己先实现 -- O(N*logN)int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}
直接选择排序的特性总结：
- 堆排序使用堆来选数，效率就高了很多。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)
- 稳定性：不稳定
3.交换排序
通过比较两个记录的键值，若需调整顺序，则交换它们在序列中的位置；排序过程中，让键值大的记录逐步移向序列尾部，键值小的移向序列前部 ，以此实现整体有序。
核心就是 “比较判需，交换调位，大后小前”，典型算法如冒泡排序、快速排序 。
1.冒泡排序
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){bool exchange = false;for (int i = 1; i < n-j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = true;}}if (exchange == false){break;}}
}
代码：简单来说，冒泡排序就是通过相邻两个元素进行比较，大的往后，一次一次找最大的放后面。
冒泡排序的特性总结：
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)
- 稳定性：稳定
2. 快速排序
快速排序由 Hoare 于 1962 年提出，是基于交换的排序算法，核心可总结为：
1.基本思想：选基准值，将序列划分为 左小、右大两个子序列，递归处理子序列，直至整体有序。
2.递归关联：递归实现框架类似二叉树前序遍历（先处理基准划分，再递归子序列 ），借助前序遍历思路可辅助写递归逻辑，重点是掌握基准划分数据的方式 。
将区间按照基准值划分为左右两半部分的常见方式有：
- hoare版本
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}
// Hoare
int PartSort1(int* a, int left, int right)
{// 三数取中int midi = GetMidNumi(a, left, right);if (midi != left)Swap(&a[midi], &a[left]);int keyi = left;while (left < right){// 右边找小while (left < right && a[right] >= a[keyi])--right;// 左边找大while (left < right && a[left] <= a[keyi])++left;Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);keyi = left;return keyi;
}
这个方法是通过下标左边找比基准小的，右边找比基准大的，然后交换，直到左边的下标与右边的下标相遇，基准与左边下标交换。
- 挖坑法
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}
// 挖坑法
int PartSort2(int* a, int left, int right)
{// 三数取中int midi = GetMidNumi(a, left, right);if (midi != left)Swap(&a[midi], &a[left]);// 21:10继续int key = a[left];int hole = left;while (left < right){// 右边找小while (left < right && a[right] >= key)--right;a[hole] = a[right];hole = right;// 左边找大while (left < right && a[left] <= key)++left;a[hole] = a[left];hole = left;}a[hole] = key;return hole;
}
挖坑法，简单来说还是以基准找大小的原理，他是先将基准作为坑位，然后右边的下标找比基准的小的元素进行交换，然后再让右边的下标作为坑位，然后让左边的下标找比基准大的，这样循环就行。
3. 前后指针版本
int GetMidNumi(int* a, int left, int right)
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right]){return mid;}else if (a[left] > a[right]){return left;}else{return right;}}else // a[left] > a[mid]{if (a[mid] > a[right]){return mid;}else if (a[left] < a[right]){return left;}else{return right;}}
}
// 前后指针法
int PartSort3(int* a, int left, int right)
{// 三数取中int midi = GetMidNumi(a, left, right);if (midi != left)Swap(&a[midi], &a[left]);int keyi = left;int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[cur], &a[prev]);++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;return keyi;
}
前后指针法：是用前指针和后指针，开始前指针后指针都再一处，然后让前指针开始遍历，前指针找到比基准小的就后指针走，反之跟着一起停下，如果前指针找到比基准小的就跟后指针的数据交换，之后基准与后指针交换。
这些都是快速排序优化
三数取中法选key
递归到小的子区间时，可以考虑使用插入排序
2.快速排序非递归
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = PartSort3(a, begin, end);// [begin,keyi-1] keyi [keyi+1, end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi+1);}if (begin < keyi-1){STPush(&st, keyi-1);STPush(&st, begin);}}STDestroy(&st);
}
快速排序的特性总结：
快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)
4.归并排序
归并排序核心思想：基于分治法，先将序列不断 拆分为子序列，使子序列自身有序，再通过归并操作（如二路归并，合并两个有序子序列为一个有序序列 ），让子序列段间有序，最终得到完全有序的序列，是分治思想在排序算法中的典型应用。
void _MergeSort(int* a, int begin, int end, int* tmp)
{if (begin >= end)return;int mid = (begin + end) / 2;// [begin, mid] [mid+1,end]，子区间递归排序_MergeSort(a, begin, mid, tmp);_MergeSort(a, mid+1, end, tmp);// [begin, mid] [mid+1,end]归并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++];}memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\n");return;}_MergeSort(a, 0, n - 1, tmp);free(tmp);
}
//非递归
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail\n");return;}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){// [begin1,end1][begin2, end2]int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//printf("[%d,%d][%d,%d] ", begin1, end1,begin2,end2);if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}printf("[%d,%d][%d,%d] ", begin1, end1, begin2, end2);int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}// 归并一部门拷贝一部分memcpy(a+i, tmp+i, sizeof(int) *(end2-i+1));}printf("\n");gap *= 2;}free(tmp);
}
一、分：拆分数组
选数组中间位置，把数组砍成 左半段 和 右半段
对左半段、右半段，重复 “砍两半” 操作，一直拆到 每个子数组只剩 1 个元素（因为 1 个元素的数组天生有序）
二、治：合并有序数组
从最小的有序子数组（长度 1）开始，两两 合并成更大的有序数组
比如 [3] 和 [1] 合并成 [1,3]；[2] 和 [4] 合并成 [2,4]
合并时用 临时数组 辅助：对比两个子数组的元素，按从小到大依次放进临时数组，最后再把临时数组内容拷贝回原数组
三、重复合并，直到整个数组合并完成
小的有序数组不断合并，像搭积木一样，最终合并成一个 完整的有序数组，排序就完成啦
归并排序的特性总结：
- 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
- 时间复杂度：O(N*logN)
- 空间复杂度：O(N)
- 稳定性：稳定
5.非比较排序
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：
- 统计相同元素出现次数
- 根据统计的结果将序列回收到原来的序列中
void CountSort(int* a, int n)
{int max = a[0], min = a[0];for (int i = 1; i < n; ++i){if (a[i] > max){max = a[i];}if (a[i] < min){min = a[i];}}int range = max - min + 1;int* countA = (int*)malloc(sizeof(int) * range);if (countA == NULL){perror("malloc fail\n");return;}memset(countA, 0, sizeof(int) * range);// 计数for (int i = 0; i < n; i++){countA[a[i] - min]++;}// 排序int j = 0;for (int i = 0; i < range; i++){while (countA[i]--){a[j++] = i + min;}}free(countA);
}
- 找范围：确定统计的 边界
遍历数组，找到 最大值 max 和 最小值 min
比如数组是 [3, 1, 2, 3, 0]，min=0，max=3 - 建 计数桶：统计每个数出现的次数
创建一个 长度为 max - min + 1 的计数数组 count
遍历原数组，把每个数对应到 count 的位置（用 数 - min 当索引），统计出现次数
比如原数组 3，对应 count[3-0]（即 count[3]），次数 +1
遍历完后，count 里存的是 [1,1,1,2]（对应 0 出现 1 次、1 出现 1 次… 3 出现 2 次 ） - 回填数组：按统计结果恢复有序数组
遍历 count，根据每个位置的计数，把数 填回 原数组
比如 count[0]=1 → 填 0；count[1]=1 → 填 1；count[2]=1 → 填 2；count[3]=2 → 填两次 3
填完后原数组变成 [0,1,2,3,3]，排序完成
计数排序的特性总结：
3. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
4. 时间复杂度：O(MAX(N,范围))
5. 空间复杂度：O(范围
6. 4. 稳定性：稳定
❤️总结
文字的旅程暂告段落，感谢你温柔相伴。若文中有疏漏，盼你轻声指正，那是成长的微光。倘若这些字句，曾为你拂去些许迷茫，不妨留个赞，让温暖延续，也欢迎你常来，共赴文字的山海，聆听心灵的回响❤️