C# 實(shí)現(xiàn)經(jīng)典排序算法

C# 實(shí)現(xiàn)經(jīng)典排序算法

using ElementType = System.Int32; // 頂部添加此行,為待排元素的數(shù)據(jù)類(lèi)型起別名(以 Int32 為例)

插入排序

  • 直接插入排序
    public static void StraightInsertSorting(ElementType[] list) {
        var flag = 0; // 存儲(chǔ)需要進(jìn)行插入的值
    
        for (int i = 1; i < list.Length; i++) {
            // 判斷是否需要向前插入
            if (list[i] < list[i-1]) {
                flag = list[i]; // 將要插入的值存儲(chǔ)下來(lái)
                list[i] = list[i - 1]; // list[i] 已確定要向前插入笤休,因此list[i-1]可向后挪一位
    
                // 尋找目標(biāo)位置
                int j;
                for (j = i - 2;  j >= 0 && list[j] > flag; j--) {
                    list[j + 1] = list[j];
                }
    
                // 找到目標(biāo)位置建峭,插入
                if (j + 1 >= 0) {
                    list[j + 1] = flag;
                }
            }
        }
    }
    

交換排序

  • 冒泡排序

    public static void BubbleSort(ElementType[] list) {
        var changed = true;
    
        // i 為窗口大小值,即需要進(jìn)行相鄰比較的次數(shù)
        // list[0] 需要進(jìn)行 n-1 次; list[1]: n-2; list[n-1]: 1
        // 因此 i 從 n-1 開(kāi)始依次遞減启泣,直至 i 為 0
        for (int i = list.Length-1; i > 0 && changed; i--) {
            changed = false;
    
            // 相鄰元素的比較與交換操作
            // 只要進(jìn)行了交換涣脚,則 changed 置為 true, 否則表明當(dāng)前序列已滿(mǎn)足非降序排列,不用再進(jìn)入后續(xù)循環(huán)
            for (int j = 0; j < i; j++) {
                if (list[j] > list[j + 1]) {
                    Swap(ref list[j], ref list[j+1]);
                    changed = true;
                }
            }
        }
    }
    
    private static void Swap(ref ElementType a, ref ElementType b) {
        var temp = a;
        a = b;
        b = temp;
    }
    
  • 快速排序

    public static void QuickSort(ElementType[] list) {
        // low: 0, high: n-1
        QSort(list, 0, list.Length - 1);
    }
    
    private static void QSort(ElementType[] list, int low, int high) {
        if (high <= low) {
            return;
        }
    
        // 一分為二寥茫,分別快排
        var pivotIndex = Partition(list, low, high);
    
        QSort(list, low, pivotIndex - 1);
        QSort(list, pivotIndex + 1, high);
    }
    
    private static int Partition(ElementType[] list, int low, int high) {
        var pivot = list[low]; // 樞紐元素
    
        while (low < high) {
            // 只要 high 指向的元素值不小于 pivot遣蚀,就繼續(xù)向前移動(dòng)
            while (low < high && list[high] >= pivot) {
                high--;
            }
    
            // 直至找到某元素的值小于 pivot,則應(yīng)該將其置于 low 區(qū)域
            list[low] = list[high];
    
            // 只要 low 指向的元素值不大于 pivot纱耻,就繼續(xù)向后移動(dòng)
            while (low < high && list[low] <= pivot) {
                low++;
            }
    
            // 直至找到某元素的值大于 pivot芭梯,則應(yīng)置于 high 區(qū)域
            list[high] = list[low];
        }
    
        list[low] = pivot; // 將樞紐元素歸位,其左邊均為不大于它的元素膝迎,右邊均為不小于它的元素
    
        return low; // 返回樞紐元素的下標(biāo)
    }
    

