首页 / 算法 / 排序(1)--插入排序和交换排序
排序(1)--插入排序和交换排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序(1)--插入排序和交换排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3695字，纯文字阅读大概需要6分钟。
内容图文
首先引入几个概念：
内部排序：整个排序过程不需要访问外存便能完成。
外部排序：参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成。
稳定性和不稳定性： 设 Ki、Kj (1≤i≤n, 1≤j≤n, i≠j ) 分别为记录 Ri、Rj 的关键字，且 Ki = Kj ，在排序前的序列中 Ri 领先于 Rj (即 i < j )。若在排序后的序列中 Ri 仍领先于 Rj ，则称所用的排序方法是稳定的；反之，则称所用的排序方法是不稳定的。
一.插入排序：
1.直接插入排序：
(1)思想： 对第i个元素，把它插入到前i-1个元素(已经有序)里面（2<=i<=n）
(2).实现：
void InsertSort(SqList &L)
{
//对顺序表L做直接插入排序
for(i=2;i<=L.length;i++)
{
if(L.r[i].key<L.r[i-1].key)
{
L.r[0]=L.r[i];
L.r[i]=L.r[i-1];
for(j=i-2;L.r[0].key<L.r[j].key;j--)
{
L.r[j+1]=L.r[j];//记录后移
}
L.r[j+1]=L.r[0];//插入到正确位置
}
}
} (3).算法性能分析：
时间复杂度：最好情况：全部有序，那么移动次数为0;
最坏情况：全部逆序，移动次数为
取移动次数的平均数得算法时间复杂度为:O(n2)
稳定性：键码相同的两个记录，在整个排序过程中，不会通过比较而相互交换，所以是稳定的。
2.折半插入排序：
(1)思想：考虑到 L.r[1,..,i-1] 是按关键字有序的有序序列，则可以利用折半查找实现“L.r[1,…,i-1]中查找 L.r[i] 的插入位置”如此实现的插入排序为折半插入排序。
(2).实现：
void BinsertSort(SqList &L){ // 折半插入排序
int i,low,high,mid;
for(i=2; i<= L.length; ++i) {
L.r[0]=L.r[i]; //将L.r [i] 暂存到L.r[0]
low=1; high=i-1;
While(low<=high) { //比较，折半查找插入位置
mid=(low+high)/2; // 折半
if (L.r[0].key< L.r[mid].key) high=mid-1; //插入点在低半区
else low=mid+1; } // 插入点在高半区
for( j=i-1; j>=low; --j ) L.r[j+1]=L.r[j]; // 记录后移
L.r[low]=L.r[0]; } // 插入
} // BInsertSort (3).算法性能分析：
时间复杂度： 折半查找比顺序查找快，所以折半插入排序就平均性能来说比直接插入排序要快。
折半插入排序减少了关键数的比较次数，但记录的移动次数不变，其时间复杂度与直接插入排序相同。
稳定性：稳定。
3.希尔插入排序：
(1)思想：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
子序列的构成不是简单地“逐段分割”，而是将相隔某个增量dk的记录组成一个子序列,让增量dk逐趟缩短（例如依次取5,3,1），直到dk＝1为止
(2)实现：
void ShellInsert ( SqList &L, int dk )
{ //一趟希尔插入排序
//1.前后记录位置的增量是dk；
//2.L.r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到
for ( i=dk+1; i<=L.length; ++i )
if ( L.r[i].key< L.r[i-dk].key) {//将R[i]插入有序增量子表
L.r[0] = L.r[i]; // 暂存在R[0]
for (j=i-dk; j>0 && (L.r[0].key< L.r[j].key);j -= dk)
L.r[j+dk] = L.r[j]; // 记录后移，查找插入位置
L.r[j+dk] = L.r[0]; // 插入
}
}//ShellInsertvoid ShellSort (SqList &L, int dlta[ ], int t)
{
// 按增量序列dlta[0..t-1]对顺序表L作希尔排序
for (k=0; k<t; ++k)
ShellInsert( L, dlta[k]); // 一趟增量为dlta[k]的插入排序
} // ShellSort(3)性能分析：
开始时dk 的值较大，子序列中的对象较少，排序速度较快；随着排序进展，dk 值逐渐变小，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对 象已基本有序，所以排序速度仍然很快。
时间复杂度：
空间效率：O(1) —— 因为仅占用1个缓冲单元
稳定性：希尔排序选取增量的时候都是一个一个子序列比较的，很容易导致后一个数排到前一个数前面去，所以不稳定！
二.交换排序：
1.冒泡排序：
(1)思想:每一轮都是两两相邻比较，直到小的浮起或大的沉底
(2)实现：
void Bubblesort(ElemType R[],int n) {
int flag=1; //当flag为0则停止排序
for (int i=n; i>1; i--) { //i表示趟数，最多n-1趟
flag=0; //开始时元素未交换
for (int j=2; j<=i; j++)
if (R[j]<R[j-1]) { //发生逆序
temp=R[j]; R[j]=R[j-1]; R[j-1]=temp;
flag=1;
}
if(flag==0) return;
}
} // Bubblesort (3)算法分析：
时间复杂度:O(n2),可以取最好情况和做差情况取平均
稳定性：稳定
起泡排序的过程可见，起泡排序是一个增加有序序列长度的过程，也是一个缩小无序序列长度的过程，每经过一趟起泡，无序序列的长度只缩小1。
试设想：若能在经过一趟排序，使无序序列的长度缩小一半，则必能加快排序的速度。
2.快速排序：
(1)思想：通过一趟排序将待排序列以枢轴为标准划分成两部分，使其中一部分记录的关键字均比另一部分小，另一部分大，再分别对这两部分进行快速排序，以达到 整个序列有序(通常取第一个记录的值为基准值或枢轴).
(2)实现：
void QSort ( Elem R[ ], int low, int high ){ //对序列R[low...high]进行快速排序
if (low < high-1) { //长度大于1
pivot = Partition( L,low,high); //将R[low..high]一分为二
QSort(L,low, pivot-1); //对低子表递归排序，pivo是枢轴
QSort(L, pivot+1, high); // 对高子表递归排序
}
} // QSort
void QuickSort(Elem R[], int n){ //对记录序列进行快速排序
QSort(R, 1, n);
} // QuickSortint Partition (Elem R[ ], int low, int high){
R[0] = R[low]; pivotkey = R[low].key;
while (low < high) { //从两端交替向中间扫描
while (low < high && R[high].key >= pivotkey) - - high;
R[low] = R[high]; //将比枢轴记录小的移到低端
while (low < high && R[low].key <= pivotkey) + + low;
R[high] = R[low]; //将比枢轴记录大的移到高端
}
R[low] = R[0]; //枢轴记录到位
return low; //返回枢轴位置
} // Partition (3)算法性能分析：
时间复杂度：
空间复杂度：快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数(新的low和high)。最大递归调用层次数与递归树的深度一致，理想情况为 └ log2n ┘ + 1(向下取整) 。因此，要求存储开销为 O(log2n)
稳定性:不稳定。
原文：http://blog.csdn.net/wust__wangfan/article/details/19749511
内容总结
以上是互联网集市为您收集整理的排序(1)--插入排序和交换排序全部内容，希望文章能够帮你解决排序(1)--插入排序和交换排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。