八大排序演算法

⑴ 八大排序演算法與復雜度

  在處理大批量數據時，有序化的數據可以在很大程度上提高演算法效率。
直接插入排序  先總結一下數據結構的八大排序，分別是插入排序中的 直接插入排序 ， 希爾排序 ，交換排序中的 起泡排序 ， 快速排序 ，選擇排序中的 直接選擇排序 ， 堆排序 ，以及 歸並排序 和 基數排序 。
  如何評價排序的優劣呢？除了正確，易讀和容錯（自動檢錯，報錯並通過與用戶對話來糾錯）以外，性能是一個重要指標。

  演算法性能是指運行一個演算法所需要的時間長短和內存多少，他們分別稱為 時間復雜性 和 空間復雜性 。

  1）有些計算機需要用戶提供程序運行時間的上限。一旦達到這個上限，程序將被強制結束。
  2）一個正在開發的程序可能需要一個令人滿意的實時響應。
  選擇什麼樣的時間單位（程序步）來度量演算法運行時間呢？對少量的輸入，演算法瞬間就運行完了。所以對演算法性能的評價總是對大的輸入量而言的。
  假設輸入量是n，演算法運行時間是n的函數T(n)，我們研究當很大時，T(n)是什麼級別。這里就用到了 大O記法 ：如果存在正常數c和n ₀ ，使得當n≥n ₀ 時，T(n)≤ c*f(n)，則記為T(n)=O(f(n))。

  演算法所需空間包括固定部分和變動部分。固定部分與輸入量或規模無關，主要包括程序碼空間和常量，變數和對象的定長所佔的空間。變動部分與輸出量有關，主要包括遞歸棧空間和中間處理所需空間。如果用P表示演算法，S(P)表示空間需求，那麼S(P)=c（固定部分）+S _p （變動部分）。演算法的空間復雜性分析重點是變動部分S _p 。

  此外，如果一種排序實施前後，關鍵碼相同的任意兩個數據元素其前後次序沒有發生變化，那麼這個排序方法就被稱作是 穩定的 ，否則就是 不穩定的 。

原理：從待排序集的第1個數據元素開始，依次選擇數據元素，與有序子集的數據元素依次從後往前進行比較，選擇插入位置。

穩定性： 穩定 。

原理：以增量為步長劃分子序列，即同一子序列的數據元素，其下標步長等於增量。對每個子序列實施直接插入排序。不斷縮小增量，當增量為1時，所有數組元素都在一個子序列中，成為有序集。
   通俗來講，增量即為數組中元素下表的差值，假設步長為4，及a[0]，a[4]，a[8]…為一個子序列。實行直接插入排序後，將增量縮小為一半，直至增量縮小為1。

穩定性： 不穩定

原理：把數組分為左右兩個半區，左半區為有序子集，右半區為無序子集。開始時，左半區為空。在無序子集中，從後往前，兩兩相鄰元素比較，逆序則交換。最後交換的位置成為有序子集的上界。直到一趟起泡排序中沒有發生交換，排序停止。

穩定性： 穩定 。

原理：取無序子集中的第一個數據元素作為基準，將無序子集分為左右兩個半區，左半區不大於基準，右半區不小於基準；然後對左右半區重復上述操作，知道各半區元素個數為1.

穩定性： 不穩定 ，主要是劃分演算法Partition造成的。

原理：將數組分為左右兩個半區，左半區為有序子集，右半區為無序子集。開始時，有序子集為空。在無序子集中，選出最小元素，與無序子集第一個元素交換，再將第一個元素並入有序子集中。重復上述操作。

穩定性： 穩定 。

原理：
1）將數組分為左右兩個半區，左半區為有序子集，右半區為無序子集。開始時，有序子集為空。
2）將無序子集創建為大根堆。
3）將堆化為無序子集首位數據元素交換，將交換後的尾元素並入有序子集，然後把縮小的無序子集調整為大根堆。
4）重復步驟3）n-2次。

穩定性： 不穩定 。

