using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace 插入排序

{

    //插入排序在大概有序时速度会快很多,比如:3,1,7,4,5,9,10,15,12

    //这种,你会发现大概上已经升序了,这时插入快,

    //平时速度跟其他排序是差不多的.

    class Program

    {

        static void Main(string[] args)

        {

            int[] arr = { , , , , , , , , , , , , ,  };  //待排序数组

            InsertSort(arr);    //调用插入排序函数

            foreach (int item in arr)

                Console.WriteLine(item);

        }

        private static void InsertSort(int[] arr)

        {

            //插入排序是把无序列的数一个一个插入到有序的数

            //先默认下标为0这个数已经是有序

            for (int i = ; i < arr.Length; i++)

            {

                int insertVal = arr[i];  //首先记住这个预备要插入的数

                int insertIndex = i - ; //找出它前一个数的下标（等下 准备插入的数 要跟这个数做比较）

                //如果这个条件满足，说明，我们还没有找到适当的位置

                while (insertIndex >=  && insertVal < arr[insertIndex])   //这里小于是升序，大于是降序

                {

                    arr[insertIndex + ] = arr[insertIndex];   //同时把比插入数要大的数往后移

                    insertIndex--;      //指针继续往后移，等下插入的数也要跟这个指针指向的数做比较

                }

                //插入(这时候给insertVal找到适当位置)

                arr[insertIndex + ] = insertVal;

            }

        }

    }

}