本文将详细说明如何用C语言对数据结构和算法进行排序和总结。这篇文章的内容质量很高，所以边肖会分享给大家参考。希望你看完这篇文章后有所了解。
00-1010学习目标：
排序和搜索是密不可分的。待处理的数据按照键值的大小进行排序后，搜索更快、更准确。
了解各种排序算法的定义和特点，灵活运用代码。
掌握各种排序方法的时间复杂度和空间复杂度
理解排序稳定性和不稳定性的概念。
重点和难点：希尔，快速，堆，合并和排序这几种快速排序。
一、前言
二、基本概念
定义：将无序数据元素的任意序列重新排列成一个顺序的过程。
代码：
typedefstruct{
intkey//假设关键字是int类型。
其他类型其他数据；
} RecordType00-10101012345678954101128107612解释：像上一个表这样的无序数组想从小到大排序。上图中下标2和下标6对应的数字是10。如果排序后红色10仍然在黑色10前面，那么这个排序方法是稳定的，否则排序方法是不稳定的。
00-1010内部排序：整个排序过程都在内存中。
外部分拣：需要分拣的数量太大，需要外部设备。
00-1010插入类：在有序序列中插入新记录，使其仍然有序。
00-1010动态演示：
算法说明：
上面的动态图可以很好的表达直接插入的过程，但是动态图有点长。
首先，用0作为观察柱，用指针寻找后面比前面小的数字。如果找到了，就放在0。
指针开始向前移动。如果指向的值大于观察柱中的值，数字将向后移动。
如果指向的值小于观察柱中的值，则将该值存储在观察柱中该元素之后。
等等
代码：
空隙排序(记录类型[]，长度)
/*直接插入记录数组r并排序，其中length是数组中需要排序的记录数*/
{
inti，j；
for(I=2；I=长度；(一)
{
r[0]=r[I]；/*存储要插入到监视日志r[0]中的记录*/
j=I-1；
While(r[0]。keyr[j]。键)/*找到插入位置*/
{
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(low<high)
{
pos=QKPass(r, low, high); /*调用一趟快速排序，将枢轴元素为界划分两个子表*/
QKSort(r, low, pos-1); /*对左部子表快速排序*/
QKSort(r, pos+1, high); /*对右部子表快速排序*/
}
}
2.非递归算法：
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<high )
{
while (low< high && r[high].key>=x.key ) /* high从右到左找小于x.key的记录 */
high--;
if ( low <high ) {r[low]= r[high]; low++;} /* 找到小于x.key的记录，则进行交换*/
while (low<high && r[low].key<x.key ) /* low从左到右找大于x.key的记录 */
low++;
if ( low<high ){ r[high]= r[low]; high--; } /* 找到大于x.key的记录，则交换*/
}
r[low]=x; /*将基准记录保存到low=high的位置*/
return low; /*返回基准记录的位置*/
} /* QKPass */
特点：
不稳定排序，但内部排序中公认效率最好的一种
时间复杂度O(nlogn) 空间复杂度O(logn)
五、总结比较
关于如何进行C语言数据结构与算法中的排序总结就分享到这里了，希望
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/150317.html