内容每5分钟更新
客服QQ:4008017500
客服QQ:4008017500
点击： 回复：2218 关闭此页
二分法排序
楼主
赌神传说 | 发表于2022-12-04 14:36:38
赌神传说 | 发表于2022-12-04 14:36:38二分法排序其实是一种改进的插入排序，也是通过查找待插入位置来实现排序，这和插入排序是类似的。
算法思想，在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半部分再进行折半，否则对后半进行折半，
直到left
二分法实际上没有进行排序，只进行了有查找。所以当找到要插入的位置时，必须从移动最后一个记录开始，向后移动一位，再移动倒数第2位，直到要插入的位置的记录移后一位。
下面的图展示了二分法排序的工作原理，看图
下面通过代码来实现二分法排序，上代码
#include
using namespace std;
void dichotomizingsort(int a[],int n) //升序排列
{
int i,j,mid=0,left,right,tem=0;
for(i=1;i
tem=a;
left=0; //指向有序表的低位
right=i-1; //指向有序表的高位
while(left<=right) //当left和right向中间靠拢的时候发生碰撞就结束排序
{
mid=(left+right)/2; //取有序表中间的那一个元素
if(a[mid]>tem)
right=mid-1; //待插入元素比大中间元素小，就对前半部分再折半
else
left=mid+1; //待插入元素不小于中间元素，就对后半部分再折半
}
for(j=i-1;j>=left;j--) //left就是在有序表中待插入的位置，但要先把left之后的所有元素向后移动一位
{
a[j+1]=a[j];
}
a[left]=tem; //移动后就可以插入了
cout<<"第"<
for(j=0;j<=i;j++)
cout<
}
int main()
{
int a[10]={34,4,78,35,3,64,45,18,26,35};
dichotomizingsort(a,10);
cout<<"执行插入排序后数组为：";
for(int i=0;i<10;i++)
cout<<<" ";
return 0;
}
测试结果如下：
最后来说一下复杂度
空间复杂度：和插入排序一样，只用到了一个辅助空间，为O(1)。
时间复杂度：二分法排序是一种稳定的排序算法，与二分排序的复杂度相同；最好的情况是当插入的位置刚好是二分位置 所用时间为O(log2n)；最坏的情况是当插入的位置不在
二分位置， 所需比较次数为O(n)，无限逼近线性查找的复杂度；而平均时间复杂度为O(n^2)。
算法思想，在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半部分再进行折半，否则对后半进行折半，
直到left
二分法实际上没有进行排序，只进行了有查找。所以当找到要插入的位置时，必须从移动最后一个记录开始，向后移动一位，再移动倒数第2位，直到要插入的位置的记录移后一位。
下面的图展示了二分法排序的工作原理，看图
下面通过代码来实现二分法排序，上代码
#include
using namespace std;
void dichotomizingsort(int a[],int n) //升序排列
{
int i,j,mid=0,left,right,tem=0;
for(i=1;i
tem=a;
left=0; //指向有序表的低位
right=i-1; //指向有序表的高位
while(left<=right) //当left和right向中间靠拢的时候发生碰撞就结束排序
{
mid=(left+right)/2; //取有序表中间的那一个元素
if(a[mid]>tem)
right=mid-1; //待插入元素比大中间元素小，就对前半部分再折半
else
left=mid+1; //待插入元素不小于中间元素，就对后半部分再折半
}
for(j=i-1;j>=left;j--) //left就是在有序表中待插入的位置，但要先把left之后的所有元素向后移动一位
{
a[j+1]=a[j];
}
a[left]=tem; //移动后就可以插入了
cout<<"第"<
for(j=0;j<=i;j++)
cout<
}
int main()
{
int a[10]={34,4,78,35,3,64,45,18,26,35};
dichotomizingsort(a,10);
cout<<"执行插入排序后数组为：";
for(int i=0;i<10;i++)
cout<
return 0;
}
测试结果如下：
最后来说一下复杂度
空间复杂度：和插入排序一样，只用到了一个辅助空间，为O(1)。
时间复杂度：二分法排序是一种稳定的排序算法，与二分排序的复杂度相同；最好的情况是当插入的位置刚好是二分位置 所用时间为O(log2n)；最坏的情况是当插入的位置不在
二分位置， 所需比较次数为O(n)，无限逼近线性查找的复杂度；而平均时间复杂度为O(n^2)。
1楼 赌神传说 | 发表于2022-12-04 14:45:27
赌神传说 | 发表于2022-12-04 14:45:27每一种算法都有自己的运行时间，而衡量运行时间的方法通常采用大O表示法。大O表示法是一种比较特殊的表示方法，指出了算法的速度有多快，根据刚才的推演，如果列表中有100个元素，最多只要猜7次就可以查找到正确答案，如果列表中包含40亿个数字，最多需要猜32次。二分查找的运行时间由此称为对数时间（或log时间），用大O表示法表示为O(logn)。
