插入排序之2路插入排序及变种算法思考

　　2-路插入排序算法是在折半插入排序的基础之上进行的改进，主要贡献是减少了排序过程中移动记录的次数，不足的地方是需要n个记录的辅助空间。

　　具体算法思路如下：

　　　　另设一个与含有n个数据的待排数据序列同类型的数组d，把待排序列的第一个元素（根据自己的数据结构来确定）赋值给d[0]，并将d[0]看做是在排好序的序列的中间位置，然后将剩下的n-1个序列一次插入到d[0]之前或之后的有序数据序列（将数组d看做循环向量）中。

　　相关变量定义如下：

View Code

1 #define MAXSIZE 20
2 typedef int KeyType;
3 typedef struct {
4     KeyType key;
5 }RedType;
6 typedef struct{
7     RedType r[MAXSIZE+1];
8     int length;
9 }Sqlist;

　　2-路插入排序算法代码：

 1 /* 2 Path Insert Sort */ 
 2 void twoPathInsertSort(Sqlist &L){
 3     if(!L.length)
 4         return;
 5     KeyType d[MAXSIZE]={0};
 6     // 设置第一个记录和最后一个记录的指针 
 7     int first=0;
 8     int final=0;
 9     // 设置d[0]为哨兵元素 
10     d[0]=L.r[1].key;
11     int i;
12     for(i=2; i<= L.length; ++i){
13         if(LT(L.r[i].key,d[first])){  // 不需移动元素 
14             first = (first-1+L.length)%L.length;
15             d[first] = L.r[i].key ;
16         }else if(LT(d[final],L.r[i].key)){ // 不需要移动元素 
17             final = final+1 ;
18             d[final] = L.r[i].key;
19         }else {    // 中间插入，需要移动元素 
20             int j=final-1;
21             final += 1;
22             d[final] = d[final-1];
23             while(LT(L.r[i].key,d[j])){
24                 d[j+1] = d[j];
25                 --j;
26             }
27             d[j+1] = L.r[i].key;
28         }
29     }
30     // 将辅助数组的数据按序复制到表L 
31     for(i=1; i<= L.length; ++i){
32         L.r[i].key = d[first%L.length];
33         ++first;
34     }
35 }

　　此算法相对折半插入算法来说，能减少移动记录的次数，但是不能绝对避免移动记录（除非是已排好序的数据序列），移动记录的次数约为N^2/8。根据由折半插入排序改进而来的2路插入排序，我不由自主的就想到了能不能来个2-路快速插入排序，即结合折半插入排序、快速排序优点的排序。

 1 void twoPQInsertSort(Sqlist &L){
 2     int i=1;
 3     int j=L.length;
 4     L.r[0].key = L.r[i].key;
 5     // Quick insert sort from two path 
 6     while(i<j){
 7         while(LE(L.r[0].key,L.r[j].key) && i<j){
 8             // Binary insert 
 9             int left=j+1;
10             int right=L.length;
11             while( left <= right ){
12                 int m = (left+right)/2 ;
13                 if(LT(L.r[j].key,L.r[m].key))
14                     right = m - 1;
15                 else
16                     left = m + 1;
17             }
18             KeyType tmp = L.r[j].key;
19             int tmpj;
20             for(tmpj=j; tmpj <= right-1; ++tmpj){
21                 L.r[tmpj].key = L.r[tmpj+1].key;
22             }
23             L.r[right].key = tmp;
24             --j;
25         }
26         L.r[i].key = L.r[j].key;
27         
28         while(LE(L.r[i].key,L.r[0].key) && i<j){
29             // Binary insert 
30             int left = 1;
31             int right = i-1;
32             while(left<=right){
33                 int m = (left+right)/2;
34                 if(LT(L.r[i].key,L.r[m].key))
35                     right = m - 1;
36                 else
37                     left = m + 1;
38             }
39             int tmpi;
40             int tmp = L.r[i].key;
41             for(tmpi=i-1; tmpi>= right+1; --tmpi){
42                 L.r[tmpi+1].key = L.r[tmpi].key;
43             }
44             L.r[right+1].key = tmp;
45             ++i;
46         }
47         L.r[j].key = L.r[i].key;
48         
49     }
50     L.r[j].key = L.r[0].key;
51 }

　　在2-路快速插入排序中，相比算法一,2-路插入排序,来说，节约了n-2个辅助存储空间，但是增加了最大n-1个记录的移动，相对0(N^2)的复杂度来说，可以忽略，然后时间复杂度并没有明显下降。在最坏的情况下（当选取的哨兵元素为数据序列中最大或最小的元素时），2-路快速插入排序退化为折半插入排序。

可运行程序源码：