選擇排序

  • 簡(jiǎn)單選擇排序

    public static void SimpleSelectionSort(ElementType[] list) {
        for (int i = 0; i < list.Length; i++) {
            // 挑出 list[i] 至 list[n-1] 中值最小的元素下標(biāo)
            var minElemIndex = SelectMinElemIndex(list, i);
    
            // 將當(dāng)前元素 list[i] 與最小元素進(jìn)行交換
            if (minElemIndex >= 0 && minElemIndex != i) {
                Swap(ref list[minElemIndex], ref list[i]);
            }
        }
    }
    
    private static int SelectMinElemIndex(ElementType[] list, int offset) {
        if (offset >= list.Length) {
            return -1;
        }
    
        // 最小值下標(biāo)默認(rèn)為 i 的起始值
        var minElemIndex = offset;
    
        for (int i = offset; i < list.Length; i++) {
            // 若當(dāng)前元素的值更小粥帚,則更新最小值下標(biāo)
            if (list[i] < list[minElemIndex]) {
                minElemIndex = i;
            }
        }
    
        return minElemIndex;
    }
    
  • 堆排序

    public static void HeapSort(ElementType[] input) {
        // 創(chuàng)建堆空間,增加 1 空閑元素限次,使各元素的下標(biāo)芒涡,與其作為完全二叉樹(shù)節(jié)點(diǎn)的編號(hào)相同
        HeapType[] h = new HeapType[input.Length + 1];
        for (int i = 0; i < input.Length; i++) {
            h[i + 1] = input[i];
        }
    
        // 構(gòu)建大頂堆, 從第一個(gè)非終端節(jié)點(diǎn)(因?yàn)橐袛嗯c其左右孩子的大小關(guān)系)開(kāi)始向前調(diào)整
        for (int i = h.Length / 2; i > 0; i--) {
            HeapFilter(h, i, h.Length - 1);
        }
    
        // 將最大元素交換至末端后,對(duì)其之前的元素再次構(gòu)建大頂堆
        // 保證每次交換至末端的都是范圍內(nèi)最大的元素
        for (int i = h.Length - 1; i > 0; i--) {
            Swap(ref h[i], ref h[1]);
            HeapFilter(h, 1, i - 1);
        }
    
        // 將排序結(jié)果輸出至原數(shù)組中
        for (int i = 0; i < input.Length; i++) {
            input[i] = h[i + 1];
        }
    }
    
    // 篩選卖漫,構(gòu)建大頂堆
    private static void HeapFilter(HeapType[] h, int insertPos, int end) {
        var insertedValue = h[insertPos];
        int maxChildIndex;
    
        for (maxChildIndex = insertPos * 2; maxChildIndex <= end; maxChildIndex *= 2) {
            // 找到較大的孩子
            if (maxChildIndex < end && h[maxChildIndex] < h[maxChildIndex+1]) {
                maxChildIndex = maxChildIndex + 1;
            }
    
            // 與較大的孩子比較费尽,若雙親較大,符合大頂堆羊始,則不用調(diào)整
            if (insertedValue >= h[maxChildIndex]) {
                break;
            }
    
            // 若雙親較小旱幼,則將較大的孩子放至雙親的當(dāng)前位置
            h[insertPos] = h[maxChildIndex];
    
            // 記錄下最大值的節(jié)點(diǎn)位置,并進(jìn)一步迭代突委,確保該節(jié)點(diǎn)及其孩子構(gòu)成的序列也是大頂堆
            insertPos = maxChildIndex;
        }
    
        h[insertPos] = insertedValue;
    }
    
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末柏卤,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子匀油,更是在濱河造成了極大的恐慌缘缚,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,946評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件敌蚜,死亡現(xiàn)場(chǎng)離奇詭異桥滨,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)齐媒,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)蒲每,“玉大人,你說(shuō)我怎么就攤上這事喻括⊙樱” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,716評(píng)論 0 364
  • 文/不壞的土叔 我叫張陵双妨,是天一觀的道長(zhǎng)淮阐。 經(jīng)常有香客問(wèn)我,道長(zhǎng)刁品,這世上最難降的妖魔是什么泣特? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,222評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮挑随,結(jié)果婚禮上状您,老公的妹妹穿的比我還像新娘。我一直安慰自己兜挨,他們只是感情好膏孟,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,223評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著拌汇,像睡著了一般柒桑。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上噪舀,一...
    開(kāi)封第一講書(shū)人閱讀 52,807評(píng)論 1 314
  • 那天魁淳,我揣著相機(jī)與錄音,去河邊找鬼与倡。 笑死界逛,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的纺座。 我是一名探鬼主播息拜,決...
    沈念sama閱讀 41,235評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼净响!你這毒婦竟也來(lái)了少欺?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 40,189評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤馋贤,失蹤者是張志新(化名)和其女友劉穎狈茉,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體掸掸,經(jīng)...
    沈念sama閱讀 46,712評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,775評(píng)論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了扰付。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片堤撵。...
    茶點(diǎn)故事閱讀 40,926評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖羽莺,靈堂內(nèi)的尸體忽然破棺而出实昨,到底是詐尸還是另有隱情,我是刑警寧澤盐固,帶...
    沈念sama閱讀 36,580評(píng)論 5 351
  • 正文 年R本政府宣布荒给,位于F島的核電站,受9級(jí)特大地震影響刁卜,放射性物質(zhì)發(fā)生泄漏志电。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,259評(píng)論 3 336
  • 文/蒙蒙 一蛔趴、第九天 我趴在偏房一處隱蔽的房頂上張望挑辆。 院中可真熱鬧,春花似錦孝情、人聲如沸鱼蝉。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,750評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)魁亦。三九已至,卻和暖如春羔挡,著一層夾襖步出監(jiān)牢的瞬間洁奈,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,867評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工婉弹, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留睬魂,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,368評(píng)論 3 379
  • 正文 我出身青樓镀赌,卻偏偏與公主長(zhǎng)得像氯哮,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子商佛,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,930評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容