插入排序之一 直接插入排序

Admin

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，它的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。时间复杂度为O(n^2)。理解：依次将每个待排序的记录插入到一个有序序列的合适位置。插入的位置是和有序序列的每一个元素进行比较，然后确定的。

1. void CInsertionSort::StraightInsertion(void)
   
2. {
   
3.     //元素0是哨兵。
   
4.     const int count = 9;
   
5.     int L[count] = {0, 49, 38, 65, 97, 76, 13, 27, 49};
   
6.     //对顺序表作直接插入排序。
   
7.     for (int i = 2; i < count; i++)
   
8.     {
   
9.         if (L[i] < L[i - 1])
   
10.         {
    
11.             L[0] = L[i];
    
12.             int j = i - 1;
    
13.             do
    
14.             {
    
15.                 L[j + 1] = L[j];
    
16.                 j--;
    
17.             } while (L[0] < L[j]);
    
18.             L[j + 1] = L[0];
    
19.         }
    
20.     }
    
21.     //打印排序结果。
    
22.     for (int i = 0; i < count; ++ i)
    
23.     {
    
24.         cout << L[i] << "\t";
    
25.     }
    
26.     cout << endl;
    
27. }

复制代码

默认循环最初的有序序列只有一个元素。