/*

        例如：对数组：{ 2，7，6，3，1 }进行比较 

        第一轮：{ 2，7，6，3，1 } ：共比较一次

        第二轮：{ 2，6，7，3，1 } ：共比较二次

        第三轮：{ 2，3，4，7，1 } ：共比较三次

        第四轮：{ 1，2，3，6，7 } ：共比较四次

        */

        public void Insert(int[] arr)

        {

            int number;

            int numIndex;

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

            {

                number = arr[i];

                numIndex = i - ;

                while (numIndex >=  && number < arr[numIndex])

                {

                    arr[numIndex + ] = arr[numIndex];

                    numIndex--;

                }

                arr[numIndex + ] = number;

                Console.Write("插入排序：");

                foreach (int item in arr)

                {

                    Console.Write(item + " ");

                }

                Console.WriteLine();

            }

        }

using System;

namespace InsertSortApplication

{

    class Program

    {

        static void Main(string[] args)

        {

            var setArray = new SetArray();

            var insertSort = new InsertSort();

            int[] arr = setArray.GetArray();

            insertSort.Insert(arr);

            Console.ReadLine();

        }

    }

    class SetArray

    {

        public int[] GetArray()

        {

            int length;

            int[] arr;

            Console.WriteLine("请输入数组长度：");

            length = Convert.ToInt32(Console.ReadLine());

            arr = new int[length];

            for (int i = ; i <= length - ; i++)

            {

                Console.Write("请输入数值第{0}位数值：", i);

                arr[i] = Convert.ToInt32(Console.ReadLine());

            }

            Console.Clear();

            Console.Write("arr[] = {");

            foreach (int item in arr)

            {

                Console.Write(item + " ");

            }

            Console.Write("}\n");

            return arr;

        }

    }

    class InsertSort // 插入排序

    {

        public void Insert(int[] arr)

        {

            int number;

            int numIndex;

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

            {

                number = arr[i];

                numIndex = i - ;

                while (numIndex >=  && number < arr[numIndex])

                {

                    arr[numIndex + ] = arr[numIndex];

                    numIndex--;

                }

                arr[numIndex + ] = number;

            }

            Console.Write("插入排序：");

            foreach (int item in arr)

            {

                Console.Write(item + " ");

            }

            Console.WriteLine();

        }

    }

}