C#之插入排序

演算法描述

1.假定數組第一位為有序序列，抽出後一位元素與有序序列中元素依次比較；

2.如果有序序列元素大於抽出元素，將該元素向後移位；

3.重覆前面步驟依次抽取無序序列中首位元素進行比較，直到所有數值排序完成；

代碼實現

        /*
        例如：對數組：{ 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 = 1; i < arr.Length; i++)
            {
                number = arr[i];
                numIndex = i - 1;

                while (numIndex >= 0 && number < arr[numIndex])
                {
                    arr[numIndex + 1] = arr[numIndex];
                    numIndex--;
                }

                arr[numIndex + 1] = 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 = 0; i <= length - 1; 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 = 1; i < arr.Length; i++)
            {
                number = arr[i];
                numIndex = i - 1;

                while (numIndex >= 0 && number < arr[numIndex])
                {
                    arr[numIndex + 1] = arr[numIndex];
                    numIndex--;
                }

                arr[numIndex + 1] = number;
            }

            Console.Write("插入排序：");
            foreach (int item in arr)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();

        }
    }
}