江门网站推广技巧方法网络营销怎么做
简介
首先要了解直接插入排序
还有二分查找
英文名:binary insertion sort
在直接插入排序算法上进行改进的算法
步骤
以下用数组2,5,8,3,6,9,1,4,7为例
从小到大排序
1.先看第一个数,将数组划分为有序和无序部分
- 首先看第一个数2,一个数必然有序,所以将2划分有序,后面都是无序
2.找到插入位置
-
取出无序部分的首个,在有序部分二分查找到位置
-
2,5,8不用移动,所以直接从3的插入开始
-
还是先拿出要插入的数
-
然后用二分查找找到应该插入的位置
3.移动数组,最后插入拿出的数
- 因为已经找到位置,所以直接全部移动,不用再去一个个比较
- 插入
后面步骤和直接插入类似,不再给出
代码
- 折半插入与直接插入的区别就在于找插入位置的方法
- 因为是二分查找,所以同样引入low和high,设为有序区的边界
- 当有序部分不存在这个数,根据二分的推论,最后low与high应该是这样
- 当存在这个数,结果是怎样?
- 注意代码中,low与high相同时,改变的是low
- 可以看到,都是从low开始去移动,最后放入low所指的位置
#include<bits/stdc++.h>using namespace std;void BInsertSort(int a[],int l)
{int temp;int low,high;int m;for(int i=1;i<l;i++){if(a[i]<a[i-1]){low=0;high=i-1;while(low<=high){m=low+(high-low)/2;if(a[m]>a[i])high=m-1;elselow=m+1;}temp=a[i];for(int j=i;j>low;j--)a[j]=a[j-1];a[low]=temp;}for(int k=0;k<l;k++)cout<<a[k]<<" ";cout<<endl;}
}int main()
{int a[10]={2,5,8,3,6,9,1,4,7};int b[10]={1,2,3,4,5,6,7,8,9};int len=9;BInsertSort(a,len);return 0;
}
特性
1.时间复杂度
折半查找只是减少了比较次数,但是元素的移动次数不变,所以时间复杂度为O(n2)O(n^2)O(n2)
2.空间复杂度
平均的空间复杂度也是:O(1)O(1)O(1)
3.算法稳定性
相同元素的前后顺序是否改变在上面的说明中已经提到了,这里再拿例子看一下
数组 2 4 5 8 3 6 4 1 4
每次输出low,也就是放入的位置的值
- 可以看到后面的相同数只会插入到相同数的后面,所以仍是稳定的排序算法
小测试
内容有点多,所以就不搞这个了,想改的话还是老规矩,和直接插入一样的
٩( ‘ω’ )و 蟹蟹!