資訊專(zhuān)欄INFORMATION COLUMN
摘要：前面介紹了七大算法的思想與實(shí)現(xiàn)步驟，下面來(lái)做一個(gè)歸總。直到無(wú)序區(qū)中的數(shù)為零，結(jié)束排序。步驟以從小到大為例，排序數(shù)組大小為。比較完以后則排序結(jié)束。堆排序思想堆排序是采用樹(shù)的形式的數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行排序的，其中每一個(gè)堆都是完全二叉樹(shù)。
前面介紹了七大算法的思想與實(shí)現(xiàn)步驟，下面來(lái)做一個(gè)歸總。
| 排序方法 | 平均復(fù)雜度 | 最壞復(fù)雜度 | 最好復(fù)雜度 | 輔助空間 | 穩(wěn)定性 | |
|---|---|---|---|---|---|---|
| 直接選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 | |
| 冒泡排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 | |
| 直接插入排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 | |
| 歸并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 穩(wěn)定 | |
| 快速排序 | O(nlogn) | O(n^2) | O(nlogn) | O(1) | 不穩(wěn)定 | |
| 希爾排序 | O(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | O(logn)~O(n) | 不穩(wěn)定 | |
| 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不穩(wěn)定 |
直接選擇排序，整體思想是將數(shù)據(jù)分成兩個(gè)區(qū)域，有序區(qū)與無(wú)序區(qū)。排序的時(shí)候是每次從無(wú)序區(qū)中選擇出最小的數(shù)，然后插入到有序區(qū)中的最末尾，從而形成更大的有序區(qū)。直到無(wú)序區(qū)中的數(shù)為零，結(jié)束排序。
步驟假設(shè)排序數(shù)組為a[0...n-1];
首先有序區(qū)中的個(gè)數(shù)為0，令i = 0。從無(wú)序區(qū)中選擇最小的數(shù)，加入到有序區(qū)a[i]中。使得有序區(qū)為a[0..i],無(wú)序區(qū)為a[i...n-1]
完成后 i++ ,然后繼續(xù)前面的步驟，直到 i = n-1 為止。使得全部數(shù)都在有序區(qū)中。
冒泡排序 思想冒泡排序主要是相鄰的兩個(gè)數(shù)兩兩進(jìn)行比較，拿從小到大說(shuō)明，進(jìn)行冒泡排序后會(huì)將大的數(shù)沉到底部，將小得數(shù)浮到頂部。所以冒泡說(shuō)法由此得名。
步驟以從小到大為例，排序數(shù)組大小為n。
第N = 0趟排序開(kāi)始都從a[0]開(kāi)始與其下面的相鄰的數(shù)進(jìn)行比較，如果大于相鄰的數(shù)則交換他們的位置。
繼續(xù)與下一個(gè)相鄰的數(shù)進(jìn)行比較，大于相鄰的就交換，最后進(jìn)行比較n-1次后，第N = 0趟排序結(jié)束，最大的數(shù)就在數(shù)組的a[n-1]處。
重復(fù)前面的步驟，直到 N = n-1,排序結(jié)束。
直接插入排序 思想直接插入排序的基本思想是:將需要排序的關(guān)鍵數(shù)與前面已經(jīng)排好序的數(shù)據(jù)從后往前進(jìn)行比較，使其插入到合適的位置。
步驟排序數(shù)組為a[0...n]
將a[0]作為起始數(shù)據(jù)，從a[1]開(kāi)始作為關(guān)鍵字向前進(jìn)行比較，若小于前面所遇到的比較數(shù)，則交換兩個(gè)比較數(shù)的位置，否則直接進(jìn)行下一個(gè)關(guān)鍵字的比較。
重復(fù)前面的步驟，直到將a[n]作為關(guān)鍵字進(jìn)行比較。比較完以后則排序結(jié)束。
歸并排序 思想歸并排序是一個(gè)效率相對(duì)較高的排序算法，它采用的是分治的思想，將待排序的序列分成若干組，保證每組都有序，然后再進(jìn)行合并排序，最終使整個(gè)序列有序。
步驟將待排序的序列采用分治思想將其劃分成若干組，使其有序，其中可采用遞歸進(jìn)行劃分。
將有序的組分別進(jìn)行歸并操作，其中借助一個(gè)輔助數(shù)組，將左右劃分的有序組從頭開(kāi)始進(jìn)行比較，將較小的數(shù)加入到輔助數(shù)組中，且較小的所在有序數(shù)組向后自增，再與原來(lái)比較的數(shù)進(jìn)行比較。
重復(fù)上面2的步驟，直到所有數(shù)據(jù)比較完畢，或者將還有剩余數(shù)未比較的有序數(shù)據(jù)直接按原有的順序加入到輔助數(shù)組中,最后將已經(jīng)排好序的輔助數(shù)組加入到原有數(shù)組的相應(yīng)位置。
重復(fù)上面的2、3步驟，直到所有的左右劃分歸并完畢。
快速排序 思想快速排序的主要思想是：將一個(gè)待排序序列分成兩個(gè)部分，以其中的一個(gè)數(shù)據(jù)作為分界線，其中一部分小于這個(gè)分界線的數(shù)據(jù)，另一部分大于這個(gè)分界線的數(shù)據(jù)。因?yàn)椴捎眠f歸的思想，再對(duì)這兩個(gè)序列進(jìn)行快速排序，直到所以的數(shù)據(jù)都是有序的。
步驟假設(shè)待排序的數(shù)組為a[0...n-1]
一般都將第一個(gè)數(shù)a[i] (i = 0) 作為關(guān)鍵數(shù)，即快速排序的分界數(shù)。先從數(shù)組的后面開(kāi)始即初值j = n-1，逐個(gè)向前進(jìn)行遍歷與選的的關(guān)鍵數(shù)進(jìn)行比較(j--)，若大于等于關(guān)鍵數(shù)則繼續(xù)遍歷，否則將其與關(guān)鍵數(shù)所在的位置進(jìn)行交換，并停止遍歷且i++記錄此時(shí)的i、j。
停止前面的遍歷，再?gòu)臄?shù)組的第i個(gè)位置開(kāi)始向后進(jìn)行遍歷，逐個(gè)與關(guān)鍵數(shù)進(jìn)行比較(i++)，若小于等于關(guān)鍵數(shù)則繼續(xù)遍歷，否則將其與關(guān)鍵數(shù)所在的位置進(jìn)行交換，并停止遍歷且j--記錄此時(shí)的i、j。
重復(fù)上面的步驟，直到i==j就結(jié)束本次快速排序。
此時(shí)已經(jīng)將其按關(guān)鍵數(shù)分成兩個(gè)部分，再重復(fù)前面的步驟，對(duì)劃分的部分進(jìn)行快速排序，直到劃分的組中的數(shù)據(jù)個(gè)數(shù)為1即此時(shí)所有數(shù)據(jù)有序。
希爾排序 思想希爾排序是記錄增量來(lái)進(jìn)行分組，再對(duì)分組內(nèi)部進(jìn)行直接插入排序，隨著增量的不斷減小，直到增量減小到1時(shí)，即每個(gè)分組中的數(shù)據(jù)量為1，此時(shí)排序結(jié)束。
步驟設(shè)待排序的數(shù)組為a[0...n-1]
一般開(kāi)始取增量數(shù)d=n/2。從a[0]~a[d-1]將數(shù)組中數(shù)據(jù)之間的間隔為增量數(shù)d的倍數(shù)歸為相同組。
依次對(duì)每組中的數(shù)據(jù)進(jìn)行直接插入排序，使其有序。
再增量數(shù)d=d/2，重復(fù)上面的步驟，直到d=1為止。
堆排序 思想堆排序是采用樹(shù)的形式的數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行排序的，其中每一個(gè)堆都是完全二叉樹(shù)。堆排序分為大根堆與小根堆，大根堆（小根堆）表示在完全二叉樹(shù)中，所用的非葉子節(jié)點(diǎn)都大于等于（小于等于）他們左右子節(jié)點(diǎn)（存在）。所以堆的頂點(diǎn)不是最大數(shù)就是最小數(shù)。這樣的話我們就可以借助這種性質(zhì)，每次都取出大根堆（小根堆）的頂點(diǎn)數(shù)，形成有序序列。
步驟首先生成小根堆或大根堆，這里以小根堆為例。我們可以將每一個(gè)非葉子節(jié)點(diǎn)都看做是一個(gè)最小的完全二叉樹(shù)，將他們都生成小根堆，從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，把其當(dāng)做是根節(jié)點(diǎn)，逐步向前進(jìn)行創(chuàng)建小根堆。
然后就是取出形成的小根堆得頂點(diǎn)值，將其與堆中第N(N=n)個(gè)節(jié)點(diǎn)互換位置，即a[N-1]。
此時(shí)小根堆被破壞，再重新生產(chǎn)小根堆N--，但此時(shí)要生成的數(shù)的范圍為a[0...N-1]。
重復(fù)上面的步驟2、3，直到N=1，即a[0]，排序結(jié)束。
如有不足之處歡迎指出，全部代碼已經(jīng)放到github上，有需要的可以下載。
github地址：https://github.com/idisfkj/Ar...
關(guān)注文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64847.html
摘要：編程思想第版這本書(shū)要常讀，初學(xué)者可以快速概覽，中等程序員可以深入看看，老鳥(niǎo)還可以用之回顧的體系。以下視頻整理自慕課網(wǎng)工程師路徑相關(guān)免費(fèi)課程。 我自己總結(jié)的Java學(xué)習(xí)的系統(tǒng)知識(shí)點(diǎn)以及面試問(wèn)題，目前已經(jīng)開(kāi)源，會(huì)一直完善下去，歡迎建議和指導(dǎo)歡迎Star： https://github.com/Snailclimb/Java-Guide 筆者建議初學(xué)者學(xué)習(xí)Java的方式：看書(shū)+視頻+實(shí)踐（初...
摘要：?jiǎn)我宦氊?zé)原則開(kāi)閉原則里氏替換原則依賴(lài)倒置原則接口隔離原則迪米特法則組合聚合復(fù)用原則單一職責(zé)原則高內(nèi)聚低耦合定義不要存在多于一個(gè)導(dǎo)致類(lèi)變更的原因。建議接口一定要做到單一職責(zé)，類(lèi)的設(shè)計(jì)盡量做到只有一個(gè)原因引起變化。使用繼承時(shí)遵循里氏替換原則。 單一職責(zé)原則 開(kāi)閉原則 里氏替換原則 依賴(lài)倒置原則 接口隔離原則 迪米特法則 組合/聚合復(fù)用原則 單一職責(zé)原則（Single Responsi...
摘要：在我們做系統(tǒng)設(shè)計(jì)時(shí)，經(jīng)常會(huì)設(shè)計(jì)接口或抽象類(lèi)，然后由子類(lèi)來(lái)實(shí)現(xiàn)抽象方法，這里使用的其實(shí)就是里氏替換原則。 1.開(kāi)閉原則（Open Close Principle/OCP） 定義：一個(gè)類(lèi)、模塊和函數(shù)應(yīng)該對(duì)擴(kuò)展開(kāi)放，對(duì)修改關(guān)閉。 開(kāi)放-封閉原則的意思就是說(shuō)，你設(shè)計(jì)的時(shí)候，時(shí)刻要考慮，盡量讓這個(gè)類(lèi)是足夠好，寫(xiě)好了就不要去修改了，如果新需求來(lái)，我們?cè)黾右恍╊?lèi)就完事了，原來(lái)的代碼能不動(dòng)則不動(dòng)。這個(gè)...
摘要：全棧數(shù)據(jù)之門(mén)前言自強(qiáng)不息，厚德載物，自由之光，你是我的眼基礎(chǔ)，從零開(kāi)始之門(mén)文件操作權(quán)限管理軟件安裝實(shí)戰(zhàn)經(jīng)驗(yàn)與，文本處理文本工具的使用家族的使用綜合案例數(shù)據(jù)工程，必備分析文件探索內(nèi)容探索交差并補(bǔ)其他常用的命令批量操作結(jié)語(yǔ)快捷鍵，之門(mén)提高效率光 showImg(https://segmentfault.com/img/bVK0aK?w=350&h=350); 全棧數(shù)據(jù)之門(mén) 前言 自強(qiáng)不息，...
閱讀 594·2021-11-22 14:45
閱讀 3086·2021-10-15 09:41
閱讀 1585·2021-10-11 10:58
閱讀 2807·2021-09-04 16:45
閱讀 2621·2021-09-03 10:45
閱讀 3252·2019-08-30 15:53
閱讀 1234·2019-08-29 12:28
閱讀 2146·2019-08-29 12:14
