插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。插入排序包括：直接插入排序，二分插入排序，希尔排序等。

直接插入排序：

1         private static void InsertSort(int[] inputArray) 2         { 3             for (int i = 1; i < inputArray.Length; i++) 4             { 5                 int record = i; 6                 for (int j = i-1 ; j >= 0; j--) 7                 { 8                     if (inputArray[j] > inputArray[record]) 9                     {10                         inputArray[j] = inputArray[j] + inputArray[record];11                         inputArray[record] = inputArray[j] - inputArray[record];12                         inputArray[j] = inputArray[j] - inputArray[record];13                         record = j;14                     }15                 }16             }17         }

二分插入排序：

1         private static void BinaryInsertSort(int[] inputArray) 2         { 3             int highIndex = 0; 4             int lowIndex = 0; 5             int midIndex = 0; 6             int temp; 7             for (int i = 0; i < inputArray.Length; i++) 8             { 9                 temp = inputArray[i];10                 highIndex = i - 1;11                 while (lowIndex <= highIndex)12                 {13                     midIndex = (lowIndex + highIndex) / 2;14                     if (inputArray[midIndex] >= temp)15                     {16                         highIndex = midIndex - 1;17                     }18                     else19                     {20                         lowIndex = midIndex + 1;21                     }22                 }23                 for (int j = i - 1; j > highIndex; j--)24                 {25                     inputArray[j + 1] = inputArray[j];26                 }27                 inputArray[highIndex + 1] = temp;28             }29         }

希尔排序：

1         private static void ShellSort(int[] inputArray) 2         { 3             int temp; 4             for (int distance = inputArray.Length / 2; distance > 0; distance--) 5             { 6                 for (int i = 0; i < distance; i++) 7                 { 8                     for (int j = i; j < inputArray.Length; j = j + distance) 9                     {10                         temp = inputArray[j];11                         int index = j - distance;12                         while (index >= 0 && temp < inputArray[index])13                         {14                             inputArray[index + distance] = inputArray[index];15                             index -= distance;16                         }17                         inputArray[index + distance] = temp;18                     }19                 }20             }21           22         }

 

插入排序是稳定排序，时间复杂度是O（n²），而希尔排序时不稳定排序，时间复杂度 平均时间 O(nlogn) 最差时间O(n^s) 1<s<2