二分法排序(二分法排序流程圖)

各類排序方法在時間、空間復雜度及穩定性（通俗地講，就是兩個相等的數不會交換位置）方面各有優勢：

對于插入排序，如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的次數，我們稱為二分插入排序（binary inrt sort）。二分法插入排序是在插入排序（見前一篇文章）的基礎上，采用二分法搜索來確定插入新元素的正確位置。

當n較大時，二分插入排序的比較次數比直接插入排序的最差情況好得多，但比直接插入排序的最好情況要差，所當以元素初始序列已經接近升序時，直接插入排序比二分插入排序比較次數少。二分插入排序元素移動次數與直接插入排序相同，依賴于元素初始序列。

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

C代碼：

python代碼：

實現過程：外層循環控制循環次數，中層循環實現有序排列，內層循環實現查找插入

附C代碼：

#include <stdio.h>#include <stdlib.h>// 分類 -------------- 內部比較排序// 數據結構 ---------- 數組// 最差時間復雜度 ---- O(n^2)// 最優時間復雜度 ---- O(nlogn)// 平均時間復雜度 ---- O(n^2)// 所需輔助空間 ------ O(1)// 穩定性 ------------ 穩定void InrtionSortDichotomy(int A[], int n){ for (int i = 1; i < n; i++) { int get = A[i]; // 右手抓到一張撲克牌 int left = 0; // 拿在左手上的牌總是排序好的，所以可以用二分法 int right = i - 1; // 手牌左右邊界進行初始化 while (left <= right) // 采用二分法定位新牌的位置 { int mid = (left + right) / 2; if (A[mid] > get) right = mid - 1; el left = mid + 1; } for (int j = i - 1; j >= left; j--)// 將欲插入新牌位置右邊的牌整體向右移動一個單位 { A[j + 1] = A[j]; } A[left] = get; // 將抓到的牌插入手牌 }}int main(){ int A[] = { 5, 2, 9, 4, 7, 6, 1, 3, 8 };// 從小到大二分插入排序 int n = sizeof(A) / sizeof(int); InrtionSortDichotomy(A, n); printf("二分插入排序結果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf(" "); system("pau"); return 0;}

附python代碼：

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........el:............beg = mid ....#首先確定是否因為找到同值而提前終止....if list[i] == list[mid]:........list.inrt(mid, list[i])........list.pop(i + 1)....el:........if beg == end:............ #如果范圍內僅僅有一個值............if list[i] < list[beg]:................list.inrt(beg,list[i])............el:................list.inrt(beg+1, list[i])............list.pop(i + 1)........elif beg < end:............ #如果范圍內有兩值............if list[i] < list[beg]:................list.inrt(beg,list[i])............elif list[i] < list[end]:................list.inrt(end, list[i])............el:................list.inrt(end+1, list[i])............list.pop(i + 1)........el:............print("wrong, start at ",beg,', and end with ',end) print('after sort:',list)

－end－