Java折半插入排序怎么实现
Java折半插入排序怎么实现
这篇文章主要讲解了“Java折半插入排序怎么实现”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“Java折半插入排序怎么实现”吧！
插入排序思想介绍
折半插入排序与直接插入排序算法原理相同。只是，在向已排序的数据中插入数据时，采用来折半查找（二分查找）。先取已经排序的序列的中间元素，与待插入的数据进行比较，如果中间元素的值大于待插入的数据，那么待插入的数据属于数组的前半部分，否则属于后半部分。依次类推，不断缩小范围，确定要插入的位置。
算法说明：
待排序数据：2，1，6，7，4
取第一个元素作为有序表，剩余的元素作为无序表
其中有序表：2；无序表：1，6，7，4
第一次比较，从无序表中取出第一个数 1，与中间值2比较，1<2，1插到2的前面，得到
有序表：1，2；无序表：6，7，4
第二次比较，从无序表中取出第一个数 6，与中间值1比较，6>1，要放在1的后面，再与后半区（有序表：2）的中间值2比较，6>2，6插入到2的后面，得到
有序表：1，2，6；无序表：7，4
第三次比较，从无序表中取出第一个数 7，与中间值2比较，7>2，7放在2后面，再与后半区（有序表：6）的中间值6比较，7>6，7放在6后面，得到
有序表：1，2，6，7；无序表：4
第四次比较，从无序表中取出第一个数 4，与中间值2比较，4>2，4放在2后面，再与后半区（有序表:6,7）的中间值6比较，4<6，4放在6前面，最终得到：
1，2，4，6，7
折半插入排序的代码实现
1.privatevoidbinaryInsertSort(intarr[]){
2.
3.intlow=0;
4.inthigh=0;
5.intm=0;//中间位置
6.for(inti=1;i<arr.length;i++){
7.low=0;
8.high=i-1;
9.while(low<=high){
10.m=(low+high)/2;
11.if(arr[m]>arr[i])
12.high=m-1;
13.else
14.low=m+1;
15.}
16.//统一移动元素，将待排序元素插入到指定位置
17.temp=arr[i];
18.for(intj=i;j>high+1;j--){
19.arr[j]=arr[j-1];
20.}
21.arr[high+1]=temp;
22.}
23.}
总结
折半插入排序相对稳定，相对于直接插入排序，减少了比较次数；但是相对直接插入排序，移动次数不变。
插入排序思想介绍
折半插入排序与直接插入排序算法原理相同。只是，在向已排序的数据中插入数据时，采用来折半查找（二分查找）。先取已经排序的序列的中间元素，与待插入的数据进行比较，如果中间元素的值大于待插入的数据，那么待插入的数据属于数组的前半部分，否则属于后半部分。依次类推，不断缩小范围，确定要插入的位置。
算法说明：
待排序数据：2，1，6，7，4
取第一个元素作为有序表，剩余的元素作为无序表
其中有序表：2；无序表：1，6，7，4
第一次比较，从无序表中取出第一个数 1，与中间值2比较，1<2，1插到2的前面，得到
有序表：1，2；无序表：6，7，4
第二次比较，从无序表中取出第一个数 6，与中间值1比较，6>1，要放在1的后面，再与后半区（有序表：2）的中间值2比较，6>2，6插入到2的后面，得到
有序表：1，2，6；无序表：7，4
第三次比较，从无序表中取出第一个数 7，与中间值2比较，7>2，7放在2后面，再与后半区（有序表：6）的中间值6比较，7>6，7放在6后面，得到
有序表：1，2，6，7；无序表：4
第四次比较，从无序表中取出第一个数 4，与中间值2比较，4>2，4放在2后面，再与后半区（有序表:6,7）的中间值6比较，4<6，4放在6前面，最终得到：
1，2，4，6，7
折半插入排序的代码实现
1.privatevoidbinaryInsertSort(intarr[]){
2.
3.intlow=;
4.inthigh=;
5.intm=;//中间位置
6.for(inti=1;i<arr.length;i++){
7.low=;
8.high=i-1;
9.while(low<=high){
10.m=(low+high)/2;
11.if(arr[m]>arr[i])
12.high=m-1;
13.else
14.low=m+1;
15.}
16.//统一移动元素，将待排序元素插入到指定位置
17.temp=arr[i];
18.for(intj=i;j>high+1;j--){
19.arr[j]=arr[j-1];
20.}
21.arr[high+1]=temp;
22.}
23.}
感谢各位的阅读，以上就是“Java折半插入排序怎么实现”的内容了，经过本文的学习后，相信大家对Java折半插入排序怎么实现这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是恰卡编程网，小编将为大家推送更多相关知识点的文章，欢迎关注！
