这篇文章主要介绍“C语言数据结构与算法排序的方法有哪些”，在日常操作中，相信很多人在C语言数据结构与算法排序的方法有哪些问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C语言数据结构与算法排序的方法有哪些”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
一、前言
主要介绍选择类排序中的简单、树形和堆排序，归并排序、分配类排序的基数排序
二、选择类排序
选择类：每次从待排序的无序序列中，选择一个最大或最小的数字，放到前面，数据元素为空时排序结束
1.简单选择排序
动态演示：
算法讲解：
首先通过n-1次比较，从n个记录中找出最小值，将它与第一个元素交换
再通过n-2次比较，从剩余的n-1个记录中找出次小的值，将它与第二个记录交换
重复上述操作n-1，排序完成
代码：
void SelectSort(RecordType r[], int length){int i,j,k;int n;RecordType x; n=length;for ( i=1 ; i<= n-1; ++i) {k=i;for (j=i+1 ; j<= n ; ++j) if (r[j].key < r[k].key ) k=j;if ( k!=i) { x= r[i]; r[i]= r[k]; r[k]=x;}}} 特点：
不稳定排序
时间复杂度O(n*n), 空间复杂度O(1)
2.树形选择排序
静态演示：
算法讲解：
最下面一行21 25 49 25 16 08 63是给定需要从小到大排序的数字
相邻的两个选出一个最小的向上移一层，只有一个的补一个值无穷大的数
倒数第二层再次两两组合，直到最顶端
此时，最顶端08就是值最小的数，输出08，把所有08至为无穷大
再次选出一个最小值，以此类推
特点：
算法不作要求
稳定排序, 增加额外的存储空间
时间复杂度O（nlogn）,空间复杂度O(n-1)
3.堆选择排序
动态演示：
算法讲解：
根结点值最大的叫大顶堆，根结点值最小的叫小顶堆，上图就是一个构造大顶堆的图
从最后一层开始，如果孩子结点的值比父亲结点大，那么就交换位置
一层层向上推，直到根结点值最大
建立初始堆：
void crt_heap(RecordType r[], int length ){int i,n; n= length;for ( i=n/2; i >= 1; --i) sift(r,i,n);}调整堆：
void sift(RecordType r[], int k, int m){RecordType t;int i,j;int x;int finished;t= r[k]; x=r[k].key;i=k;j=2*i;finished=FALSE;while( j<=m && !finished ) { if (j<m && r[j].key< r[j+1].key ) j=j+1; if ( x>= r[j].key)finished=TRUE; else { r[i] = r[j]; i=j; j=2*i;} }r[i] =t; }堆排序：
void HeapSort(RecordType r[],int length) {int i,n;RecordType b;crt_heap(r, length);n= length;for ( i=n ; i>= 2; --i) {b=r[1]; r[1]= r[i];r[i]=b; sift(r,1,i-1); }} 特点：
堆选择是树形的改进，空间占用较小
不稳定排序，适合n值较大的排序
时间复杂度O(n*logn)，空间复杂度O(1)
三、归并排序
法一：
将整体数字一分为二，逐层细分
细分完成后，每一块进行排序，直到整体有序
法二：
将一串序列，相邻的两个归并到一起排序，再次把相邻两个有序的归并块再次排序，直到最后有序（优先推荐这种算法）
代码：
void MergeSort ( RecordType r[], int n) {MSort ( r, 1, n, r);}void MSort(RecordType r1[], int low, int high, RecordType r3[]) {int mid; RecordType r2[20];if (low==high) r3[low]=r1[low];else{mid=(low+high)/2; MSort(r1,low, mid, r2); MSort(r1,mid+1,high, r2); Merge (r2,low,mid,high, r3); }} 特点：
稳定排序
时间复杂度O(nlogn)，空间复杂度O(n)
附加空间比较大，很少用于内部排序，主要是外部排序
四、分配类排序
1.多关键字排序
高位优先：按照花色大小分成四类，在每一类中按照面值进行排序
低位优先：按照面值大小分成13类，将相同面值的不同花色进行排序
2.链式基数排序
算法讲解：
对于上面的9个三位数，第一步我们按照个位数从小到大排序
接着第一步的结果，按照十位数从小到达排序
最后借助第二步的结果，按照百位数从小到大排序
同样的，对于4位 5 位方法一样
特点：
时间复杂度O(d*n)，d是关键字数，n是记录数
稳定的排序
空间复杂度=2个队列指针+n个指针域
到此，关于“C语言数据结构与算法排序的方法有哪些”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注编程网网站，小编会继续努力为大家带来更多实用的文章！
