插入排序

Complexity

稳定性

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有 1 个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

Implementation: 代码实现

插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。
插入排序方法分直接插入排序和折半插入排序两种，这里只介绍直接插入排序，折半插入排序留到 “ 查找 ” 内容中进行。
图 1 演示了对 4 个元素进行直接插入排序的过程，共需要 (a),(b),(c) 三次插入。

/// <summary>
  /// 插入排序
  /// </summary>
  /// <param name="unsorted"></param>
  static void insertion_sort(int[] unsorted)
  {
  for (int i = 1; i < unsorted.Length; i++)
  {
  if (unsorted[i - 1] > unsorted[i])
  {
  int temp = unsorted[i];
  int j = i;
  while (j > 0 && unsorted[j - 1] > temp)
  {
  unsorted[j] = unsorted[j - 1];
  j--;
              }
                    unsorted[j] = temp;
                }
            }
        }


        static void Main(string[] args)
        {
            int[] x = { 6, 2, 4, 1, 5, 9 };
            insertion_sort(x);
            foreach (var item in x)
            {
                if (item > 0)
                    Console.WriteLine(item + ",");
            }
            Console.ReadLine();
        }