- 相關(guān)推薦
排序算法的算法思想和使用場(chǎng)景總結(jié)
總結(jié)就是把一個(gè)時(shí)間段取得的成績(jī)、存在的問(wèn)題及得到的經(jīng)驗(yàn)和教訓(xùn)進(jìn)行一次全面系統(tǒng)的總結(jié)的書(shū)面材料，它可以幫助我們有尋找學(xué)習(xí)和工作中的規(guī)律，快快來(lái)寫(xiě)一份總結(jié)吧。那么如何把總結(jié)寫(xiě)出新花樣呢？下面是小編收集整理的排序算法的算法思想和使用場(chǎng)景總結(jié)，供大家參考借鑒，希望可以幫助到有需要的朋友。
1.概述
排序算法是計(jì)算機(jī)技術(shù)中最基本的算法，許多復(fù)雜算法都會(huì)用到排序。盡管各種排序算法都已被封裝成庫(kù)函數(shù)供程序員使用，但了解排序算法的思想和原理，對(duì)于編寫(xiě)高質(zhì)量的軟件，顯得非常重要。
本文介紹了常見(jiàn)的排序算法，從算法思想，復(fù)雜度和使用場(chǎng)景等方面做了總結(jié)。
2.幾個(gè)概念
（1）排序穩(wěn)定：如果兩個(gè)數(shù)相同，對(duì)他們進(jìn)行的排序結(jié)果為他們的相對(duì)順序不變。例如A={1,2,1,2,1}這里排序之后是A = {1,1,1,2,2}穩(wěn)定就是排序后第一個(gè)1就是排序前的第一個(gè)1，第二個(gè)1就是排序前第二個(gè)1，第三個(gè)1就是排序前的第三個(gè)1。同理2也是一樣。不穩(wěn)定就是他們的順序與開(kāi)始順序不一致。
（2）原地排序：指不申請(qǐng)多余的空間進(jìn)行的排序，就是在原來(lái)的排序數(shù)據(jù)中比較和交換的排序。例如快速排序，堆排序等都是原地排序，合并排序，計(jì)數(shù)排序等不是原地排序。
總體上說(shuō)，排序算法有兩種設(shè)計(jì)思路，一種是基于比較，另一種不是基于比較。《算法導(dǎo)論》一書(shū)給出了這樣一個(gè)證明：“基于比較的算法的最優(yōu)時(shí)間復(fù)雜度是O（N lg N）”。對(duì)于基于比較的算法，有三種設(shè)計(jì)思路，分別為：插入排序，交換排序和選擇排序。非基于比較的排序算法時(shí)間復(fù)雜度為O(lg N)，之所以復(fù)雜度如此低，是因?yàn)樗鼈円话銓?duì)排序數(shù)據(jù)有特殊要求。如計(jì)數(shù)排序要求數(shù)據(jù)范圍不會(huì)太大，基數(shù)排序要求數(shù)據(jù)可以分解成多個(gè)屬性等。
3.基于比較的排序算法
正如前一節(jié)介紹的，基于比較的排序算法有三種設(shè)計(jì)思路，分別為插入，交換和選擇。對(duì)于插入排序，主要有直接插入排序，希爾排序；對(duì)于交換排序，主要有冒泡排序，快速排序；對(duì)于選擇排序，主要有簡(jiǎn)單選擇排序，堆排序；其它排序：歸并排序。
3.1插入排序
（1）直接插入排序
特點(diǎn)：穩(wěn)定排序，原地排序，時(shí)間復(fù)雜度O(N*N)
思想：將所有待排序數(shù)據(jù)分成兩個(gè)序列，一個(gè)是有序序列S，另一個(gè)是待排序序列U，初始時(shí)，S為空，U為所有數(shù)據(jù)組成的數(shù)列，然后依次將U中的數(shù)據(jù)插到有序序列S中，直到U變?yōu)榭铡?/p>
適用場(chǎng)景：當(dāng)數(shù)據(jù)已經(jīng)基本有序時(shí)，采用插入排序可以明顯減少數(shù)據(jù)交換和數(shù)據(jù)移動(dòng)次數(shù)，進(jìn)而提升排序效率。
（2）希爾排序
特點(diǎn)：非穩(wěn)定排序，原地排序，時(shí)間復(fù)雜度O(n^lamda)(1 < lamda < 2), lamda和每次步長(zhǎng)選擇有關(guān)。
思想：增量縮小排序。先將序列按增量劃分為元素個(gè)數(shù)近似的若干組，使用直接插入排序法對(duì)每組進(jìn)行排序，然后不斷縮小增量直至為1，最后使用直接插入排序完成排序。
適用場(chǎng)景：因?yàn)樵隽砍跏贾挡蝗菀走x擇，所以該算法不常用。
3.2交換排序
（1）冒泡排序
特點(diǎn)：穩(wěn)定排序，原地排序，時(shí)間復(fù)雜度O(N*N)
思想：將整個(gè)序列分為無(wú)序和有序兩個(gè)子序列，不斷通過(guò)交換較大元素至無(wú)序子序列首完成排序。
適用場(chǎng)景：同直接插入排序類(lèi)似
（2）快速排序
特點(diǎn)：不穩(wěn)定排序，原地排序，時(shí)間復(fù)雜度O(N*lg N)
思想：不斷尋找一個(gè)序列的樞軸點(diǎn)，然后分別把小于和大于樞軸點(diǎn)的數(shù)據(jù)移到樞軸點(diǎn)兩邊，然后在兩邊數(shù)列中繼續(xù)這樣的操作，直至全部序列排序完成。
適用場(chǎng)景：應(yīng)用很廣泛，差不多各種語(yǔ)言均提供了快排API
3.3選擇排序
（1）簡(jiǎn)單選擇排序
特點(diǎn)：不穩(wěn)定排序（比如對(duì)3 3 2三個(gè)數(shù)進(jìn)行排序，第一個(gè)3會(huì)與2交換），原地排序，時(shí)間復(fù)雜度O(N*N)
思想：將序列劃分為無(wú)序和有序兩個(gè)子序列，尋找無(wú)序序列中的最小（大）值和無(wú)序序列的首元素交換，有序區(qū)擴(kuò)大一個(gè)，循環(huán)下去，最終完成全部排序。
適用場(chǎng)景：交換少
（2）堆排序
特點(diǎn)：非穩(wěn)定排序，原地排序，時(shí)間復(fù)雜度O(N*lg N)
思想：小頂堆或者大頂堆
適用場(chǎng)景：不如快排廣泛
3.4其它排序
（1）歸并排序
特點(diǎn)：穩(wěn)定排序，非原地排序，時(shí)間復(fù)雜度O(N*N)
思想：首先，將整個(gè)序列（共N個(gè)元素）看成N個(gè)有序子序列，然后依次合并相鄰的兩個(gè)子序列，這樣一直下去，直至變成一個(gè)整體有序的序列。
適用場(chǎng)景：外部排序
4.非基于比較的排序算法
非基于比較的排序算法主要有三種，分別為：基數(shù)排序，桶排序和計(jì)數(shù)排序。這些算法均是針對(duì)特殊數(shù)據(jù)的，不如要求數(shù)據(jù)分布均勻，數(shù)據(jù)偏差不會(huì)太大。采用的思想均是內(nèi)存換時(shí)間，因而全是非原地排序。
4.1基數(shù)排序
特點(diǎn)：穩(wěn)定排序，非原地排序，時(shí)間復(fù)雜度O(N)
思想：把每個(gè)數(shù)據(jù)看成d個(gè)屬性組成，依次按照d個(gè)屬性對(duì)數(shù)據(jù)排序（每輪排序可采用計(jì)數(shù)排序），復(fù)雜度為O(d*N)
適用場(chǎng)景：數(shù)據(jù)明顯有幾個(gè)關(guān)鍵字或者幾個(gè)屬性組成
4.2桶排序
特點(diǎn)：穩(wěn)定排序，非原地排序，時(shí)間復(fù)雜度O(N)
思想：將數(shù)據(jù)按大小分到若干個(gè)桶（比如鏈表）里面，每個(gè)桶內(nèi)部采用簡(jiǎn)單排序算法進(jìn)行排序。
適用場(chǎng)景：0
4.3計(jì)數(shù)排序
特點(diǎn)：穩(wěn)定排序，非原地排序，時(shí)間復(fù)雜度O(N)
思想：對(duì)每個(gè)數(shù)據(jù)出現(xiàn)次數(shù)進(jìn)行技術(shù)（用hash方法計(jì)數(shù)，最簡(jiǎn)單的hash是數(shù)組！），然后從大到小或者從小到大輸出每個(gè)數(shù)據(jù)。
使用場(chǎng)景：比基數(shù)排序和桶排序廣泛得多。
5. 總結(jié)
對(duì)于基于比較的排序算法，大部分簡(jiǎn)單排序(直接插入排序，選擇排序和冒泡排序)都是穩(wěn)定排序，選擇排序除外；大部分高級(jí)排序（除簡(jiǎn)單排序以外的）都是不穩(wěn)定排序，歸并排序除外，但歸并排序需要額外的存儲(chǔ)空間。對(duì)于非基于比較的排序算法，它們都對(duì)數(shù)據(jù)規(guī)律有特殊要求，且采用了內(nèi)存換時(shí)間的思想。排序算法如此之多，往往需要根據(jù)實(shí)際應(yīng)用選擇最適合的排序算法。
【排序算法的算法思想和使用場(chǎng)景總結(jié)】相關(guān)文章：
九年級(jí)數(shù)學(xué)《生活與算法》評(píng)課稿（通用12篇）08-21
解放思想是做好工作的前提和基礎(chǔ)的總結(jié)10-10
關(guān)于個(gè)人思想和工作總結(jié)（精選16篇）10-24
思想和業(yè)務(wù)技術(shù)工作總結(jié)（精選10篇）10-20
教師教學(xué)經(jīng)驗(yàn)和思想工作總結(jié)11-15
犯罪思想總結(jié)06-13
思想總結(jié)大全09-21
聽(tīng)課思想總結(jié)08-15
教育思想總結(jié)08-17