折半(二分)插入排序
1#include <stdio.h>
2int main(){
3 int arr[] = {10,4,6,1,2,7,5,8,3,9};
4 int length = 10;
5 for(int i = 1; i < length; i++){ //逐个比较元素大小，并插入适当位置
6 int temp = arr[i];
7 int j = i-1;
8 // j 的条件必须是 >= 0
9 for(; j >= 0; j--){
10 if(arr[j] > temp)
11 arr[j+1] = arr[j];
12 else
13 break;
14 }
15 arr[j+1] = temp;
16 }
17
18 for(int i = 0; i < length; i++)
19 printf("%d\t", arr[i]);
20 // 输出:1 2 3 4 5 6 7 8 9 10
21}
我们再将插入排序优化一下。查找数据时，二分查找的速度是非常快的，所以我们使用二分查找来确定元素的插入位置；相较于使用 for 循环逐个比较元素大小，以此来确定插入位置，使用折半（二分）查找的插入排序算法的执行效率就提升了不少。
1#include <stdio.h>
2int main(){
3 int arr[] = {10,4,6,1,2,7,5,8,3,9};
4 int length = 10;
5 for(int i = 1; i < length; i++){
6 int start = 0; // 有序区域的起点
7 int end = i-1; // 有序区域的末尾
8 int mid = (start+end)/2;
9 int temp = arr[i];
10 while(start <= end){ // 折半查找
11 if(arr[mid] <= temp)
12 start = mid+1;
13 else
14 end = mid-1;
15 mid = (start+end)/2;
16 }
17 // 插入数据
18 for(int j = i; j > start; j--)
19 arr[j] = arr[j-1];
20 arr[start] = temp;
21 }
22 for(int i = 0; i < length; i++)
23 printf("%d\t", arr[i]);
24 // 输出:1 2 3 4 5 6 7 8 9 10
25}
PS：折半 <==> 二分
推荐阅读