二分法插入排序

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

基本介紹

• 中文名：二分法插入排序
• 外文名：Binary Insert Sort
• 類型：算法
• 複雜度：O(nlgn)
• 性質：穩定性
• 特點：使用二分法尋找查找插入位置

算法思想簡單描述：

二分法沒有排序，只有查找。所以當找到要插入的位置時。移動必須從最後一個記錄開始，向後移動一位，再移動倒數第2位，直到要插入的位置的記錄移後一位。

複雜度分析

二分插入排序是穩定的與二分查找的複雜度相同；

最好的情況是當插入的位置剛好是二分位置 所用時間為O(log₂n);

最壞的情況是當插入的位置不在二分位置 所需比較次數為O(n)，無限逼近線性查找的複雜度。

S<=∑n「log₂n「-2^n「log₂n「+1

k= 1

平均時間O(n^2)

實施步驟

1、二分法查找插入位置

如果R<R[m]成立，那右指針就要向左移動中間指針一位，否則，左指針要向右移動中間指針一位。反覆查找，直到左指針大於右指針時停止。

2、後移，有點迷惑，什麼時候需要後移呢？有哪些記錄需要移動呢？

雖然我們很清楚的知道，我們需要後移那些排序碼大於R的記錄，但難免會問自己這樣幾個問題。其實它相當於需要移動從i-1到左指針的記錄。

3、插入

由1中得到的左指針其實就是元素要插入的位置。

相關代碼

C源碼

/* 二分法插入排序的算法源程式*/#include<stdio.h>#define MAXNUM 100typedef int KeyType;typedef int DataType;typedef struct{    KeyType key; /* 排序碼欄位 */    /*DataType info; 記錄的其它欄位 */} RecordNode;typedef struct{    int n; /* n為檔案中的記錄個數，n<MAXNUM */    RecordNode record[MAXNUM];} SortObject;void binSort(SortObject * pvector) /* 按遞增序進行二分法插入排序 */{    int i, j, left, mid, right;    RecordNode temp;    RecordNode *data = pvector->record;    for( i = 1; i < pvector->n; i++ )    {        temp = data[i];        left = 0;        right = i-1; /* 置已排序區間的下、上界初值 */        while (left <= right)        {            mid = (left + right)/2; /* mid指向已排序區間的中間位置 */            if (temp.key < data[mid].key)                right = mid-1; /* 插入元素應在左子區間 */            else left = mid+1; /* 插入元素應在右子區間 */        }        for (j = i-1; j >= left; j--)            data[j+1] = data[j]; /* 將排序碼大於ki的記錄後移 */        if (left != i) data[left] = temp;    }}SortObject vector= {10, 49,38,65,97,76,13,27,49,50,101};int main(){    int i;    binSort(&vector);    for(i = 0; i < vector.n; i++)    printf("%d ", vector.record[i]);    getchar();    return 0;}

Python源碼

# 二分法插入排序是在插入排序的基礎上，使用二分法查找將元素插入的方法# 基本原理：（升序）# 1.將元素依次放入有序序列中# 2.取出待排序元素，與有序序列的前半段進行比較# 3.縮小有序序列範圍，進一步劃分比較，直至範圍內僅有1或2個數字# 4.將插入值與範圍進行比較# 3.重複實現升序# 實現過程：外層循環控制循環次數，中層循環實現有序排列，內層循環實現查找插入import random# 生成序列Range = 10Length = 5list = random.sample(range(Range),Length)print('before sort:',list)# 元素插入for i in range(1,Length):            #從第2個元素開始，插入到前一部分元素中    beg,end = 0,i-1                  #定義插入範圍    mid = (beg + end) // 2           #定義二分/中間邊界    while beg < end:                #當邊界順序時，進行二分比較        mid = (beg + end) // 2        if mid == beg:               #如果中間值與邊界相等，則邊界已確定，結束二分            break        #在確定中間與邊界不相等時，對邊界繼續縮小        if list[i] == list[mid]:            break        elif list[i]<list[mid]:            end = mid        else:            beg = mid    #首先確定是否因為找到同值而提前終止    if list[i] == list[mid]:        list.insert(mid, list[i])        list.pop(i + 1)    else:        if beg == end:              #如果範圍內僅僅有一個值            if list[i] < list[beg]:                list.insert(beg,list[i])            else:                list.insert(beg+1, list[i])            list.pop(i + 1)        elif beg < end:             #如果範圍內有兩值            if list[i] < list[beg]:                list.insert(beg,list[i])            elif list[i] < list[end]:                list.insert(end, list[i])            else:                list.insert(end+1, list[i])            list.pop(i + 1)        else:            print("wrong, start at ",beg,', and end with ',end)print('after sort:',list)

java源碼

public static void advanceInsertSortWithBinarySearch(int[] arr) {    for (int i = 1; i < arr.length; i++) {        int temp = arr[i];        int low = 0, high = i - 1;        int mid = -1;        while (low <= high) {                        mid = low + (high - low) / 2;                        if (arr[mid] > temp) {                               high = mid - 1;                        } else { // 元素相同時，也插入在後面的位置                                low = mid + 1;                        }                }                for(int j = i - 1; j >= low; j--) {                        arr[j + 1] = arr[j];                }                arr[low] = temp;        }}