[21 Days Learning Challenge] Half Insertion Sort

​
​

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

插入排序

插入排序的基本思路是每次插入一个元素,Each trip is done one-to-one The placement of elements to be queued,直到全部插入完成.
Simply put, the small number is inserted before the large number,So that the entire array is sorted
A simple example is playing poker
Anyone who has played poker will have a certain understanding of insertion sort
Sorting playing cards means inserting the smaller cards one by one in front of the larger ones

代码

	public static void insertionSort(int[] arr) {
    
		if (arr == null || arr.length < 2) {
    
			return;
		}
		// 不只1个数
		for (int i = 1; i < arr.length; i++) {
     // 0 ~ i 做到有序
			for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
    
				swap(arr, j, j + 1);
			}
		}
	}
	public static void swap(int[] arr, int i, int j) {
    
		arr[i] = arr[i] ^ arr[j];
		arr[j] = arr[i] ^ arr[j];
		arr[i] = arr[i] ^ arr[j];
	}

折半插入排序

The halved insertion sort is a halved search based on the insertion sort,to quickly locate where you want to insert

low到heightRepresents the extent of the ordered region,minRepresents the smallest number in the unordered area
第一次遍历,有序区为[0,0],min=1;
将1Insert into the ordered area

The ordered area is expanded by one
通过二分查找,We can determine the ratio2The rightmost position of the small number
1后面即为2要插入的位置

到6了,
Same as binary search,We can quickly determine what to insert into5的后面,

Then follow the steps above,Arrange the entire array

时间复杂度

如果输入的元素刚好是反向有序的,Then you need to search the location every time,But the number of searches is less. 可以知道,Because the interval is reduced by half each time,
The maximum number of times the seek location can be obtained is log2 i量级,But since the number of moving elements doesn't change,时间复杂度依然是0(n²).

代码

public class BinaryInsert {
    

    public static void main(String[] args) {
    
        // input data
        int[] a = {
    11,34,20,10,12,35,41,32,43,14};
        // 数组下标从0开始,j初始为1,指向第二个元素
        for (int i = 1;i < a.length;i++){
    
            if (a[i] < a[i - 1]){
    
                // 使用temp记录当前元素的值
                int tmp = a[i];
                // 初始化变量
                int left = 0;
                int right = i - 1;
                // while循环作用：Use binary search to determine element location,并串出对应的位置
                while(left <= right){
    
                    // 取中间元素,以下写法防止数据量较大时发生溢出
                    int mid = (right - left) / 2 + left;
                    if(a[mid] > tmp){
    
                        // Elements to be queued are smaller,Narrows the search range to the left half
                        right = mid - 1;
                    }else {
    
                        // The elements to be queued are larger,Narrows the search range to the right half
                        left = mid + 1;
                    }
                }
                // 将待排元素放在对应的位置
                for (int j = i - 1;j >= right + 1;j--){
    
                    a[j + 1] = a[j];
                }
                a[right + 1] = tmp;
            }
        }
        // 查看排序结果
        for (int data : a){
    
            System.out.print(data + "\t");
        }
    }

}