折半插入排序详解「终于解决」

折半插入排序详解「终于解决」算法的基本过程:  1)计算 0 ~ i-1 的中间点,用 i 索引处的元素与中间值进行比较,如果 i 索引处的元素大,说明要插入的这个元素应该在中间值和刚加入i索引之间,反之,就是在刚开始的位置到中间值的位置,这样很简单的完成了折半;  2)在相应的半个范围里面找插入的位置时,不断的用(1)步骤缩小范围,不停的折半,范围依次缩小为 1/2  1/4  1/8 …..

   

算法的基本过程:

   1)计算 0 ~ i-1 的中间点,用 索引处的元素与中间值进行比较,如果 索引处的元素大,说明要插入的这个元素应该在中间值和刚加入i索引之间,反之,就是在刚开始的位置 到中间值的位置,这样很简单的完成了折半;

   2)在相应的半个范围里面找插入的位置时,不断的用(1)步骤缩小范围,不停的折半,范围依次缩小为 1/2  1/4  1/8 …….快速的确定出第 i  个元素要插在什么地方;

   3)确定位置之后,将整个序列后移,并将元素插入到相应位置。

时间复杂度O(n^2)

附加空间O(1)

 本来我觉得折半插入排序是特别简单点的,但是发现自己写起代码来特别费劲,然后就去翻书看博客,发现大家对折半插入的讲解都没有特别的透彻,在此写一篇博客来记录下折半插入排序的详细过程。我们先来看看各位前辈大牛的代码吧!针对重点关键代码我来为大家做详细的解释。

Java code

?

1
2
3
public static void  halfInsertSort(int[] arr ) {


int size = arr.length;


int low, high, mid;


for(int i=2;i<size;i++){


low = 1;


high = i-1;


arr[0] = arr[i];//哨兵复制


while(low<=high){


mid = (low+high)/2;


if(arr[0]>arr[mid]){


low = mid+1;


}


else {


high = mid – 1;


}


}


for(int j = i;j>high+1;j–){


arr[j] = arr[j-1];


}


arr[high+1] = arr[0];


}

}

1、为什么要从2开始算起,不应该是1吗?

    其实你会看到有的人写这个算法的时候是从1开始,但有更多的代码写的是从2开始,目的是第0个元素腾出来作为哨兵(该哨兵不在已排序队列内),第一个元素只有一个元素不用排,所以从第二个元素开始。

2、为什么要放一个哨兵

    有的代码不放哨兵,不放哨兵就需要判断high下表是否出界,而放了哨兵就完全不用担心出界的问题,这样能提高代码的性能。举个不放哨兵的例子:已排好序的13 16,现在要插入9,按照上面的算法,low指向第0个元素13,high指向第一个元素16,mid指向0号元素,判断发现9比13小,所以high=mid-1=-1。越界了!!!但是如果放了哨兵呢?low =1;high =2,mid =1岁,high=mid-1=0,没有越界,此时low>high,跳出循环。

 明白了放哨兵的作用了吧!

3、为什么j的范围是从i到high

   首先看看我们的while语句,条件是low<=high,也就是说只有high<low的时候才会停止while循环,而high<low是因为目标值小于arr[mid]导致的。再来分析下,什么情况下high就小于low了呢?肯定是mid值和low相等了,也就是说:目标值应该插在low的前面,也就是目前high值的后面。可能大家有di点晕了。跳出循环的最后一幕:

折半插入排序详解「终于解决」

折半插入排序详解「终于解决」

跳出后,high就变成了mid-1了。因此应该把目标元素插在mid指向的位子,也就是跳出while循环后的high+1的地方。所以high+1(包括high+1)的后面的数组整体应该向后移一位。因此第high+1个元素再等于目标元素。


还有些问题:

1、一般来说输入的数组都会是一个乱序的数组,不会是故意将第0号元素空出来,所以这个代码从某种意义上说还不算完美。


所以,我写的完整代码如下:

1
public class HalfInserSort {


public static void  halfInsertSort(int[] arr ) {


int size = arr.length;


int low, high, mid;


int tempArr = arr[0];//将0号元素腾空

for(int i=2;i<size;i++){


low = 1;


high = i-1;


arr[0] = arr[i];


while(low<=high){


mid = (low+high)/2;


if(arr[0]>arr[mid]){


low = mid+1;


}


else {


high = mid – 1;


}


}


for(int j = i;j>high+1;j–){


arr[j] = arr[j-1];


}


arr[high+1] = arr[0];


}


//把tempArr加入


low = 1; 


high = size -1;


arr[0]=tempArr;


while(low<=high){


mid = (low+high)/2;


if(tempArr>arr[mid]){


low = mid+1;


}


else {


high = mid – 1;


}


}


for(int k =0;k<high;k++){


arr[k]= arr[k+1];


}


arr[high]=tempArr;





for(int i =0;i<size;i++){


System.out.print(arr[i]+”   “);


}


}

        public static void main(String[] args) {


System.out.println(“请输入待排序数组,并请先输入数组个数”);


Scanner in=new Scanner(System.in);


int size = in.nextInt();


int[] num = new int[size];


for(int i =0;i<size;i++){


num[i]=in.nextInt();


}


halfInsertSort(num);


System.exit(0);


}

这里可能有点费解,
//把tempArr加入:

与前面的向后移动一个位子是一个意思,找到插入的位子,将这个位子之前的所有元素向前移动,将目标元素插入到这个位子上。

L[0]L[1,..,target,…n-1] 左移之后:

折半插入排序详解「终于解决」

折半插入排序详解「终于解决」

如果有什么写的不对的,还请指正

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/10719.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注