[数据结构与算法]【AU】插入排序之 折半插入排序

折半插入排序

时间复杂度

O(n²)

减少了元素比较次数O(nlog₂n)，未减少元素的移动次数

空间复杂度

O(1)
辅助空间为 常数个辅助单元

适用性

顺序存储（因为应用了折半查找）

稳定性

稳定！

代码

import java.util.Scanner;

public class BInsert {

	public static void sort(int []list,int n) {
		int i,j,low,high,mid;
		for(i=2;i<=n;i++) {
			list[0]=list[i];
			low=1;
			high=i-1;
			while(low<=high) {
				mid=(low+high)/2;
				if(list[mid]>list[0]) {
					high=mid-1;
				}else {
					low=mid+1;
				}
			}
			for(j=i-1;j>=high+1;--j) {
				list[j+1]=list[j];
			}
			list[j+1]=list[0];
		}		
	}
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int []list=new int[n+1];
		for(int i=1;i<=n;i++) {
			list[i]=sc.nextInt();
		}
		sort(list,n);
		for(int i=1;i<=n;i++) {
			System.out.print(list[i]+"  ");
		}
		sc.close();
	}
}