資訊專欄INFORMATION COLUMN
摘要：穩(wěn)定與不穩(wěn)定算法示例以下圖片解釋了穩(wěn)定和不穩(wěn)定的排序是如何工作的這就是穩(wěn)定和不穩(wěn)定排序算法之間的區(qū)別。穩(wěn)定排序算法的一些常見示例是合并排序，插入排序和冒泡排序。
來(lái)源 | 愿碼(ChainDesk.CN)內(nèi)容編輯
愿碼Slogan | 連接每個(gè)程序員的故事
網(wǎng)站 | http://chaindesk.cn
愿碼愿景 | 打造全學(xué)科IT系統(tǒng)免費(fèi)課程，助力小白用戶、初級(jí)工程師0成本免費(fèi)系統(tǒng)學(xué)習(xí)、低成本進(jìn)階，幫助BAT一線資深工程師成長(zhǎng)并利用自身優(yōu)勢(shì)創(chuàng)造睡后收入。
官方公眾號(hào) | 愿碼 | 愿碼服務(wù)號(hào) | 區(qū)塊鏈部落
免費(fèi)加入愿碼全思維工程師社群 | 任一公眾號(hào)回復(fù)“愿碼”兩個(gè)字獲取入群二維碼
本文閱讀時(shí)長(zhǎng)：6min
你是否理解QuickSort與MergeSort之間的區(qū)別？你穩(wěn)定和不穩(wěn)定的排序算法的含義是什么？
當(dāng)面試官問到以上問題應(yīng)如何回答？
如果排序算法保持?jǐn)?shù)字/記錄的相對(duì)順序，即如果需要排序1 1 2 3，那么如果不更改前兩個(gè)排序的順序，則認(rèn)為排序算法是穩(wěn)定的，但如果交換它們，則盡管總體結(jié)果或排序順序保持不變，但它將變得不穩(wěn)定。
當(dāng)您對(duì)對(duì)象進(jìn)行排序時(shí)（例如，按鍵對(duì)鍵值對(duì)進(jìn)行排序），這種差異會(huì)變得更加明顯。在穩(wěn)定算法的情況下，保留鍵值對(duì)的原始順序，如下例所示。
實(shí)際上，如果您忘記提及這些概念，面試官可能會(huì)將此問題視為快速排序與合并排序的后續(xù)工作。
quicksort和mergesort之間的主要區(qū)別之一是快速排序不穩(wěn)定，而合并排序是一種穩(wěn)定的排序算法。順便說一句，如果您不熟悉Quicksort和Mergesort等基本排序算法，那么我建議您學(xué)習(xí)下全面的數(shù)據(jù)結(jié)構(gòu)課程，如數(shù)據(jù)結(jié)構(gòu)和算法：深度使用Java。它將為您提供進(jìn)一步探索所需的所有基礎(chǔ)知識(shí)。
穩(wěn)定與不穩(wěn)定算法假設(shè)您需要按鍵的遞增順序?qū)σ韵骆I值對(duì)進(jìn)行排序：
INPUT：（4,5）（3,2）（4,3）（5,4）（6,4）
現(xiàn)在，有兩個(gè)密鑰相同的兩對(duì)的可能解決方案即（4,5）和（4,3）如下所示：
OUTPUT1：（3,2），（4,5），（4,3），（5,4），（6,4）
OUTPUT2：（3,2 ），（4,3），（4,5），（5,4），（6,4）
將產(chǎn)生第一個(gè)輸出的排序算法稱為穩(wěn)定排序算法，因?yàn)楸３至讼嗟孺I的原始順序，您可以看到（4,5）以排序順序出現(xiàn)在（4,3）之前，這是原始順序，即在給定的輸入中，（4,5）出現(xiàn)在（4,3）之前。
產(chǎn)生第二輸出的算法將被稱為不穩(wěn)定的排序算法，因?yàn)榫哂邢嗤I的對(duì)象的順序不按排序順序維持。你可以看到，在第二個(gè)輸出中，（4,3）出現(xiàn)在（4,5）之前，原始輸入中不是這種情況。
現(xiàn)在，最大的問題是穩(wěn)定和不穩(wěn)定排序算法的一些例子是什么？那么，你可以把所有眾所周知的排序算法分成穩(wěn)定和不穩(wěn)定的。穩(wěn)定算法的一些示例是合并排序，插入排序，冒泡排序和二叉樹排序。而QuickSort，堆排序和選擇排序是不穩(wěn)定的排序算法。
如果你還記得，Collections.sort（）Java Collection框架中的方法使用迭代合并排序，這是一種穩(wěn)定的算法。如果輸入數(shù)組被部分排序，它的比較也比NLog（N）少得多。
如果您有興趣了解有關(guān)此主題的更多信息，我建議您學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法，比如算法和數(shù)據(jù)結(jié)構(gòu)-第1部分和第2部分。它是Java程序員算法的綜合課程之一。
以下圖片解釋了穩(wěn)定和不穩(wěn)定的排序是如何工作的：
這就是穩(wěn)定和不穩(wěn)定排序算法之間的區(qū)別。請(qǐng)記住，如果在排序的輸出中保持相等鍵或數(shù)字的原始順序，則該算法稱為排序算法。穩(wěn)定排序算法的一些常見示例是合并排序，插入排序和冒泡排序。
你還想要知道哪些關(guān)于面試題的知識(shí)呢？請(qǐng)?jiān)谙路搅粞裕?/p>
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/74167.html
摘要：前言排序算法可能是你學(xué)編程第一個(gè)學(xué)習(xí)的算法，還記得冒泡嗎當(dāng)然，排序和查找兩類算法是面試的熱門選項(xiàng)。本篇將會(huì)總結(jié)一下，在前端的一些排序算法。函數(shù)的性能相信對(duì)于排序算法性能來(lái)說，時(shí)間復(fù)雜度是至關(guān)重要的一個(gè)參考因素。 前言 排序算法可能是你學(xué)編程第一個(gè)學(xué)習(xí)的算法，還記得冒泡嗎？ 當(dāng)然，排序和查找兩類算法是面試的熱門選項(xiàng)。如果你是一個(gè)會(huì)寫快排的程序猿，面試官在比較你和一個(gè)連快排都不會(huì)寫的人的時(shí)...
摘要：目錄常見的八種排序常見的八種排序直接插入排序直接插入排序希爾排序希爾排序直接選擇排序直接選擇排序堆排序堆排序冒泡排序冒泡排序快速排序快速排序版本版本挖坑法挖坑法前后指針版前后指針版快速排序代碼 目錄 常見的八種排序 直接插入排序 希爾排序 直接選擇排序 堆排序 冒泡排序? 快速排序 hoar...
摘要：如果對(duì)空間限制不大，可以使用基數(shù)排序等方法降低時(shí)間復(fù)雜度，這些線性時(shí)間排序法是利用了數(shù)據(jù)的特性達(dá)到最佳的效果。 內(nèi)部排序 以下為基于比較的排序。 一、插入排序 直接插入排序 基本思想： 將元素插入到已經(jīng)排好序的序列中。第一個(gè)元素已經(jīng)是有序序列，然后比較外圍的元素和序列的最后一個(gè)元素，判斷是否需要插入，如果小，則插入。 時(shí)間復(fù)雜度：最優(yōu) O(n) 最差 O(n^2) 是否穩(wěn)定：是 ...
閱讀 1918·2021-11-25 09:43
閱讀 1425·2021-11-22 14:56
閱讀 3290·2021-11-22 09:34
閱讀 2028·2021-11-15 11:37
閱讀 2283·2021-09-01 10:46
閱讀 1412·2019-08-30 15:44
閱讀 2310·2019-08-30 13:15
閱讀 2406·2019-08-29 13:07
