c++对插入排序的改进
发布时间：2010/7/29 10:24:41 来源：城市学习网 编辑：ziteng
其思想如下，插入排序中每次将本次取到的数据插入到已排序序列的时候，都会将有序序列中大于这个数据的元素依次向后移动一个单元，这个过程的时间复杂度就是n，有没有办法简化这个过程呢，其实有一种方法：因为待插入的序列是有序的，所以我们可以使用一个二分查询定位出新元素要插入的位置(插入到这个位置后，这个序列依然保持有序，这个操作的时间复杂度为logn)，知道这个位置之后就好办了，我们可以将这个位置后面的序列整块的向后移动一个位置，这个操作称为memmove—整块的移动内存单元(这样，移动元素的时间复杂度就变成1了)，因为这时候数组的位置已经腾出来了，我们可以将新的元素插入到指定位置(这个操作复杂度为1)。
因此，整个插入的操作时间复杂度为logn+2，常数项可以忽略，因此复杂度为logn，因为整个排序需要n次插入操作，那么整个算法的复杂度就为nlogn
从宏观上看，这个算法的时间复杂度为nlogn，当然具体的性能还要看memmove这个操作的效率。
一个C语言的实现如下
1 #include <ctype.h>
2 #include <string.h>
3
4 int binary_index(int *arr,int p,int q,int key){
5
6 int mid;
7 while(p <= q){
8 mid = (q + p) / 2;
9 if(arr[mid] < key){
10 p = mid + 1;
11 }else if(arr[mid] > key){
12 q = mid - 1;
13 }else{
14 return mid;
15 }
16 }
17 return p;
18
19 }
20 void insertion_sort_improved(int *arr,int len){
21 int i,j,key,k,move_len;
22 for(i = 1;i < len;i++){
23 j = i - 1;
24 key = arr[i];
25 k = binary_index(arr,0,j,key);
26 move_len = j - k + 1;
27 memmove(arr + (k + 1),arr + k,move_len * sizeof(int));
28 arr[k] = key;
29
30 }
31
32 }
