C#怎么實現冒泡排序和插入排序算法

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

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

升序

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

/// <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;
                    }
                }

            }

            //交換次數更少，內循環只交換索引，最后再交換值
            //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 。所以算法的時間效率取決于比較的次數。

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

缺點

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

優點

數據移動少。交換次數和數組大小是線性的。

2.插入排序

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

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

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

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

            /*
             * 將當前位置的值與前一個比較，如果小就互換，
             * 然后用前一個位置的值繼續,
             * 直到遇到比它大的值，停止內循環、
             * 相當于拿當前值跟左邊有序數組依次比較，如果當前值小就交換，如果遇到比當前值大的元素就跳出內循環，說明已經找到合適的位置了。
             */
            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 存儲當前值
             * 然后拿 temp 跟左邊的值挨個比較
             * 如果temp小就將比較的值向右移一位，直到遇到比temp大的數或者到頭了
             * 就將temp放到當前位置+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 次交換。因為每次循環都需要 i 次比較和交換 （1+2.....+N-1）* N 。

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

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

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

插入排序對于非隨機數組（部分有序）很有效。例如，有序數組或主鍵全部相同的數組，它的運行時間是線性的。

現在考慮一般的情況是部分有序的數組。倒置指的是數組中兩個順序顛倒的元素。比如 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 。如果數組中倒置的數量小于數組大小的某個倍數，這個數組就是部分有序的。

下面是典型的部分有序的數組：

數組中每個元素距離它的最終位置都不遠；

一個有序的大數組接一個小數組；

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

當倒置的數量很少時，插入排序可能比任何排序算法都快。

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

上面的插入排序算法代碼，只要遇到比當前元素大的就交換。可以優化這一塊，上面注釋的代碼，可以減少數組訪問次數。

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

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