插入排序之三 2-路插入排序

Admin

2-路插入排序是在折半插入排序的基础上再改进之，其目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。时间复杂度为O(n^2)。理解：所谓的2-路，是指优先插入在序列前面或后面，然后再考虑插入到中间。

1. void CInsertionSort::Path2Insertion(void)
   
2. {
   
3.     //元素0是哨兵。
   
4.     const int count = 9, length = count -1;
   
5.     int L[count] = {0, 49, 38, 65, 97, 76, 13, 27, 49};
   
6.     //对顺序表L作2-路插入排序。
   
7.     int d[length] = { 0 };
   
8.     d[0] = L[1];//L中D的第一个记录为d中排好序的记录。
   
9.     int first = 0, final = 0;//first、final分别指示d中排好序的记录的第1个和最后1个记录的位置。
   
10.     for (int i = 2; i <= length; ++i)//依次将L的第2个～最后一个记录插入d中。
    
11.     {
    
12.         if (L[i] < d[first])//待插入记录小于d中最小值，插入到d[first]之前（不需移动d数组的元素）。
    
13.         {
    
14.             first = (first - 1 + length) % length;
    
15.             d[first] = L[i];
    
16.         }
    
17.         else if (L[i] > d[final])//待插入记录大于d中最小值，插入到d[final]之后（不需移动d数组的元素）。
    
18.         {
    
19.             final = final + 1;
    
20.             d[final] = L[i];
    
21.         }
    
22.         else//待插入记录大于d中最小值，小于d中最大值，插入到d的中间（需要移动d数组的元素）。
    
23.         {
    
24.             int j = final ++;//移动d尾部元素以便按序插入记录。
    
25.             while (L[i] < d[j])
    
26.             {
    
27.                 d[(j + 1) % length] = d[j];
    
28.                 j = (j - 1 + length) % length;
    
29.             }
    
30.             d[j + 1] = L[i];
    
31.         }
    
32.     }
    
33.     for (int i = 1; i <= length; i ++)//循环把d赋给L。
    
34.     {
    
35.         L[i] = d[(i + first - 1) % length];//线性关系。
    
36.     }
    
37.     //打印排序结果。
    
38.     for (int i = 0; i <= length; ++ i)
    
39.     {
    
40.         cout << L[i] << "\t";
    
41.     }
    
42.     cout << endl;
    
43. }

复制代码

通过巧妙的取余运算，找到正确的插入位置。要想理解算法，一定要将数值代入到程序中，用脑子来运算这段代码。只能说这个取余运算很巧妙。