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