龙空技术网

好程序员Java教程分享5分钟了解折半插入排序

好程序员 90

前言:

现在姐妹们对“折半排序法例题”大概比较关怀,我们都想要分析一些“折半排序法例题”的相关内容。那么小编也在网上搜集了一些关于“折半排序法例题””的相关文章,希望兄弟们能喜欢,大家一起来了解一下吧!

好程序员Java教程分享5分钟了解折半插入排序,前言: 折半插入排序(Binary Insertion Sort)是对直接插入排序算法的一种改进。

插入排序思想介绍

折半插入排序与直接插入排序算法原理相同。只是,在向已排序的数据中插入数据时,采用来折半查找(二分查找)。先取已经排序的序列的中间元素,与待插入的数据进行比较,如果中间元素的值大于待插入的数据,那么待插入的数据属于数组的前半部分,否则属于后半部分。依次类推,不断缩小范围,确定要插入的位置。

算法说明:

待排序数据: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.private void binaryInsertSort(int arr[]){

2.

3. int low = 0;

4. int high = 0;

5. int m = 0;// 中间位置

6. for(int i = 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(int j=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. private void binaryInsertSort(int arr[]){

2.

3. int low = 0;

4. int high = 0;

5. int m = 0;// 中间位置

6. for(int i = 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(int j=i; j > high+1; j--){

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

20. }

21. arr[high+1] = temp;

22. }

23. }

总结

折半插入排序相对稳定,相对于直接插入排序,减少了比较次数;但是相对直接插入排序,移动次数不变。

标签: #折半排序法例题