摘要:穩定與不穩定算法示例以下圖片解釋了穩定和不穩定的排序是如何工作的這就是穩定和不穩定排序算法之間的區別。穩定排序算法的一些常見示例是合并排序,插入排序和冒泡排序。
來源 | 愿碼(ChainDesk.CN)內容編輯
愿碼Slogan | 連接每個程序員的故事
網站 | http://chaindesk.cn
愿碼愿景 | 打造全學科IT系統免費課程,助力小白用戶、初級工程師0成本免費系統學習、低成本進階,幫助BAT一線資深工程師成長并利用自身優勢創造睡后收入。
官方公眾號 | 愿碼 | 愿碼服務號 | 區塊鏈部落
免費加入愿碼全思維工程師社群 | 任一公眾號回復“愿碼”兩個字獲取入群二維碼
本文閱讀時長:6min
你是否理解QuickSort與MergeSort之間的區別?你穩定和不穩定的排序算法的含義是什么?
當面試官問到以上問題應如何回答?
如果排序算法保持數字/記錄的相對順序,即如果需要排序1 1 2 3,那么如果不更改前兩個排序的順序,則認為排序算法是穩定的,但如果交換它們,則盡管總體結果或排序順序保持不變,但它將變得不穩定。
當您對對象進行排序時(例如,按鍵對鍵值對進行排序),這種差異會變得更加明顯。在穩定算法的情況下,保留鍵值對的原始順序,如下例所示。
實際上,如果您忘記提及這些概念,面試官可能會將此問題視為快速排序與合并排序的后續工作。
quicksort和mergesort之間的主要區別之一是快速排序不穩定,而合并排序是一種穩定的排序算法。順便說一句,如果您不熟悉Quicksort和Mergesort等基本排序算法,那么我建議您學習下全面的數據結構課程,如數據結構和算法:深度使用Java。它將為您提供進一步探索所需的所有基礎知識。
穩定與不穩定算法假設您需要按鍵的遞增順序對以下鍵值對進行排序:
INPUT:(4,5)(3,2)(4,3)(5,4)(6,4)
現在,有兩個密鑰相同的兩對的可能解決方案即(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)
將產生第一個輸出的排序算法稱為穩定排序算法,因為保持了相等鍵的原始順序,您可以看到(4,5)以排序順序出現在(4,3)之前,這是原始順序,即在給定的輸入中,(4,5)出現在(4,3)之前。
產生第二輸出的算法將被稱為不穩定的排序算法,因為具有相同鍵的對象的順序不按排序順序維持。你可以看到,在第二個輸出中,(4,3)出現在(4,5)之前,原始輸入中不是這種情況。
現在,最大的問題是穩定和不穩定排序算法的一些例子是什么?那么,你可以把所有眾所周知的排序算法分成穩定和不穩定的。穩定算法的一些示例是合并排序,插入排序,冒泡排序和二叉樹排序。而QuickSort,堆排序和選擇排序是不穩定的排序算法。
如果你還記得,Collections.sort()Java Collection框架中的方法使用迭代合并排序,這是一種穩定的算法。如果輸入數組被部分排序,它的比較也比NLog(N)少得多。
如果您有興趣了解有關此主題的更多信息,我建議您學習數據結構和算法,比如算法和數據結構-第1部分和第2部分。它是Java程序員算法的綜合課程之一。
以下圖片解釋了穩定和不穩定的排序是如何工作的:
這就是穩定和不穩定排序算法之間的區別。請記住,如果在排序的輸出中保持相等鍵或數字的原始順序,則該算法稱為排序算法。穩定排序算法的一些常見示例是合并排序,插入排序和冒泡排序。
你還想要知道哪些關于面試題的知識呢?請在下方留言!
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/74167.html
摘要:目錄常見的八種排序常見的八種排序直接插入排序直接插入排序希爾排序希爾排序直接選擇排序直接選擇排序堆排序堆排序冒泡排序冒泡排序快速排序快速排序版本版本挖坑法挖坑法前后指針版前后指針版快速排序代碼 目錄 常見的八種排序 直接插入排序 希爾排序 直接選擇排序 堆排序 冒泡排序? 快速排序 hoar...
閱讀 1905·2021-11-25 09:43
閱讀 1405·2021-11-22 14:56
閱讀 3280·2021-11-22 09:34
閱讀 2010·2021-11-15 11:37
閱讀 2256·2021-09-01 10:46
閱讀 1396·2019-08-30 15:44
閱讀 2294·2019-08-30 13:15
閱讀 2393·2019-08-29 13:07