直接插入排序

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置后

重复步骤2~5

  1 // 参考白话经典算法之直接插入排序的思想
  2 #include <stdio.h>
  3 
  4 void SwapValue(int *OperatorA, int *OperatorB)
  5 {
  6     if ((NULL == OperatorA) || (NULL == OperatorB))
  7     {
  8         printf ("Invalid Parameter(s)!\n");
  9         return;
 10     }
 11 
 12     if ((*OperatorA) != (*OperatorB))
 13     {
 14         *OperatorA ^= *OperatorB;
 15         *OperatorB ^= *OperatorA;
 16         *OperatorA ^= *OperatorB;
 17     }
 18 }
 19 
 20 void InsertSort(int *a, int N)
 21 {
 22     if ((NULL == a) || (N <= 0))
 23     {
 24         printf ("Invalid Parameter(s)!\n");
 25         return;
 26     }
 27 
 28     for (int i = 1; i < N; ++i)
 29     {
 30         int j;
 31 
 32         for (j = i-1; j >= 0; --j)
 33         {
 34             if (a[j] <= a[i])
 35             {
 36                 break;
 37             }
 38         }
 39 
 40         int nTemp = a[i];
 41 
 42         for (int k = i - 1; k > j; --k)
 43         {
 44             a[k+1] = a[k];
 45         }
 46 
 47         a[j+1] = nTemp;
 48     }
 49 }
 50 
 51 // 优化一，若在a[i]本就与a[0...i-1]有序则直接跳入下论循环
 52 void InsertSort1(int *a, int N)
 53 {
 54     if ((NULL == a) || (N <= 0))
 55     {
 56         printf ("Invalid Parameter(s)!\n");
 57         return;
 58     }
 59 
 60     for (int i = 1; i < N; ++i)
 61     {
 62         if (a[i] < a[i-1])
 63         {
 64             int j;
 65 
 66             for (j = i-1; j >= 0; --j)
 67             {
 68                 if (a[j] <= a[i])
 69                 {
 70                     break;
 71                 }
 72             }
 73 
 74             int nTemp = a[i];
 75 
 76             for (int k = i - 1; k > j; --k)
 77             {
 78                 a[k+1] = a[k];
 79             }
 80 
 81             a[j+1] = nTemp;
 82         }
 83     }
 84 }
 85 
 86 // 优化二，将搜索和移位和并在一起实现
 87 void InsertSort2(int *a, int N)
 88 {
 89     if ((NULL == a) || (N <= 0))
 90     {
 91         printf ("Invalid Parameter(s)!\n");
 92         return;
 93     }
 94 
 95     for (int i = 1; i < N; ++i)
 96     {
 97         if (a[i] < a[i-1])
 98         {
 99             int nTemp = a[i];
100 
101             for (int j = i - 1; (j >= 0) && (a[j] > nTemp); --j)
102             {
103                 SwapValue (&a[j+1], &a[j]);
104             }
105         }
106     }
107 }
108 
109 int main(void)
110 {
111     int a1[9] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
112     int a2[9] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
113     int a3[9] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
114 
115     InsertSort (a1, 9);
116     InsertSort1 (a2, 9);
117     InsertSort2 (a3, 9);
118 
119     for (int i = 0; i < 9; ++i)
120     {
121         printf ("%d ", a1[i]);
122     }
123 
124     printf ("\n");
125 
126     for (int i = 0; i < 9; ++i)
127     {
128         printf ("%d ", a2[i]);
129     }
130 
131     printf ("\n");
132 
133     for (int i = 0; i < 9; ++i)
134     {
135         printf ("%d ", a3[i]);
136     }
137 
138     printf ("\n");
139 
140     return 0;
141 }