数据结构 ----- 折半插入排序

​​​​

​ 折半插入排序
​

活动地址：CSDN21天学习挑战赛

一、折半插入排序

1.1 概念

折半插入排序（Binary Insertion Sort）是对插入排序算法的一种改进。所谓插入排序，就是不断的依次将元素插入前面已排好序的序列中。

1.2 查找过程

• 折半插入排序的基本思想跟直接插入排序基本一致，都是通过将元素一个个插入有序序列进行排序；
• 折半插入排序跟直接插入排序的区别在于寻找插入位置的方法，直接插入排序是由后往前一个个进行对比寻找合适的插入位置，而折半插入排序则是利用折半查找的思路寻找合适的插入位置；
• 因为折半插入排序是直接插入排序的优化版本，所以单纯看每一趟排序的结果跟直接插入排序的结果是一样的；

图 1.1

1.3 代码演示

1.3.1

• 建立一个数组，并将待排序元素传入数组；
• 建立一个排序方法，方法内传入所建立的数组；

图 1.2

1.3.2

• 跟直接插入排序一样，从第二个元素开始依次插入已排序的序列中，直到所有元素都处于有序区；（ 第一个元素默认在有序区，做对第一个元素的插入操作没有意义 ）
• 建立三个变量并初始化；
• 一个变量存储最小坐标，一个变量存储当前最大坐标，一个变量存储中间值坐标；
• 建立一个辅助变量，用于存储当前插入元素；

图 1.3

1.3.3

• 在 for 循环内部再建立一个循环，功能是用于查找插入位置；
• 给中间值赋初值，即最小坐标和最大坐标的和的一半；
• 然后拿待插入元素跟每次循环的中间元素的值进行对比，如果小于等于中间值就代表插入位置在中间坐标右边到最大坐标的范围内， 如果小于中间元素的值则代表在最小坐标到中间坐标的范围内；
• 最后跳出循环后对最大坐标进行自增 1 ，此时的最大坐标代表的是插入位置；

图 1.4 ##### 1.3.4 >* 确定好位置后将插入位置开始的所有元素进行后移一位，为插入元素腾出空间； >* 最后将待插入元素插入相应位置即排序结束；

图 1.5

1.4 代码测试

1. 在每一趟排序进行输出；
2. 对获得的排序进行确认；
3. 结论：代码可用无误；

图 1.6

1.5 代码分享

public class test {

    public static void main(String[] args){
       int[] arr = { 98 , 53 , 12 , 8 , 64 , 75 , 14 , 61};
        halfsort( arr );
        for (int j : arr) {
            System.out.print(j + " ");
        }
    }

    public static  void halfsort( int[] arr ) {
        for (int i = 1; i < arr.length; i++) {
            int mid;
            int low = 0 , high = i - 1;
            int temp = arr[i];
            while ( low <= high ){
                mid = ( low + high ) >>> 1;
                if ( arr[mid] <= temp ){
                    low = mid + 1;
                }else {
                    high = mid - 1;
                }
            }
            high++;
            for (int j = i; j > high ; j--) {
                arr[j] = arr[j - 1];
            }
            arr[high] = temp;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32