折半插入排序

 1         /// <summary>
 2         /// 折半插入排序
 3         /// </summary>
 4         /// <param name="arr"></param>
 5         /// <returns></returns>
 6         public static int[] HalfInsertSort(int[] arr)
 7         {
 8             for (int i = 1; i < arr.Length; i++)
 9             {
10                 if (arr[i] >= arr[i - 1])
11                     continue;
12                 int low = 0;
13                 int high = i - 1; 
14                 int temp = arr[i];
15                 int j = i;
16 
17                 //二分法查找插入点
18                 while (low <= high)
19                 {
20                     int mid = (low + high) / 2; //中点在low
21                     if (temp > arr[mid])
22                         low = mid + 1;
23                     else if (temp < arr[mid])
24                         high = mid - 1;
25                     else
26                         break;
27                 }
28 
29                 //移动位置
30                 while(j > low)  //low == high，arr[low]即为插入点
31                 {
32                     arr[j] = arr[j - 1];
33                     --j;
34                 }
35                 arr[j] = temp;
36             }
37             return arr;
38         }
工欲善其事，必先利其器。