排序算法第二篇——折半插入排序

算法描述：

在上一篇插入排序算法中，已经提到，插入排序的核心是在有序的集合中找到要插入的位置。所以，在这里介绍一种对插入排序的改进算法，即折半插入排序。折半插入排序是指利用折半查找的算法，在有序集合中找到要插入的位置。

Java代码：

<span style="font-size: 18px;">package ljp.sort.insert;

public class InsertSortDemo02 {
	private int[] list;

	public InsertSortDemo02(int[] list) {
		this.list = list;
	}

	// 将i位置的元素插入到j位置
	public void insert(int i, int j) {
		if (i != j) {
			int temp = list[i];
			for (int k = i; k > j; k--) {
				list[k] = list[k - 1];
			}
			list[j] = temp;
		}
	}

	public void sort() {
		for (int i = 1; i < list.length; i++) {
			int start = 0;
			int end = i - 1;
			if (list[i] < list[i - 1]) {
				int j = i;
				while (end >= start) {
					j = (start + end) / 2;
					if (list[i] > list[j]) {
						start = j + 1;
						if (start < list.length && list[i] < list[start]) {
							j=start;
							break;
						}
					} else if (list[i] < list[j]) {
						end = j - 1;
						if (end > 0 && list[i] > list[j - 1]) {
							break;
						}
					} else {
						break;
					}
				}
				insert(i, j);
			}
			System.out.println("第" + i + "次排序：");
			display();
		}
	}

	public void display() {
		for (int i : list) {
			System.out.print(i + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		int[] list = new int[10];
		for (int i = 0; i < list.length; i++) {
			list[i] = (int) (Math.random() * 1000);
		}
		InsertSortDemo02 sort = new InsertSortDemo02(list);
		System.out.println("排序前：");
		sort.display();
		sort.sort();
	}

}
</span>

运行结果：

排序前：
719 660 723 463 586 925 971 922 544 890
第1次排序：
660 719 723 463 586 925 971 922 544 890
第2次排序：
660 719 723 463 586 925 971 922 544 890
第3次排序：
463 660 719 723 586 925 971 922 544 890
第4次排序：
463 586 660 719 723 925 971 922 544 890
第5次排序：
463 586 660 719 723 925 971 922 544 890
第6次排序：
463 586 660 719 723 925 971 922 544 890
第7次排序：
463 586 660 719 723 922 925 971 544 890
第8次排序：
463 544 586 660 719 723 922 925 971 890
第9次排序：
463 544 586 660 719 723 890 922 925 971
时间复杂度分析：由于二分查找的时间复杂度为O(log2n)，所以折半插入排序算法的复杂度为O(nlog2n)。

稳定性分析：有排序算法稳定性概念可知，折半插入排序算法是稳定的。