原理：
1） 歸並 （一般指二路歸並）：將兩個有序表合成一個新的有序表。包含關鍵碼的原始數組ini分為左右兩個有序分區（歸並段）[s,m]和[m+1,e]，將他們按序歸並，一個歸並段存儲到一個輔助數組（merge）中。
2） 迭代歸並 ：包含關鍵碼的原始數組ini按長度len劃分為幾個連續的歸並段，每一個歸並段都有序，用二路歸並將相鄰歸並段合成一個長度為2len的歸並段並存入輔助數組，這個過程稱為 一趟歸並 。重復上述步驟。
 ①剩下一個長度為len的歸並段和一個長度不足len的歸並段，繼續調用二路歸並。
 ②只剩下一個長度為len或不足len的歸並段，直接移至輔助數組merge。

穩定性： 穩定 。

原理：採用「分配」和「收集」技術，從關鍵碼的低位到高位進行比較。有十個隊列作為分配用的」箱子「，編號0~9。遵照先進先出原則，從個位開始排序，到十位，百位，以此類推。

穩定性： 穩定 。

⑵ 八大演算法

演算法中比較常用的有八種演算法，基本演算法的題，都是依靠這些基礎演算法或者結合使用出題的，所以要學會基礎演算法，才有可能去更好的掌握演算法題。

插入排序，又叫直接插入排序。實際中，我們玩撲克牌的時候，就用了插入排序的思想。

基本思想：在待排序的元素中，假設前n-1個元素已有序，現將第n個元素插入到前面已經排好的序列中，使得前n個元素有序。按照此法對所有元素進行插入，直到整個序列有序。但我們並不能確定待排元素中究竟哪一部分是有序的，所以我們一開始只能認為第一個元素是有序的，依次將其後面的元素插入到這個有序序列中來，直到整個序列有序為止。

希爾排序，又稱縮小增量法。其基本思想是：

 1>先選定一個小於N的整數gap作為第一增量，然後將所有距離為gap的元素分在同一組，並對每一組的元素進行直接插入排序。然後再取一個比第一增量小的整數作為第二增量，重復上述操作…

    2>當增量的大小減到1時，就相當於整個序列被分到一組，進行一次直接插入排序，排序完成。

選擇排序，即每次從待排序列中選出一個最小值，然後放在序列的起始位置，直到全部待排數據排完即可。

如何進行堆排序呢？

步驟如下：

 1、將堆頂數據與堆的最後一個數據交換，然後對根位置進行一次堆的向下調整，但是調整時被交換到最後的那個最大的數不參與向下調整。

 2、完成步驟1後，這棵樹除最後一個數之外，其餘數又成一個大堆，然後又將堆頂數據與堆的最後一個數據交換，這樣一來，第二大的數就被放到了倒數第二個位置上，然後該數又不參與堆的向下調整…反復執行下去，直到堆中只有一個數據時便結束。此時該序列就是一個升序。

冒泡排序，該排序的命名非常形象，即一個個將氣泡冒出。冒泡排序一趟冒出一個最大（或最小）值。

快速排序是公認的排序之王，快速排序是Hoare於1962年提出的一種二叉樹結構的交換排序演算法，其基本思想為：

 任取待排序元素序列中的某元素作為基準值，按照該基準值將待排序列分為兩子序列，左子序列中所有元素均小於基準值，右子序列中所有元素均大於基準值，然後左右序列重復該過程，直到所有元素都排列在相應位置上為止。

歸並排序是採用分治法的一個非常典型的應用。其基本思想是：將已有序的子序合並，從而得到完全有序的序列，即先使每個子序有序，再使子序列段間有序。

計數排序，又叫非比較排序。顧名思義，該演算法不是通過比較數據的大小來進行排序的，而是通過統計數組中相同元素出現的次數，然後通過統計的結果將序列回收到原來的序列中。

⑶ 演算法八大排序是否都要會默寫

演算法八大排序都要會默寫。根據查詢相關公開信息得知，八大演算法指插入排序、選擇排序、冒泡排序、希爾排序、歸並排序、快速排序、堆排序、計數排序。是編程必會的知識，要熟練掌握並默寫。

⑷ 幾種排序演算法的比較

一、八大排序演算法的總體比較

4.3、堆的插入：

每次插入都是將新數據放在數組最後。可以發現從這個新數據的父結點到根結點必然為一個有序的數列，然後將這個新數據插入到這個有序數據中

（1）用大根堆排序的基本思想

先將初始數組建成一個大根堆，此對為初始的無序區；

再將最大的元素和無序區的最後一個記錄交換，由此得到新的無序區和有序區，且滿足<=的值；

