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

各类排序方法在时间、空间复杂度及稳定性（通俗地讲，就是两个相等的数不会交换位置）方面各有优势：

对于插入排序，如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的次数，我们称为二分插入排序（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－