C语言之 插入排序的改良[网络技术]

根源:博客园
插入排序的性能大家都理解了,时间复杂度是O(n2),有没有办法晋升他的效率呢? 这里有一个办法,在宏观上可以将插入排序的时间复杂度降低到nlogn.

　　其思惟以下,插入排序中每次将本次取到的数据插入到已排序序列的时刻,城市将有序序列中大于这个数据的元素顺次向后移动一个单元,这个历程的时间复杂度就是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　}