快捷導(dǎo)航

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

更新時(shí)間：2022年04月15日 13:35:17 作者：Ruby_Lu

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

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

升序

用第一個(gè)元素跟其他元素比較，如果該元素比其他元素，則交換，保證該元素是最小的。然后再用第二個(gè)元素跟后面其他的比較，保證第二個(gè)元素是除第一個(gè)最小的。依次循環(huán)，直到整個(gè)數(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)前元素跟其他元素比較，交換元素的代碼寫(xiě)在內(nèi)循環(huán)之外，每次交換都能排定一個(gè)元素，因此交換總次數(shù)是 N 。所以算法的時(shí)間效率取決于比較的次數(shù)。

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

缺點(diǎn)

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

優(yōu)點(diǎn)

數(shù)據(jù)移動(dòng)少。交換次數(shù)和數(shù)組大小是線(xiàn)性的。

2.插入排序

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

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

和選擇排序不同的是，插入排序所需的時(shí)間取決于元素的初始順序。一個(gè)對(duì)部分有序的數(shù)組會(huì)比對(duì)隨機(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)前位置的值與前一個(gè)比較，如果小就互換，
             * 然后用前一個(gè)位置的值繼續(xù),
             * 直到遇到比它大的值，停止內(nèi)循環(huán)、
             * 相當(dāng)于拿當(dāng)前值跟左邊有序數(shù)組依次比較，如果當(dāng)前值小就交換，如果遇到比當(dāng)前值大的元素就跳出內(nèi)循環(huán)，說(shuō)明已經(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 存儲(chǔ)當(dāng)前值
             * 然后拿 temp 跟左邊的值挨個(gè)比較
             * 如果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;
        }

    }

對(duì)于最壞情況下（逆序），插入排序需要 ~ N^2 / 2 次比較和 ~ N^2 / 2 次交換。因?yàn)槊看窝h(huán)都需要 i 次比較和交換（1+2.....+N-1）* N 。

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

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

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

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

現(xiàn)在考慮一般的情況是部分有序的數(shù)組。倒置指的是數(shù)組中兩個(gè)順序顛倒的元素。比如 E X A M P L E 中有 11 對(duì)倒置：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ù)組大小的某個(gè)倍數(shù)，這個(gè)數(shù)組就是部分有序的。

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

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

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

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

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

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

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