選擇排序：首先找到數(shù)組中最小的那個(gè)元素，其次將它和數(shù)組第一個(gè)元素交換位置（如果第一個(gè)元素就是最小元素那么它就和自己交換）。再次，在剩下的元素中找到最小的元素，將它與數(shù)組的第二個(gè)元素交換。

插入排序：遍歷數(shù)組（原址排序），將每一個(gè)數(shù)插入到之前排序好了的部分?jǐn)?shù)組中的適當(dāng)?shù)奈恢?，并將?要插入的位置的右邊 到 當(dāng)前遍歷到的位置 之間的數(shù)右移一位（參考以下例子）（具體實(shí)現(xiàn)是將遍歷到的數(shù) 與 左邊（左邊部分?jǐn)?shù)組已經(jīng)是有序的）的數(shù)進(jìn)行比較 如果不符合順序就交換，如果符合就到達(dá)了適當(dāng)?shù)奈恢茫?/p>

• 具體例子:圖表演示

  
  
  圖片.png

希爾排序(改進(jìn)的插入排序算法, 將移動(dòng)間隔增加為一個(gè)比較大的數(shù), 用1,4,13,40.... 3n + 1, 中較大的一個(gè)數(shù), 然后遞減為遞增數(shù)組中較小的一個(gè)數(shù),直至為1)

• 例子(暫無(wú))

歸并排序

• 自頂向下排序
  (加粗表示當(dāng)前操作的部分)
  
  圖片.png
• 自下向上排序
  加粗表示當(dāng)前操作部分
  
  圖片.png
• 歸并排序的一些改進(jìn)建議:
  • 對(duì)于已經(jīng)足夠小的數(shù)組, 用別的排序方法(例如選擇排序), 有助于提高算法性能
  • 測(cè)試數(shù)組是否有序, 即測(cè)試要?dú)w并的兩個(gè)數(shù)組的 前一個(gè)數(shù)組的最后一個(gè)小于后一個(gè)數(shù)組的最前一個(gè).
• 不將元素復(fù)制到輔助數(shù)組, 而是通過(guò)歸并排序到一個(gè)新的數(shù)組,然后再歸并排序回來(lái)原來(lái)的數(shù)組(如此來(lái)回切換), 來(lái)使得復(fù)制數(shù)組的花銷(xiāo)變小.

快速排序

• 基本思想:
  • 先使數(shù)組大致有序, 然后對(duì)小數(shù)組繼續(xù)遞歸使用 大致排序 ,直到最后剩下一個(gè)元素
• 第一種實(shí)現(xiàn): 從數(shù)組往右遍歷,如果遇到比要對(duì)比的數(shù)小或者等于的數(shù), 較小數(shù)組index_1+1，遍歷數(shù)組的index_0暫時(shí)不變，然后交換 arr[index_1]、arr[index_0] 。index_0再+1。如果遇到比要對(duì)比的數(shù)大的數(shù)，index_0 + 1, index_1 不變。直到遍歷完數(shù)組，最后交換arr[0]、arr[index_1]
• 第二種實(shí)現(xiàn)：從數(shù)組往右遍歷，直到遇到比要對(duì)比的數(shù)大的數(shù)停止，當(dāng)前下標(biāo) index_0，然后從右往左遍歷數(shù)組，直到遇到比要對(duì)比的數(shù)小的數(shù)停止，當(dāng)前下標(biāo)index_1，交換arr[index_0]、arr[index_1]。直到index_0>=index_1，最后交換arr[index_1]、arr[0]
• 快速排序的幾個(gè)注意點(diǎn)
• 原地切分
• 別越界（如果要切分的元素是數(shù)組中最大的或者最小的，別讓下標(biāo)跑到數(shù)組外面）
• 保存隨機(jī)性
• 終止循環(huán)的確定性
• 處理重復(fù)值情況
• 終止遞歸
• 提高性能的一些常用建議
• 對(duì)于小規(guī)模數(shù)組，使用其他排序方法
• 對(duì)于重復(fù)元素特別多情況，可以采用三切法，將元素分為小于、等于、大于三部分

優(yōu)先隊(duì)列--基于堆數(shù)據(jù)結(jié)構(gòu)

• 堆數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)
  * 使用數(shù)組實(shí)現(xiàn)即可,不使用第一個(gè)位置 arr[0], 基于完全二叉樹(shù)
• 維護(hù)堆的特性:
  • 上升:一個(gè)堆底的元素,上升,直到遇到一個(gè)比他大的父元素
  • 下沉:一個(gè)堆頂?shù)脑?下沉(和較大的子節(jié)點(diǎn)交換),直到遇到兩個(gè)比他小的子節(jié)點(diǎn)
• 實(shí)現(xiàn)優(yōu)先隊(duì)列的兩個(gè)關(guān)鍵操作
  • 插入一個(gè)元素: 將新元素放置堆的末尾, 然后使用上升將該元素放置適合的位置
  • 刪除一個(gè)元素: 將堆頂?shù)脑貏h除,然后將堆末尾的元素放置堆頂, 然后使用下沉, 將該元素放置適合的位置
• 使用堆進(jìn)行排序--堆排序

排序的思考

• 將各種數(shù)據(jù)排序（通過(guò)引用）
• 如何選擇排序算法

幾個(gè)注意的地方:

• 多叉堆
• 適當(dāng)加入調(diào)整數(shù)組大小的邏輯, 以防止出現(xiàn)下標(biāo)溢出
• 元素不可變性: 保證元素放入堆后, 無(wú)法改變其值
• 通過(guò)使用索引(比如Integer類(lèi)型), 快速對(duì)元素進(jìn)行操作(雖然會(huì)花費(fèi)額外的空間).但是只對(duì)索引進(jìn)行操作,不管插入. 刪除. 交換. 等速度會(huì)快很多