时间:2021-05-20
直接插入排序
1 排序思想:
将待排序的记录Ri插入到已经排好序的记录R1,R2,……,R(N-1)中。
对于一个随机序列而言,就是从第二个元素开始,依次将这个元素插入到它之前的元素中的相应位置。它之前的元素已经排好序。
第1次排序:将第2个元素插入到前边的有序列表(此时前边只有一个元素,当然是有序的),之后,这个序列的前2个元素就是有序的了。
第2次排序:将第3个元素插入到前边长度为2的有序列表,使得前2个元素是有序的。
以此类推,直到将第N个元素插入到前面长度为(N-1)的有序列表中。
2 算法实现:
// 直接插入排序void straight_insert_sort(int num[], int len){ int i,j,key; for(j=1;j<len;j++){ key=num[j]; i=j-1; while(i>=0&&num[i]>key){ num[i+1]=num[i]; i--; } num[i+1]=key; }}3 性能分析:
3.1 空间复杂度:如上代码,使用了一个辅助单元key,空间复杂度为O(1)
3.2 时间复杂度:
3.2.1 最好情况:待排序记录已经是有序的,则一趟排序,关键字比较1次,记录移动2次。则整个过程
比较次数为
记录移动次数为
时间复杂度O(n)
3.2.2 最坏情况:待排序记录已经是逆序的,则一趟排序,关键字比较次数i次(从i-1到0),记录移动(i+2)次。整个过程
比较次数为
记录移动次数为
时间复杂度O(n^2)
3.2.3 平均时间复杂度:O(n^2)
3.3 稳定性:稳定
折半插入排序
1 排序思想:
直接排序的基础上,将待排序的记录Ri插入到已经排好序的记录R1,R2,……,R(N-1)中,由于记录R1,R2,……,R(N-1)已经排好序,所以在查找插入位置时可采用“折半查找”。
2 算法实现:
// 折半插入排序void binary_insert_sort(int num[], int len){ int i,j,key,low,high,mid; for(i=1;i<len;i++){ key=num[i]; low=0; high=i-1; mid=(low+high)/2; // 寻找插入点,最终插入点在low while(low<=high){ if(key<num[mid]) high=mid-1; else low=mid+1; mid=(low+high)/2; } // 移动记录 for(j=i;j>low;j--){ num[j]=num[j-1]; } // 插入记录 num[low]=key; }}3 性能分析:
3.1 空间复杂度:如上代码,使用了一个辅助单元key,空间复杂度为O(1)
3.2 时间复杂度:虽然折半查找减少了记录比较次数,但没有减少移动次数,因此时间复杂度同直接查找算法。
3.2.1 最好情况:时间复杂度O(n)
3.2.2 最坏情况:时间复杂度O(n^2)
3.2.3 平均时间复杂度:O(n^2)
3.3 稳定性:稳定
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
一、折半插入排序(二分插入排序)将直接插入排序中寻找A[i]的插入位置的方法改为采用折半比较,即可得到折半插入排序算法。在处理A[i]时,A[0]……A[i-1
前面的文章已经介绍了几种排序算法,如插入排序(直接插入排序,折半插入排序,希尔排序)、交换排序(冒泡排序,快速排序)、选择排序(简单选择排序,堆排序)、2-路归
插入排序Python实现importrandoma=[random.randint(1,999)forxinrange(0,36)]#直接插入排序算法defin
本文总结了一下常用的7种排序方法,并用php语言实现。1、直接插入排序/**直接插入排序,插入排序的思想是:当前插入位置之前的元素有序,*若插入当前位置的元素比
本文实例讲述了Java排序算法总结之希尔排序。分享给大家供大家参考。具体分析如下:前言:希尔排序(ShellSort)是插入排序的一种。是针对直接插入排序算法的