由於交換後新的根可能違反堆性質，故將當前無序區調整為堆。然後再次將其中最大的元素和該區間的最後一個記錄交換，由此得到新的無序區和有序區，且仍滿足關系的值<=的值，同樣要將其調整為堆；

..........

直到無序區只有一個元素為止；

4.4：應用

尋找M個數中的前K個最小的數並保持有序；

時間復雜度：O(K)[創建K個元素最大堆的時間復雜度] +（M-K）*log(K)[對剩餘M-K個數據進行比較並每次對最大堆進行從新最大堆化]

5.希爾排序

（1）基本思想

先將整個待排序元素序列分割成若乾子序列（由相隔某個「增量」的元素組成的）分別進行直接插入排序，然後依次縮減增量再進行排序，待整個序列中的元素基本有序（增量足夠小）時，再對全體元素進行一次直接插入排序（因為直接插入排序在元素基本有序的情況下，效率很高）；

（2）適用場景

比較在希爾排序中是最主要的操作，而不是交換。用已知最好的步長序列的希爾排序比直接插入排序要快，甚至在小數組中比快速排序和堆排序還快，但在涉及大量數據時希爾排序還是不如快排；

6.歸並排序

（1）基本思想

首先將初始序列的n個記錄看成是n個有序的子序列，每個子序列的長度為1，然後兩兩歸並，得到n/2個長度為2的有序子序列，在此基礎上，再對長度為2的有序子序列進行兩兩歸並，得到若干個長度為4的有序子序列，以此類推，直到得到一個長度為n的有序序列為止；

（2）適用場景

若n較大，並且要求排序穩定，則可以選擇歸並排序；

7.簡單選擇排序

（1）基本思想

第一趟：從第一個記錄開始，將後面n-1個記錄進行比較，找到其中最小的記錄和第一個記錄進行交換；

第二趟：從第二個記錄開始，將後面n-2個記錄進行比較，找到其中最小的記錄和第2個記錄進行交換；

...........

第i趟：從第i個記錄開始，將後面n-i個記錄進行比較，找到其中最小的記錄和第i個記錄進行交換；

以此類推，經過n-1趟比較，將n-1個記錄排到位，剩下一個最大記錄直接排在最後；

⑸ 八大經典排序演算法原理及實現

該系列文章主要是記錄下自己暑假這段時間的學習筆記，暑期也在實習，抽空學了很多，每個方面的知識我都會另起一篇博客去記錄，每篇頭部主要是另起博客的鏈接。

冒泡排序演算法應該是大家第一個接觸的演算法，其原理都應該懂，但我還是想以自己的語言來敘述下其步奏：

按照計算時間復雜度的規則，去掉常數、去掉最高項系數，其復雜度為O(N^2)
冒泡排序及其復雜度分析

空間復雜度就是在交換元素時那個臨時變數所佔的內存

給定一個整數序列{6,1,2,3,4},每完成一次外層循環的結果為：

我們發現第一次外層循環之後就排序成功了，但是還是會繼續循環下去，造成了不必要的時間復雜度，怎麼優化？

冒泡排序都是相鄰元素的比較，當相鄰元素相等時並不會交換，因此冒泡排序演算法是穩定性演算法

插入排序是對冒泡排序的一種改進

插入排序的思想是數組是部分有序的，再將無序的部分插入有序的部分中去,如圖：
（圖片來自 這里 ）

空間復雜度就是在交換元素時那個臨時變數所佔的內存

插入排序的優化，有兩種方案：

文章後面會給出這兩種排序演算法

由於插入排序也是相鄰元素的比較，遇到相等的相鄰元素時不會發生交換，也不會造成相等元素之間的相對位置發生變化

其原理是從未排序的元素中選出最小值(最大值)放在已排序元素的後面

空間復雜度就是在交換元素時那個臨時變數所佔的內存

選擇排序是不穩定的，比如 3 6 3 2 4，第一次外層循環中就會交換第一個元素3和第四個元素2，那麼就會導致原序列的兩個3的相對位置發生變化

希爾排序算是改良版的插入排序演算法，所以也稱為希爾插入排序演算法

