C#實(shí)現(xiàn)插入排序

更新時(shí)間：2022年08月13日 16:35:14 作者：Darren Ji

這篇文章介紹了C#實(shí)現(xiàn)插入排序的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

在選擇排序中，從第一個(gè)元素開(kāi)始，依次遍歷數(shù)組中的元素，找出當(dāng)前遍歷元素之后的最小元素，與當(dāng)前遍歷元素交換位置，依此類(lèi)推，是一種由前往后的排序。而在插入排序中，從第二個(gè)元素開(kāi)始，依次遍歷數(shù)組中的元素，把當(dāng)前遍歷元素與之前的元素進(jìn)行比較，并插入到之前的某個(gè)位置，是一種由后往前的排序。

自定義一個(gè)類(lèi)，里面維護(hù)著一個(gè)int[]類(lèi)型數(shù)組，通過(guò)構(gòu)造函數(shù)定義數(shù)組長(zhǎng)度并初始化，并提供了打印和插入排序的相關(guān)方法。

    public class MyArray
    {
        private static int[] arr;
        private static Random r = new Random();
        public MyArray(int size)
        {
            arr = new int[size];
            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = r.Next(10, 100);
            }
        }
        //插入排序
        public void Sort()
        {
            int insert;
            for (int i = 1; i < arr.Length; i++) //從第二個(gè)元素開(kāi)始遍歷
            {
                insert = arr[i];//把當(dāng)前遍歷元素視為插入元素，放到臨時(shí)變量insert中
                int moveItem = i;//movieItem可以理解為一個(gè)動(dòng)態(tài)索引，初始位置在當(dāng)前遍歷元素的索引
                while (moveItem > 0 && arr[moveItem -1] > insert) //如果前面一個(gè)元素比插入元素大
                {
                    arr[moveItem] = arr[moveItem - 1];//那就把前面這個(gè)元素賦值給后面位置，相當(dāng)于往后移一位
                    moveItem--;//再把動(dòng)態(tài)索引位置向前移動(dòng)一位
                }
                arr[moveItem] = insert;
                Print();
            }
        }
        //打印數(shù)組元素
        public void Print()
        {
            foreach (var item in arr)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine();
        }
    }

以上，大致過(guò)程是：從數(shù)組中第二個(gè)元素開(kāi)始，先把當(dāng)前遍歷元素賦值給一個(gè)臨時(shí)變量，比如說(shuō)是insert,insert這個(gè)變量肯定要插入到當(dāng)前遍歷元素之前的某個(gè)位置，如何確定插入位置呢？假設(shè)用moveItem變量表示最終要插入的索引位置，先把當(dāng)前遍歷元素的索引賦值給moveItem，如果moveItem-1位置上的元素大于insert，那就把moveItem-1位置上的元素向后移動(dòng)一位，并把moveItem-1位置的索引賦值給moveItem，insert是要插入到當(dāng)前的這個(gè)moveItem位置嗎？不一定。再繼續(xù)拿當(dāng)前moveItem位置的前面一個(gè)位置上的元素與insert比較，只要是比insert大，就把該位置上的元素向后移動(dòng)一位，并重新設(shè)置moveItem的值，直到停止循環(huán)。此時(shí)moveItem的值就是insert需要插入的位置。

客戶(hù)端調(diào)用。

    class Program
    {
        static void Main(string[] args)
        {
            MyArray myArray = new MyArray(8);
            Console.WriteLine("排序前：");
            myArray.Print();
            Console.WriteLine("排序后：");
            myArray.Sort();
            Console.ReadKey();
        }
    }

對(duì)于插入排序，當(dāng)依次遍歷數(shù)組元素時(shí)，進(jìn)行了n-1次迭代，當(dāng)把第二個(gè)元素插入到之前某個(gè)位置時(shí)進(jìn)行了1次迭代，當(dāng)把第三個(gè)元素插入到之前某個(gè)位置時(shí)進(jìn)行了2次迭代......第n個(gè)元素進(jìn)行了n-1次迭代，以時(shí)間復(fù)雜度來(lái)說(shuō)，忽略小項(xiàng)和常數(shù)項(xiàng)，插入排序基本上是一個(gè)平方階，寫(xiě)成O(n²)。

到此這篇關(guān)于C#實(shí)現(xiàn)插入排序的文章就介紹到這了。希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: