【AU】插入排序之 折半插入排序

文章目錄

• 折半插入排序
• • • 時間複雜度
    • 空間複雜度
    • 适用性
    • 穩定性
    • 代碼

折半插入排序

時間複雜度

O(n2)

減少了元素比較次數O(nlog2n)，未減少元素的移動次數

空間複雜度

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();
	}
}