二分法排序其实是一种改进的插入排序，也是通过查找待插入位置来实现排序，这和插入排序是类似的。
算法思想，在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半部分再进行折半，否则对后半进行折半，
直到left<right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。
二分法实际上没有进行排序，只进行了有查找。所以当找到要插入的位置时，必须从移动最后一个记录开始，向后移动一位，再移动倒数第2位，直到要插入的位置的记录移后一位。
下面的图展示了二分法排序的工作原理，看图
下面通过代码来实现二分法排序，上代码
1 #include<iostream> 2 using namespace std; 3 4 void dichotomizingsort(int a[],int n) //升序排列 5 { 6 int i,j,mid=0,left,right,tem=0; 7 for(i=1;i<n;i++) 8 { 9 tem=a[i]; 10 left=0; //指向有序表的低位 11 right=i-1; //指向有序表的高位 12 while(left<=right) //当left和right向中间靠拢的时候发生碰撞就结束排序 13 { 14 mid=(left+right)/2; //取有序表中间的那一个元素 15 if(a[mid]>tem) 16 right=mid-1; //待插入元素比大中间元素小，就对前半部分再折半 17 else 18 left=mid+1; //待插入元素不小于中间元素，就对后半部分再折半 19 } 20 for(j=i-1;j>=left;j--) //left就是在有序表中待插入的位置，但要先把left之后的所有元素向后移动一位 21 { 22 a[j+1]=a[j]; 23 } 24 a[left]=tem; //移动后就可以插入了 25 cout<<"第"<<i<<"次待插入的数据是："<<tem<<endl; 26 cout<<"此时有序表中的数据位："; 27 for(j=0;j<=i;j++) 28 cout<<a[j]<<" "; 29 cout<<endl; 30 } 31 } 32 int main() 33 { 34 int a[10]={34,4,78,35,3,64,45,18,26,35}; 35 dichotomizingsort(a,10); 36 cout<<"执行插入排序后数组为："; 37 for(int i=0;i<10;i++) 38 cout<<a[i]<<" "; 39 return 0; 40 }
测试结果如下：
最后来说一下复杂度
空间复杂度：和插入排序一样，只用到了一个辅助空间，为O(1)。
时间复杂度：二分法排序是一种稳定的排序算法，与二分排序的复杂度相同；最好的情况是当插入的位置刚好是二分位置 所用时间为O(log2n)；最坏的情况是当插入的位置不在
二分位置， 所需比较次数为O(n)，无限逼近线性查找的复杂度；而平均时间复杂度为O(n^2)。
本人水平有限，如有错误欢迎指出 ！谢谢！
2020-04-30 18:03:11
今天的文章二分法排序_二分法排序的时间复杂度分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/51366.html