其原理是將序列分割成若乾子序列（由相隔某個 增量 的元素組成的），分別進行直接插入排序；接著依次縮小增量繼續進行排序，待整個序列基本有序時，再對全體元素進行插入排序，我們知道當序列基本有序時使用直接插入排序的效率很高。
上述描述只是其原理，真正的實現可以按下述步奏來：

希爾排序的效率取決於 增量值gap 的選取，這涉及到數學上尚未解決的難題，但是某些序列中復雜度可以為O(N 1.3)，當然最好肯定是O(N)，最壞是O(N 2)

空間復雜度就是在交換元素時那個臨時變數所佔的內存

希爾排序並不只是相鄰元素的比較，有許多跳躍式的比較，難免會出現相同元素之間的相對位置發生變化，所以希爾排序是不穩定的

理解堆排序，就必須得先知道什麼是堆？

二叉樹的特點：

當父節點的值總是大於子結點時為 最大堆 ；反之為 最小堆 ，下圖就為一個二叉堆

一般用數組來表示堆，下標為 i 的結點的父結點下標為(i-1)/2；其左右子結點分別為 (2 i + 1)、(2 i + 2)

怎麼將給定的數組序列按照堆的性質，調整為堆？

這里以建立最小堆為示例，

很明顯對於其葉子結點來說，已經是一個合法的子堆，所以做堆調整時，子節點沒有必要進行，這里只需從結點為A[4] = 50的結點開始做堆調整，即從（n/2 - 1）位置處向上開始做堆調整：

由於每次重新恢復堆的時間復雜度為O(logN)，共N - 1次重新恢復堆操作，再加上前面建立堆時N / 2次向下調整，每次調整時間復雜度也為O(logN)，二次操作時間相加還是O(N logN)。故堆排序的時間復雜度為O(N * logN)。

空間復雜度就是在交換元素時那個臨時變數所佔的內存

由於堆排序也是跨越式的交換數據，會導致相同元素之間的相對位置發生變化，則演算法不穩定。比如 5 5 5 ,堆化數組後將堆頂元素5與堆尾元素5交換，使得第一個5和第三個5的相對位置發生變化

歸並排序是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

快速排序在應該是大家經常看到、聽到的演算法，但是真正默寫出來是有難度的。希望大家看了下面 挖坑填數 方法後，能快速寫出、快速排序。

其原理就這么幾句話，但是現實起來並不是這么簡單，我們採取流行的一種方式 挖坑填數分治法

對於序列： 72 6 57 88 60 42 83 73 48 85

數組變為： 48 6 57 88 60 42 83 73 88 85
再重復上面的步驟，先從後向前找，再從前向後找：

數組變為： 48 6 57 42 60 72 83 73 88 85
可以看出a[5]前面的數字都小於它，a[5]後面的數字都大於它。因此再對a[0…4]和a[6…9]這二個子區間重復上述步驟就可以了

空間復雜度，主要是遞歸造成的棧空間的使用:

快速排序的優化主要在於基準數的選取

快速排序也是跨越式比較及交換數據，易導致相同元素之間的相對位置發生變化，所以快速排序不穩定

前面也說了二分查找排序是改進的插入排序，不同之處在於，在有序區間查找新元素插入位置時，為了減少比較次數提高效率，採用二分查找演算法進行插入位置的確定
具體步驟，設數組為a[0…n]：

二分查找插入位置，因為不是查找相等值，而是基於比較查插入合適的位置，所以必須查到最後一個元素才知道插入位置。
二分查找最壞時間復雜度：當2^X>=n時，查詢結束，所以查詢的次數就為x，而x等於log2n（以2為底，n的對數）。即O(log2n)
所以，二分查找排序比較次數為：x=log2n
二分查找插入排序耗時的操作有：比較 + 後移賦值。時間復雜度如下：

二分查找排序在交換數據時時進行移動，當遇到有相等值插入時也只會插入其後面，不會影響其相等元素之間的相對位置，所以是穩定的

白話經典演算法排序
冒泡排序選擇排序
快速排序復雜度分析
優化的插入排序

⑹ java的都學習哪些內容

學習java是個不錯的選擇，java在it行業需求的人才每年占上百萬個，並且平均每個月薪資也是在1.8W左右。

如果想達到工作標准可以參考下面的內容：

1.Java SE部分 初級語法，面向對象，異常，IO流，多線程，Java Swing，JDBC，泛型，註解，反射等。