View Code

  1 /*
  2 *    2-road Insert sort algorithm
  3 *    Post at 2012.10.8
  4 */
  5 #include <stdio.h>
  6 #include <stdlib.h>
  7 #include <string.h>
  8 
  9 #define MAXSIZE 20
 10 typedef int KeyType;
 11 typedef struct {
 12     KeyType key;
 13 }RedType;
 14 typedef struct{
 15     RedType r[MAXSIZE+1];
 16     int length;
 17 }Sqlist;
 18 
 19 
 20 void initSqlist(Sqlist &L){
 21     printf("input the sort record length:");
 22     if(!scanf("%d",&L.length) && L.length <= MAXSIZE ){
 23         printf("input error!\n");
 24         exit(-1);
 25     }
 26     int i;
 27     for(i=1; i<= L.length; ++i){
 28         //printf("input the record:");
 29         scanf("%d",&L.r[i].key);
 30     }
 31 } 
 32 
 33 bool LT(KeyType r1, KeyType r2){
 34     if(r1<r2){
 35         return true;
 36     }else{
 37         return false;
 38     }
 39 }
 40 
 41 bool LE(KeyType r1, KeyType r2){
 42     if(r1<=r2){
 43         return true;
 44     }else{
 45         return false;
 46     }
 47 }
 48 
 49 /* 2 Path Insert Sort */ 
 50 void twoPathInsertSort(Sqlist &L){
 51     if(!L.length)
 52         return;
 53     KeyType d[MAXSIZE]={0};
 54     // 设置第一个记录和最后一个记录的指针 
 55     int first=0;
 56     int final=0;
 57     // 设置d[0]为哨兵元素 
 58     d[0]=L.r[1].key;
 59     int i;
 60     for(i=2; i<= L.length; ++i){
 61         if(LT(L.r[i].key,d[first])){  // 不需移动元素 
 62             first = (first-1+L.length)%L.length;
 63             d[first] = L.r[i].key ;
 64         }else if(LT(d[final],L.r[i].key)){ // 不需要移动元素 
 65             final = final+1 ;
 66             d[final] = L.r[i].key;
 67         }else {    // 中间插入，需要移动元素 
 68             int j=final-1;
 69             final += 1;
 70             d[final] = d[final-1];
 71             while(LT(L.r[i].key,d[j])){
 72                 d[j+1] = d[j];
 73                 --j;
 74             }
 75             d[j+1] = L.r[i].key;
 76         }
 77     }
 78     // 将辅助数组的数据按序复制到表L 
 79     for(i=1; i<= L.length; ++i){
 80         L.r[i].key = d[first%L.length];
 81         ++first;
 82     }
 83 }
 84 
 85 /* 2 path quick insert sort ,has some problem not deal with*/
 86 void twoPQInsertSort(Sqlist &L){
 87     int i=1;
 88     int j=L.length;
 89     L.r[0].key = L.r[i].key;
 90     // Quick insert sort from two path 
 91     while(i<j){
 92         while(LE(L.r[0].key,L.r[j].key) && i<j){
 93             // 下面是折半插入代码 
 94             int left=j+1;
 95             int right=L.length;
 96             while( left <= right ){
 97                 int m = (left+right)/2 ;
 98                 if(LT(L.r[j].key,L.r[m].key))
 99                     right = m - 1;
100                 else
101                     left = m + 1;
102             }
103             KeyType tmp = L.r[j].key;
104             int tmpj;
105             for(tmpj=j; tmpj <= right-1; ++tmpj){
106                 L.r[tmpj].key = L.r[tmpj+1].key;
107             }
108             L.r[right].key = tmp;
109             --j;
110         }
111         L.r[i].key = L.r[j].key;
112         
113         while(LE(L.r[i].key,L.r[0].key) && i<j){
114             // 下面是折半插入代码 
115             int left = 1;
116             int right = i-1;
117             while(left<=right){
118                 int m = (left+right)/2;
119                 if(LT(L.r[i].key,L.r[m].key))
120                     right = m - 1;
121                 else
122                     left = m + 1;
123             }
124             int tmpi;
125             int tmp = L.r[i].key;
126             for(tmpi=i-1; tmpi>= right+1; --tmpi){
127                 L.r[tmpi+1].key = L.r[tmpi].key;
128             }
129             L.r[right+1].key = tmp;
130             ++i;
131         }
132         L.r[j].key = L.r[i].key;
133         
134     }
135     L.r[j].key = L.r[0].key;
136 }
137 
138 void printSqlist(Sqlist &L){
139     printf("Sorted Sqlist as follow:");
140     int i;
141     for(i=1; i <= L.length; ++i){
142         printf(" %d ",L.r[i].key);
143     }
144     printf("\n");
145 }
146 
147 
148 int main(int argc, char **argv){
149     Sqlist L;
150     L.length = 0;
151     initSqlist(L);
152     //twoPathInsertSort(L);    
153     twoPQInsertSort(L);
154     printSqlist(L);
155     return 0;
156 }