排序算法及分析（插入、希尔、选择、冒泡）
假如我们要从小到大排序，下面几种简单的算法可以处理规模不大的数据，我写成函数形式。
一、插入排序
思想就是：从左到右对每个数，每次在它前面找到一个合适的位置把它插进去。
void InsertSort(int a[],int n){
int i,j,key;
for(i=2;i<=n;i++){
key=a[i];
for(j=i-1;j&&key<a[j];j--)a[j+1]=a[j];
a[j+1]=key;
}
}C是比较次数，M是移动次数，则
最好情况$C_{min}=n-1$，$M_{min}=0$;
最坏情况$C_{max}=(n+2)*(n-1)/2$,$M_{max}=\frac{(n+4)(n-1)}{2}$
随机情况$C_{avg}=(C_{min}+C_{max})/2 \approx n^2/4$,$M_{avg}\approx n^2/4$
折半插入排序，找插入位置时可以二分。
表插入排序：基于链表存储。
希尔排序：
1）按增量d分组。
2）每组用直接插入排序。
3）然后减小d(有一个增量序列，比如..15，7，3，1)，回到1），最后一次d为1。
int dlta[5]={15,7,3,1};
void ShellSort(int a[],int n){
int i,j,k,key;
for(k=0;k<4;k++){
int dk=dlta[k];
for(i=1+dk;i<=n;i++){
key=a[i];
for(j=i-dk;j&&key<a[j];j-=dk)a[j+dk]=a[j];
a[j+dk]=key;
}
}
}二、选择排序
思想是：每次找未排序的部分（i到n）最小的，和第i个交换。
void SelectSort(int a[],int n){
int i,j,Min,t;
for(i=1;i<n;i++){
Min=i;
for(j=i+1;j<=n;j++)
if(a[j]<a[Min]) Min=j;
t=a[i];
a[i]=a[Min];
a[Min]=t;
}
}比较次数 $C=n(n-1)/2$
移动次数 $M_{max}=3(n-1),M_{min}=0$
改进：树形选择排序（锦标赛排序）
是稳定排序。
时间复杂度$O(nlog_2n)$
辅助空间较多。
三、冒泡排序
思想：每次从左到右将每对相邻的且逆序的数交换，可以使未排序的最大的数放到未排序数的最后。
void BubbleSort(int a[],int n)
{//a数组下标1~n
int i,j,temp;
bool sorted;
for(i=1; i<n && !sorted; i++)
{
sorted=true;
for(j=1; j<=n-i; j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
sorted=false;
}
}
}
}调用：
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
BubbleSort(a,n);本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015-11-24 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读