当前位置： 首页 > ops >正文

C数据结构：排序

ops 2025/9/1 8:03:14

C数据结构：排序

1.插入排序
2.希尔排序
3.选择排序
4.快速排序
5.归并排序
6.计数排序
7.排序总结

1.插入排序

数组arr的长度为n，假定下标[0,end]对应的元素有序，把arr[end+1]与下标为[0,end]对应的元素比较，从而找到合适位置插入arr[end+1]，使[0,end+1]有序。

void InsertSort(int* a, int n)//插入排序
{for (int i = 0;i < n - 1;i++){int end = i;int t = a[end + 1];while (end >= 0){if (t < a[end]){a[end + 1] = a[end];--end;}elsebreak;}a[end + 1] = t;}
}

例如数组arr[]={2,1,1,3}。
在这里插入图片描述
进入while循环，比较t与arr[end]的大小，执行if语句，把arr[end]的值覆盖到arr[end+1]，end再自减1。
在这里插入图片描述
由于end<0，跳出while循环，把t赋值给此时的arr[end+1]。
在这里插入图片描述
进入下一次for循环，i变为1。
在这里插入图片描述
此时t又小于arr[end]，再把arr[end]的值覆盖到arr[end]。
在这里插入图片描述
此时，t=arr[end]，执行break，跳出while循环，再把t的值赋给arr[end+1]。
在这里插入图片描述
进入新一轮for循环，i为2，end更新为2，t变为3。
在这里插入图片描述
进入while循环，t>arr[end]，执行break，跳出while循环，再把t赋给arr[end+1]，arr[end+1]仍为3，排序完成。从这里也可看到，for循环的循环条件必须是i<n-1，若i<n，则i=n-1时，end+1就越界了。

插入排序的特性：

  1. 元素集合越接近有序，直接插入排序算法的时间效率越高
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)，它是一种稳定的排序算法
  4. 稳定性：稳定（相同值在数组中相对顺序经排序后仍不变，则为稳定）

2.希尔排序

希尔排序是插入排序的优化，先选定一个整数gap，从首元素开始，每隔gap距离就把元素分为一组，然后控制gap进行循环，当gap>1时为预排序，让数组接近有序，当gap=1时，为插入排序。

