如何进行C语言数据结构与算法中的排序总结
这篇文章将为大家详细讲解有关如何进行C语言数据结构与算法中的排序总结，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。
一、前言
学习目标：
排序和查找密不可分，将待处理的数据按关键值大小有序排列后，查找更加快速准确
理解各种排序算法的定义和特点，并能将代码灵活运用
掌握各种排序方法时间复杂度与空间复杂度
理解排序稳定和不稳定的概念
重点和难点： 希尔、快速、堆、归并排序这几种快速排序
二、基本概念
1.排序
定义：将一个无序的数据元素任意序列，重新排列成有序的过程
代码：
typedef struct{ int key; //假设关键字为int型 OtherType other_data;} RecordType;2.排序方法的稳定性
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 5 | 4 | 10 | 11 | 22 | 8 | 10 | 76 | 1 | 2 |
解读：如上个表格这样的一个无序数组，想要将它按照从小到大排序。上图下标2和6对应的数字都是10，排序后假如红色的10任然在黑色的10前面，那这种排序方法就是稳定的，否则排序方法不稳定。
3.内部和外部排序
内部排序：整个排序过程在内存中
外部排序：需要排序的数过大，需要借助外部设备
三、插入类排序
插入类：在一个有序序列插入一个新的记录，使之仍然有序
1.直接插入排序
动态演示：
算法讲解：
上面的动态图可以很好的表达直接插入的过程，只是动态图有点长
首先将0作为监视哨，用一个指针从前往后找后面的数字比前面数字小的，找到了放到0
指针开始向前移动，如果指向的值比监视哨里的值大，数字向后移
如果指向的值比监视哨里的值小，那把监视哨里的值存入这个元素之后
以此类推
代码：
void InsSort(RecordType r[], int length)/* 对记录数组r做直接插入排序，length为数组中待排序记录的数目*/{ int i,j; for (i=2; i<=length; i++) { r[0]=r[i]; /*将待插入记录存放到监视哨r[0]中*/ j=i-1; while (r[0].key< r[j].key ) /* 寻找插入位置 */ { r[j+1]= r[j]; j=j-1; } r[j+1]=r[0]; /*将待插入记录插入到已排序的序列中*/ }} /* InsSort */特点：
稳定排序
时间复杂度O(n*n), 空间复杂度O(1)
2.折半插入排序
算法讲解：
动态图没找到，只能用上面这张图片了
折半插入和折半查找思想差不多，对于一个有序的数组，将一个数字插入之后任然有序
k=要插入的值 low=1, high=length , mid=(low+high)+1 mid对应的值比k大， high=low-1,否则 low=mid+1,
当low >high ，low后面就是k插入的位置
代码：
void BinSort (RecordType r[], int length)/*对记录数组r进行折半插入排序，length为数组的长度*/{ int i,j; RecordType x; int low,high,mid; for (i=2; i<=length ; ++i ) { x= r[i]; low=1; high=i-1; while (low<=high ) /* 确定插入位置*/ { mid=(low+high) / 2; if ( x.key< r[mid].key) high=mid-1; else low=mid+1; } for ( j=i-1 ; j>= low; --j ) r[j+1]= r[j]; /* 记录依次向后移动 */ r[low]=x; /* 插入记录 */ }}/*BinSort*/特点：
稳定排序
时间复杂度O(n*n), 空间复杂度O(1)
3.希尔排序
动态演示：
算法讲解：
对于希尔排序来说取增量 d (d一般为奇数，并且逐次递减)
上图第一次排序d等于5，将第一个作为起始点，下标+5取下一个值，一直到最后，将去到的值从小到达排序，然后将第二个作为起始点，3 4 5依次作为起始点排序
第二次是d等于3
第三次是d等于1
代码：
void ShellInsert(RecordType r[], int length, int delta)/*对记录数组r做一趟希尔插入排序，length为数组的长度,delta 为增量*/{ int i,j; for(i=1+delta;i<= length; i++) /* 1+delta为第一个子序列的第二个元素的下标 */ if(r[i].key < r[i-delta].key) { r[0]= r[i]; /* 备份r[i] (不做监视哨) */ for(j=i-delta; j>0 &&r[0].key < r[j].key; j-=delta) r[j+delta]= r[j]; r[j+delta]= r[0]; }}/*ShellInsert*/特点：
不稳定排序方法
增量序列的d取值无除1之外的公因子，最后一个增量值必须为1
时间复杂度O(nlogn) 空间复杂度O(1)
四、交换类排序
1.冒泡排序
动态演示：
算法讲解：
设立两个指针，i，j
每一次排序都会把最大的一个数放到后面，依次类推，假设执行2次以后，那么最后2个数就不需要比较了
执行n-1次排序，结果完成
代码：
void BubbleSort(RecordType r[], int length )/*对记录数组r做冒泡排序，length为数组的长度*/{ int n,i,j; nt change; RecordType x; n=length; change=TRUE; for ( i=1 ; i<= n-1 && change ;++i ) { change=FALSE; for ( j=1 ; j<= n-i ; ++j) if (r[j].key > r[j+1].key ) { x= r[j]; r[j]= r[j+1]; r[j+1]= x; change=TRUE; } }} /* BubbleSort特点：
稳定排序
时间复杂度O(n*n), 空间复杂度O(1)
2.快速排序
动态演示：
算法讲解：
快速排序讲起来稍微有点复杂，其实就是划分区域
建立两个指针low high 分别指向第一个和第二个元素，把第一个元素的值赋给x变量
high向前移动，假如high指向的值小于x，则high指向的值与x互换
low向后移动，假如low指向的值大于x，则low指向的值与x互换
重复3 4两步，知道high==low，第一次结束
将low指向第二个元素，把第二个元素的值赋给x变量
重复操作，知道元素有序
代码：
1.递归算法:
void QKSort(RecordType r[],int low, int high )/*对记录数组r[low..high]用快速排序算法进行排序*/{ int pos; if(low2.非递归算法：
int QKPass(RecordType r[],int left,int right)/*对记录数组r 中的r[left]至r[right]部分进行一趟排序，并得到基准的位置，使得排序后的结果满足其之后（前）的记录的关键字均不小于（大于）于基准记录*/{ RecordType x; int low,high; x= r[left]; /* 选择基准记录*/ low=left; high=right; while ( low=x.key ) /* high从右到左找小于x.key的记录 */ high--; if ( low 特点：
不稳定排序，但内部排序中公认效率最好的一种
时间复杂度O(nlogn) 空间复杂度O(logn)
五、总结比较
关于如何进行C语言数据结构与算法中的排序总结就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。
