插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
///
/// 简单插入排序
///
public class Program {
public static void Main(string[] args) {
int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 };
StraightInsertionSort(array);
ShowSord(array);
Console.ReadKey();
}
private static void ShowSord(int[] array) {
foreach (var num in array) {
Console.Write($"{num} ");
}
Console.WriteLine();
}
public static void StraightInsertionSort(int[] array) {
for (int i = 1; i < array.Length; i++) {
int sentinel = array[i];
int j = i - 1;
while (j >= 0 && sentinel < array[j]) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = sentinel;
}
}
}
插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。