2.資料庫部分，基礎的sql語句，sql語句調優，索引，資料庫引擎，存儲過程，觸發器，事務等。

3. 前端部分， HTML5 CSS3 JS， HTML DOM Jquery BootStrap等。

4. Java EE部分，Tomcat和Nginx伺服器搭建，配置文件，Servlet，JSP，Filter，Listener，http協議，MVC等。

5. 框架部分，每個框架都可以分開學，在去學如何使用SSM 或者SSH框架，如何搭建，如何整合。開發中為什麼會用框架，Rest是啥？Spring為啥經久不衰，底層如何實現等。

6.23種設計模式，掌握常用的，比如單例模式的多種實現，責任鏈模式，工廠模式，裝飾器模式等，了解常用場景。

7. 基礎演算法和數據結構，八大排序演算法，查找演算法。

8. 熟練使用maven等構建工具，git等版本控制工具，熟悉常用linux命令，log4j，bug，junit單元測試，日誌列印工具，Redis等NoSql。

互聯網行業目前還是最熱門的行業之一，學習IT技能之後足夠優秀是有機會進入騰訊、阿里、網易等互聯網大廠高薪就業的，發展前景非常好，普通人也可以學習。

想要系統學習，你可以考察對比一下開設有相關專業的熱門學校，好的學校擁有根據當下企業需求自主研發課程的能力，能夠在校期間取得大專或本科學歷，中博軟體學院、南京課工場、南京北大青鳥等開設相關專業的學校都是不錯的，建議實地考察對比一下。

祝你學有所成，望採納。

⑺ 數據結構-八大排序演算法的時間復雜度 穩定性

1：直接插入排序：
最好：待排序已經有序， 從前往後走都不用往裡面 插入。 時間復雜度為o(n)
最壞：待排序列是逆序，每一次都要移位插入。 時間復雜度o(n^2)
是穩定排序

2：希爾排序：
最好：縮小增量的插入排序，待排序已經有序。時間復雜度o(n）
一般：平均時間復雜度o(n ^{1.3)，最差也是時間復雜度o(n} 1.3)
不穩定排序

3：冒泡排序：
最好：待排序已經有序。時間復雜度o(n）
最壞：待排序是逆序。時間復雜度o(n^2）
穩定排序

4：快速排序：
最好：待排序無序。時間復雜度o(nlogn)
最壞: 待排序已經有序，基準定義在開始。 時間復雜度為o(n^2)
不穩定排序

5：直接選擇排序：
無論好壞:o(n^2)
穩定排序

6：堆排序：
無論好壞：時間復雜度o(nlogn)
不穩定排序

7：歸並排序：

穩定排序

8：基數排序：
無論好壞:o(d(n+r)) ，r為基數，d為位數.
穩定排序

⑻ iOS演算法系列（二）- 八大排序演算法

排序演算法也算是老生常談了，如果你大學專業是計算機或軟體，甚至你參加過國二國三都會學到排序演算法，如果我沒猜錯的話你接觸的第一個演算法是冒泡。
排序演算法老生常談，但確實多少大廠面試題中的必考題。
廢話不多說，開始正題
常見的八種排序演算法他們的關系如下：

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個演算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

希爾排序是基於插入排序的以下兩點性質而提出改進方法的：
插入排序在對幾乎已經排好序的數據操作時， 效率高， 即可以達到線性排序的效率
但插入排序一般來說是低效的， 因為插入排序每次只能將數據移動一位

希爾排序的基本思想是：先將整個待排序的記錄序列分割成為若乾子序列分別進行直接插入排序，待整個序列中的記錄「基本有序」時，再對全體記錄進行依次直接插入排序。

說基數排序之前，我們簡單介紹桶排序：
演算法思想：是將陣列分到有限數量的桶子里。每個桶子再個別排序（有可能再使用別的排序演算法或是以遞回方式繼續使 用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結果。當要被排序的陣列內的數值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序並不是 比較排序，他不受到 O(n log n) 下限的影響。
簡單來說，就是把數據分組，放在一個個的桶中，然後對每個桶裡面的在進行排序。
例如要對大小為[1..1000]范圍內的n個整數A[1..n]排序

各種排序的穩定性，時間復雜度、空間復雜度、穩定性總結如下圖：