C#怎么實現(xiàn)冒泡排序和插入排序算法

這篇文章主要講解了“C#怎么實現(xiàn)冒泡排序和插入排序算法”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“C#怎么實現(xiàn)冒泡排序和插入排序算法”吧！

1.選擇排序（冒泡排序）

升序

用第一個元素跟其他元素比較，如果該元素比其他元素，則交換，保證該元素是最小的。然后再用第二個元素跟后面其他的比較，保證第二個元素是除第一個最小的。依次循環(huán)，直到整個數(shù)組。

/// <summary>
    /// 選擇排序
    /// </summary>
    public class Selection:BaseSort
    {
        public static long usedTimes = 0;
        public Selection()
        {
        }

        public static void Sort(IComparable[] a)
        {
            Stopwatch timer = new Stopwatch();
            timer.Start();


            for (var i = 0; i < a.Length; i++)
            {
                int minIndex = i;
                for (var j = i + 1; j < a.Length; j++)
                {
                    if (Less(a[j], a[minIndex]))
                    {
                        Exch(a, j, minIndex);
                        //minIndex = j;
                    }
                }

            }

            //交換次數(shù)更少，內(nèi)循環(huán)只交換索引，最后再交換值
            //for (var i = 0; i < a.Length; i++)
            //{
            //    int minIndex = i;
            //    for (var j = i + 1; j < a.Length; j++)
            //    {
            //        if (Less(a[j], a[minIndex]))
            //            minIndex = j;
            //    }
            //    Exch(a, minIndex, i);
            //}

            
            timer.Stop();
            usedTimes = timer.ElapsedMilliseconds;
        }
    }

該算法的內(nèi)循環(huán)是拿當(dāng)前元素跟其他元素比較，交換元素的代碼寫在內(nèi)循環(huán)之外，每次交換都能排定一個元素，因此交換總次數(shù)是 N 。所以算法的時間效率取決于比較的次數(shù)。

由代碼可知，0 到 N-1 之間的任意 i 會進(jìn)行一次交換和 N-1-i 次比較，所以總共有 N 次交換和（N-1）+ （N-2）+ ...+2+1 = N(N-1)/2 ~ N^2 / 2次比較。

缺點

為了找出最小元素需要掃描一遍數(shù)組，但這并沒有為下一篇掃描數(shù)組提供什么信息。排序一個有序的數(shù)組或一個主鍵全部相同的數(shù)組同樣需要和排序隨機(jī)數(shù)組一樣的時間。

優(yōu)點

數(shù)據(jù)移動少。交換次數(shù)和數(shù)組大小是線性的。

2.插入排序

把一個元素插入一個有序的數(shù)組，右邊元素需要右移一位。

與選擇排序一樣，當(dāng)前索引左邊的所有元素都是有序的，但它們的最終位置還不確定，為了給更小的元素騰出空間，它們可能會被移動。當(dāng)索引達(dá)到最右端時，數(shù)組排序就完成了。初始時，可以認(rèn)為第一個元素就是一個有序的數(shù)組。

和選擇排序不同的是，插入排序所需的時間取決于元素的初始順序。一個對部分有序的數(shù)組會比對隨機(jī)數(shù)組排序要快的多。

public class Insertion : BaseSort
    {
        public static long usedTimes = 0;
        public static void Sort(IComparable[] a)
        {
            Stopwatch timer = new Stopwatch();
            timer.Start();

            /*
             * 將當(dāng)前位置的值與前一個比較，如果小就互換，
             * 然后用前一個位置的值繼續(xù),
             * 直到遇到比它大的值，停止內(nèi)循環(huán)、
             * 相當(dāng)于拿當(dāng)前值跟左邊有序數(shù)組依次比較，如果當(dāng)前值小就交換，如果遇到比當(dāng)前值大的元素就跳出內(nèi)循環(huán)，說明已經(jīng)找到合適的位置了。
             */
            for (var i = 0; i < a.Length; i++)
            {
                for (var j = i; j > 0 && Less(a[j], a[j - 1]); j--)
                {
                    Exch(a, j, j - 1);
                }
            }



            /*
             * temp 存儲當(dāng)前值
             * 然后拿 temp 跟左邊的值挨個比較
             * 如果temp小就將比較的值向右移一位，直到遇到比temp大的數(shù)或者到頭了
             * 就將temp放到當(dāng)前位置+1的地方
             */
            //int N = a.Length;
            //for (int i = 1; i < N; i++)
            //{
            //    IComparable temp = a[i];
            //    int j;
            //    for (j = i - 1; j >= 0 && Less(temp, a[j]); j--)
            //    {
            //        a[j + 1] = a[j];
            //    }
            //    a[j + 1] = temp;
            //}

            timer.Stop();
            usedTimes = timer.ElapsedMilliseconds;
        }

    }

對于最壞情況下（逆序），插入排序需要 ~ N^2 / 2 次比較和 ~ N^2 / 2 次交換。因為每次循環(huán)都需要 i 次比較和交換 （1+2.....+N-1）* N 。

對于最好情況下（全部有序），插入排序需要 N-1 次比較和 0 次交換。因為有序，所以不需要交換，只需要每次循環(huán)比較。

對于隨機(jī)排列的數(shù)組，平均情況下插入排序需要 ~ N^2 / 4 次比較和 ~ N^2 / 4 次交換。隨機(jī)數(shù)組在平均情況下每個元素都有可能移動半個數(shù)組的長度。

插入排序比較的次數(shù)是交換的次數(shù)加上一個額外項，該項為 N 減去被插入的元素正好是已知的最小元素的次數(shù)。最好情況下（全部有序），每一個元素都是已知的最小元素，所以這一項為 N-1。

插入排序?qū)τ诜请S機(jī)數(shù)組（部分有序）很有效。例如，有序數(shù)組或主鍵全部相同的數(shù)組，它的運行時間是線性的。

現(xiàn)在考慮一般的情況是部分有序的數(shù)組。倒置指的是數(shù)組中兩個順序顛倒的元素。比如 E X A M P L E 中有 11 對倒置：E-A, X-A, X-M, X-P, X-L, X-E, M-L, M-E, P-L, P-E, L-E 。如果數(shù)組中倒置的數(shù)量小于數(shù)組大小的某個倍數(shù)，這個數(shù)組就是部分有序的。

下面是典型的部分有序的數(shù)組：

數(shù)組中每個元素距離它的最終位置都不遠(yuǎn)；

一個有序的大數(shù)組接一個小數(shù)組；

數(shù)組中只有幾個元素的位置不確定；

當(dāng)?shù)怪玫臄?shù)量很少時，插入排序可能比任何排序算法都快。

插入排序需要的交換次數(shù)和數(shù)組中倒置的數(shù)量相同，每次交換相當(dāng)于減少一對倒置。需要比較的次數(shù)大于等于倒置的數(shù)量，小于等于倒置的數(shù)量加上數(shù)組的大小減一。因為 1 到 N-1 之間的每個 i 都需要一次比較，然后每次交換對應(yīng)著一次比較，這兩種比較之間可能存在交叉，所以是小于等于。

上面的插入排序算法代碼，只要遇到比當(dāng)前元素大的就交換?？梢詢?yōu)化這一塊，上面注釋的代碼，可以減少數(shù)組訪問次數(shù)。

插入排序運行時間大概是選擇排序的一半。

感謝各位的閱讀，以上就是“C#怎么實現(xiàn)冒泡排序和插入排序算法”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對C#怎么實現(xiàn)冒泡排序和插入排序算法這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！