二分排序

二分排序是指利用二分法的思想對插入排序進行改進的一種插入排序算法，不同於二叉排序，可以利用數組的特點快速定位指定索引的元素。

基本介紹

• 中文名：二分插入排序
• 性質：排序算法
• 利用原理：二分法
• 用途：快速插入排序
• 區別：與二叉排序完全不同

簡介

算法思想

二分法插入排序是在插入第i個元素時，對前面的0～i-1元素進行折半，先跟他們中間的那個元素比，如果小，則對前半再進行折半，否則對後半進行折半，直到left>right，然後再把第i個元素前1位與目標位置之間的所有元素後移，再把第i個元素放在目標位置上。

代碼示例

以下代碼源自java API源碼中TimSort。

private static <T> void binarySort(T[] a, int lo, int hi, int start,

Comparator<? super T> c) {

assert lo <= start && start <= hi;

if (start == lo)

start++;

for ( ; start < hi; start++) {

T pivot = a[start];

// Set left (and right) to the index where a[start] (pivot) belongs

int left = lo;

int right = start;

assert left <= right;

/*

* Invariants:

* pivot >= all in [lo, left).

* pivot < all in [right, start).

*/

while (left < right) {

int mid = (left + right) >>> 1;

if (c.compare(pivot, a[mid]) < 0)

right = mid;

else

left = mid + 1;

}

assert left == right;

/*

* The invariants still hold: pivot >= all in [lo, left) and

* pivot < all in [left, start), so pivot belongs at left. Note

* that if there are elements equal to pivot, left points to the

* first slot after them -- that's why this sort is stable.

* Slide elements over to make room for pivot.

*/

int n = start - left; // The number of elements to move

// Switch is just an optimization for arraycopy in default case

switch (n) {

case 2: a[left + 2] = a[left + 1];

case 1: a[left + 1] = a[left];

break;

default: System.arraycopy(a, left, a, left + 1, n);

}

a[left] = pivot;

}

}

分析

二分排序的時間複雜度是O(n^2)，

空間複雜度O(1)，是穩定排序。