void ShellSort(int* a, int n)//希尔排序
{int gap = n;while (gap > 1){gap = gap / 3 + 1;//+1保证最后一个gap一定是1，gap>1时为预排序，gap=1时为插入排序for (int i = 0;i < n - gap;i++){int end = i;int t = a[end + gap];while (end >= 0){if (t < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = t;}}
}

设数组a[10]={9,1,2,5,7,4,8,6,3,5}，数组长度为10，即gap=10。进入while循环，gap变为4，即for循环的循环条件为i<6，进入for循环。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
最终执行完一次for循环，数据变得有序。
在这里插入图片描述
接下来进入新一轮while循环，gap变为2，执行for循环。当再次进入while循环后gap变为1，我们把代码中for循环部分的gap全部换为1，就与插入排序的代码一样了。

希尔排序的特性：

  1. gap越大，大的数越快跳到后面，小的数越快跳到前面，相对越不接近有序
  2. gap越小，跳得越慢，但越接近有序
  3. 时间复杂度：O(N^1.3)
  4. 空间复杂度：O(1)
  5. 稳定性：不稳定

3.选择排序

选择排序遍历一遍数组，找出最小值，然后与首元素交换，除去首元素后再遍历一遍数组，找出最小值，与数组下标为1的元素交换，如此循环往复，直到只剩一个元素。优化后，我们可以一次遍历就取得最小最大值，分别放在数组的首尾，缩小区间，再次遍历。

void Swap(int* p1, int* p2)//交换
{int t = *p1;*p1 = *p2;*p2 = t;
}void SelectSort(int* a, int n)//选择排序
{int begin = 0, end = n - 1;while (begin < end){int maxi = begin, mini = begin;for (int i = begin + 1;i <= end;i++)//循环一次，找到最大最小值，放到最左最右边，{                                   //缩小区间，再进入新循环。if (a[i] > a[maxi])maxi = i;if (a[i] < a[mini])mini = i;}Swap(&a[begin], &a[mini]);if (begin == maxi)maxi = mini;Swap(&a[end], &a[maxi]);begin++;//缩小区间end--;}}

以数组a[8]={9,1,2,5,7,4,6,3}为例。执行完第一次for循环后如图所示：
在这里插入图片描述
把数组中最小元素放到下标为0的位置出，即交换a[begin]和a[mini]。
在这里插入图片描述
此时，数组中最大值被换到了下标为mini的位置，如果直接交换a[maxi]和a[end]，最小值就会被换到数组的最后，排序结果就会出错。所以需要判断当下标begin=maxi时，由于先执行了交换a[begin]和a[mini]，最大值被换到了下标为mini的位置，要把maxi更新为mini，再交换a[maxi]和a[end]。
在这里插入图片描述
在这里插入图片描述
最后缩小区间，进入新一轮的while循环。
在这里插入图片描述
选择排序的特性：

  1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
  2. 时间复杂度：O(N^2)
  3. 空间复杂度：O(1)
  4. 稳定性：不稳定

4.快速排序

hoare法

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

我们一般把首元素作为基准值。

void QuickSort1(int* a, int left, int right)//快速排序：hoare法
{if (left >= right)//不存在的区间return;int key = left;int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= a[key])//end找比a[key]小的数end--;while (begin < end && a[begin] <= a[key])//begin找比a[key]大的数begin++;Swap(&a[begin], &a[end]);}Swap(&a[begin], &a[key]);key = begin;    //[left,key-1] key [key+1,right]QuickSort1(a, left, key - 1);QuickSort1(a, key + 1, right);
}

以数组a[10]={6,1,2,7,9,3,4,5,10,8}为例，进入循环前如图所示。
在这里插入图片描述
当a[end]<a[key]时，end停下；当a[begin]>a[key]时，begin停下。此时交换a[end]和a[begin]。
在这里插入图片描述
在这里插入图片描述
end走到a[end]=3时，end停下，begin开始走，当begin=end时，不满足begin<end，begin停下，交换a[begin]和a[end]，此时相当于自己和自己交换。
在这里插入图片描述
跳出外层while循环，交换a[key]和a[begin]，让key=begin，分割出左右区间，再分别对两区间排序，即递归。
在这里插入图片描述
在这里插入图片描述
问题： 下标0做key，右边end先走时，为什么begin和end相遇位置一定比a[key]小？

若begin遇到end，因为end停下的位置对应的元素一定比a[key]小，所以相遇位置比a[key]小。若end遇到begin，end未遇到比a[key]小的元素就与begin相遇，由于经过上一轮交换，此时a[begin]<a[key]，所以相遇位置比a[key]小。

相反，让最右边做key，左边begin先走，可保证相遇位置比a[key]大。

hoare法优化

三数取中： 当待排序数组已经是有序时，再使用快排会出现效率退化，end要走到最左边才能开始交换、递归。所以，我们在排序前取最左边元素a[left]、中间元素a[mid]、最右边元素a[right]，比较后得到中间大小的元素，将它与首元素交换后作为a[key]。

int GetMidi(int* a, int left, int right)//三数取中
{int mid = (left + right) / 2;if (a[left] < a[mid]){if (a[mid] < a[right])return mid;elsereturn a[left] < a[right] ? right : left;}else{if (a[mid] > a[right])return mid;elsereturn a[left] < a[right] ? left : right;}
}

小区间优化： 当区间内元素较少时，不必再递归分割排序，改为插入排序，可减少递归次数，防止栈溢出，并提升效率。

优化后的代码如下：

void QuickSort2(int* a, int left, int right)
{if (left >= right)return;if ((right - left + 1) < 10)//小区间优化，当区间内元素较少时，不再递归分割排序。减少递归次数。InsertSort(a + left, right - left + 1);else{int begin = left, end = right;int midi = GetMidi(a, left, right);//三数取中Swap(&a[midi], &a[begin]);int key = begin;while (begin < end){while (begin < end && a[end] >= a[key])end--;while (begin < end && a[begin] <= a[key])begin++;Swap(&a[begin], &a[end]);}Swap(&a[key], &a[begin]);key = begin;QuickSort2(a, left, key - 1);QuickSort2(a, key + 1, right);}
}
前后指针法

用prev、cur表示数组下标，初始时，prev指向首元素，cur指向prev指向的下一个元素。每次循环cur都要走一步，当a[cur]>=a[key]时，prev也走，当a[cur]<a[key]，且prev走了一步后未与cur相遇时，交换a[prev]和a[cur]。直到cur越界时，停止循环，交换a[prev]和a[key]。

int PartSort(int* a, int left, int right)
{int midi = GetMidi(a, left, right);//三数取中Swap(&a[left], &a[midi]);int key = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[key] && ++prev != cur)Swap(&a[prev], &a[cur]);cur++;}Swap(&a[prev], &a[key]);return prev;
}
void QuickSort(int* a, int left, int right)
{if (left >= right)return;int key = PartSort(a, left, right);QuickSort(a, left, key - 1);QuickSort(a, key + 1, right);
}

仍以a[10]={6,1,2,7,9,3,4,5,10,8}为例。
在这里插入图片描述
在这里插入图片描述
如果a[cur]>a[key]，则不执行交换，prev也不移动，这样的操作使prev和cur之间的元素全是大于a[key]的元素。
在这里插入图片描述
在这里插入图片描述

快排：非递归

我们使用数据结构中的栈，将区间[0,n]存入栈中，再将区间取出作为前后指针法函数的参数进行排序，接下来分出右左区间入栈，进入新循环。

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 key = PartSort(a, begin, end);//前后指针，单趟排序if (key + 1 < end)//右区间入栈{STPush(&st, end);STPush(&st, key + 1);}if (begin < key - 1)//左区间入栈{STPush(&st, key - 1);STPush(&st, begin);}}
}

在这里插入图片描述
快速排序的特性总结：

  1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(logN)
  4. 稳定性：不稳定

在这里插入图片描述

5.归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：
在这里插入图片描述
此算法要借助一个数组中转。

void _MergeSort(int* a, int* t, int begin, int end)//a中数据分解，谁小谁先放入t,最后把t拷贝给a
{if (begin >= end)return;int mid = (begin + end) / 2;//后序遍历_MergeSort(a, t, begin, mid);_MergeSort(a, t, mid + 1, end);//[begin,mid]和[mid+1]区间内数据有序就开始归并int begin1 = begin, end1 = mid;//归并int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2])t[i++] = a[begin1++];elset[i++] = a[begin2++];}  //循环结束后，要么begin1走完，要么begin2走完while (begin1 <= end1)//begin2走完，begin1未走完t[i++] = a[begin1++];while (begin2 <= end2)//begin1走完，begin2未走完t[i++] = a[begin2++];memcpy(a + begin, t + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)//归并排序
{int* t = (int*)malloc(n * sizeof(int));if (t == NULL){perror("malloc fail");return;}_MergeSort(a, t, 0, n - 1);free(t);t = NULL;
}
归并排序：非递归
void MergeSortNonR(int* a, int n)//归并排序：非递归
{int* t = (int*)malloc(n * sizeof(int));if (t == NULL){perror("malloc fail");return;}int gap = 1;//一次归并中，参与归并的两组数据中每组有gap个数while (gap < n){for (int i = 0;i < n;i += 2 * gap){int begin1 = i, end1 = i + gap - 1;//区间[begin1,end1]int begin2 = i + gap, end2 = i + 2 * gap - 1;//区间[begin2,end2]if (begin2 >= n)//第二组区间都越界不存在，不用归并这一组break;if (end2 >= n)//第二组begin2没越界，end2越界，修正后归并end2 = n - 1;int j = i;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2])t[j++] = a[begin1++];elset[j++] = a[begin2++];}  //循环结束后，要么begin1走完，要么begin2走完while (begin1 <= end1)//begin2走完，begin1未走完t[j++] = a[begin1++];while (begin2 <= end2)//begin1走完，begin2未走完t[j++] = a[begin2++];memcpy(a + i, t + i, (end2 - i + 1) * sizeof(int));}gap *= 2;}free(t);t = NULL;
}

归并排序的特性总结：

  1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(N)
  4. 稳定性：稳定

6.计数排序

计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：

  1. 统计相同元素出现次数
  2. 根据统计的结果将序列回收到原来的序列中
void CountSort(int* a, int n)//计数排序
{int min = a[0], max = a[0];for (int i = 1;i < n;i++)//找出a中最大最小元素{if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int range = max - min + 1;//待排序数组在区间[min,max]内有几个元素int* count = (int*)calloc(range, sizeof(int));//count储存的是a中某元素在a出现的次数if (count == NULL){perror("calloc fail");return;}for (int i = 0;i < n;i++)//a[i]-min使a中元素对应数组count的下标count[a[i] - min]++; //a中某元素出现一次，count中对应下标的元素加1int j = 0;for (int i = 0;i < range;i++){while (count[i]--)a[j++] = i + min;}free(count);
}

计数排序的特性总结：

  1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
  2. 时间复杂度：O(MAX(N,range))
  3. 空间复杂度：O(range)
  4. 稳定性：稳定

7.排序总结

在这里插入图片描述
在这里插入图片描述

拙作一篇，望诸位同道不吝斧正。

http://www.xdnf.cn/news/19295.html

相关文章：

  • 第25章学习笔记｜额外的提示、技巧与技术（PowerShell 实战版）
  • Qt Core 之 QString
  • PyTorch 张量（Tensor）详解：从基础到实战
  • 【深度学习】配分函数：近似最大似然与替代准则
  • python复杂代码如何让ide自动推导提示内容
  • 编写Linux下usb设备驱动方法：disconnect函数中要完成的任务
  • More Effective C++ 条款20：协助完成返回值优化（Facilitate the Return Value Optimization）
  • 每日算法题【栈和队列】：栈和队列的实现、有效的括号、设计循环队列
  • [软考中级]嵌入式系统设计师—考核内容分析
  • Redis持久化之AOF(Append Only File)
  • Java基础知识（十二）
  • 8.31【Q】CXL-DMSim:
  • vue3+vite+ts 发布npm 组件包
  • Deep Think with Confidence：llm如何进行高效率COT推理优化
  • 第24章学习笔记｜用正则表达式解析文本文件（PowerShell 实战）
  • zkML-JOLT——更快的ZK隐私机器学习：Sumcheck +Lookup
  • Pytest 插件介绍和开发
  • leetcode 260 只出现一次的数字III
  • COLA：大型语言模型高效微调的革命性框架
  • 免费电脑文件夹加密软件
  • 基于Adaboost集成学习与SHAP可解释性分析的分类预测
  • 【K8s】整体认识K8s之存储--volume
  • 在win服务器部署vue+springboot + Maven前端后端流程详解，含ip端口讲解
  • Transformer架构三大核心：位置编码（PE）、前馈网络（FFN）和多头注意力（MHA）。
  • 学习Python中Selenium模块的基本用法（12：操作Cookie）
  • TFS-2005《A Possibilistic Fuzzy c-Means Clustering Algorithm》
  • 使用 Python 自动化检查矢量面数据的拓扑错误（含导出/删除选项）
  • 算法题（196）：最大异或对
  • 特殊符号在Html中的代码及常用标签格式的记录
  • Qt组件布局的经验