Java实现直接插入排序和折半插入排序算法示例

直接插入排序​
1 排序思想：

将待排序的记录ri插入到已经排好序的记录r1，r2，……，r（n-1）中。

对于一个随机序列而言，就是从第二个元素开始，依次将这个元素插入到它之前的元素中的相应位置。它之前的元素已经排好序。

第1次排序：将第2个元素插入到前边的有序列表（此时前边只有一个元素，当然是有序的），之后，这个序列的前2个元素就是有序的了。
第2次排序：将第3个元素插入到前边长度为2的有序列表，使得前2个元素是有序的。
以此类推，直到将第n个元素插入到前面长度为（n-1）的有序列表中。

2 算法实现：

// 直接插入排序
void straight_insert_sort(int num[], int len){
 int i,j,key;
 for(j=1;j<len;j++){
  key=num[j];
  i=j-1;
  while(i>=0&&num[i]>key){
   num[i+1]=num[i];
   i--;
  }
  num[i+1]=key;
 }
}

3 性能分析：

3.1 空间复杂度：如上代码，使用了一个辅助单元key，空间复杂度为o(1)

3.2 时间复杂度：

3.2.1 最好情况：待排序记录已经是有序的，则一趟排序，关键字比较1次，记录移动2次。则整个过程

比较次数为

记录移动次数为

时间复杂度o(n)

3.2.2 最坏情况：待排序记录已经是逆序的，则一趟排序，关键字比较次数i次（从i-1到0），记录移动（i+2）次。整个过程

比较次数为

记录移动次数为

时间复杂度o(n^2)

3.2.3 平均时间复杂度：o(n^2)

3.3 稳定性：稳定

折半插入排序
1 排序思想：

直接排序的基础上，将待排序的记录ri插入到已经排好序的记录r1，r2，……，r（n-1）中，由于记录r1，r2，……，r（n-1）已经排好序，所以在查找插入位置时可采用“折半查找”。

2 算法实现：

// 折半插入排序
void binary_insert_sort(int num[], int len){
 int i,j,key,low,high,mid;
 for(i=1;i<len;i++){
  key=num[i];
  low=0;
  high=i-1;
  mid=(low+high)/2;
  // 寻找插入点，最终插入点在low
  while(low<=high){
   if(key<num[mid])
    high=mid-1;
   else 
    low=mid+1;
   mid=(low+high)/2;
  }
  // 移动记录
  for(j=i;j>low;j--){
   num[j]=num[j-1];
  }
  // 插入记录
  num[low]=key;
 }
}

3 性能分析：

3.1 空间复杂度：如上代码，使用了一个辅助单元key，空间复杂度为o(1)

3.2 时间复杂度：虽然折半查找减少了记录比较次数，但没有减少移动次数，因此时间复杂度同直接查找算法。

3.2.1 最好情况：时间复杂度o(n)

3.2.2 最坏情况：时间复杂度o(n^2)

3.2.3 平均时间复杂度：o(n^2)

3.3 稳定性：稳定