目录一、前言二、基本概念1.排序2.排序方法的稳定性3.内部和外部排序三、插入类排序1.直接插入排序2.折半插入排序3.希尔排序四、交换类排序1.冒泡排序2.快速排序五、总结比较一、
学习目标：
排序和查找密不可分，将待处理的数据按关键值大小有序排列后，查找更加快速准确
理解各种排序算法的定义和特点，并能将代码灵活运用
掌握各种排序方法时间复杂度与空间复杂度
理解排序稳定和不稳定的概念
重点和难点： 希尔、快速、堆、归并排序这几种快速排序
定义：将一个无序的数据元素任意序列，重新排列成有序的过程
代码：
typedef struct{
int key; //假设关键字为int型
OtherType other_data;
} RecordType;| 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前面，那这种排序方法就是稳定的，否则排序方法不稳定。
插入类：在一个有序序列插入一个新的记录，使之仍然有序
动态演示：
算法讲解：
代码：
void InsSort(RecordType r[], int length)
{
int i,j;
for (i=2; i<=length; i++)
{
r[0]=r[i];
j=i-1;
while (r[0].key< r[j].key )
{
r[j+1]= r[j];
j=j-1;
}
r[j+1]=r[0];
}
} 特点：
稳定排序
时间复杂度O(n*n), 空间复杂度O(1)
算法讲解：
代码：
void BinSort (RecordType r[], int 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;
}
}特点：
稳定排序
时间复杂度O(n*n), 空间复杂度O(1)
动态演示：
算法讲解：
代码：
void shellInsert(RecordType r[], int length, int delta)
{ int i,j;
for(i=1+delta;i<= length; i++)
if(r[i].key < r[i-delta].key)
{
r[0]= 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];
}
}特点：
不稳定排序方法
增量序列的d取值无除1之外的公因子，最后一个增量值必须为1
时间复杂度O(nlogn) 空间复杂度O(1)
动态演示：
算法讲解：
代码：
void BubbleSort(RecordType r[], int 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;
}
}
}
{
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)
{
RecordType x; int low,high;
x= r[left];
low=left; high=right;
while ( low<high )
{
while (low< high && r[high].key>=x.key )
high--;
if ( low <high ) {r[low]= r[high]; low++;}
while (low<high && r[low].key<x.key )
low++;
if ( low<high ){ r[high]= r[low]; high--; }
}
r[low]=x;
return low;
} 特点：
不稳定排序，但内部排序中公认效率最好的一种
时间复杂度O(nlogn) 空间复杂度O(logn)
--结束END--
本文标题: C语言数据结构与算法之排序总结(一)
本文链接: https://lsjlt.com/news/160188.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
官方手机版
微信公众号
商务合作
0