軟體設計師--資料結構複習（排序）案例及相關知識

• 直接插入排序
• 希爾排序
• 冒泡排序
• 歸并排序
• 簡單選擇排序
• 快速排序
• 堆排序
• 基數排序

直接插入排序

一種簡單的排序方法

具體做法是：再插入第i個記錄時，R1,R2…Ri-1已經排好序，這時将關鍵字ki與關鍵字ki-1，ki-2進行比較進而找到位置插入

案例：

<3，1，4，1，5，9，6，5> 
原元素序列：監視哨（3）1,4,1,5,9,6,5
一、3 (1,3),4,1,5,9,6,5		插入時與1進行比較一次
二、4（1，3，4)1,5,9,6,5		插入時與3進行比較一次
三、1（1，1，3，4）5,9,6,5		插入時與1，3，4進行比較三次
四、5（1，1，3，4，5）9,6,5		插入時與4進行比較一次
五、9（1，1，3，4，5，9）6,5		插入時與5進行比較一次
六、6（1，1，3，4，5，6，9）5		插入時與5，9進行比較兩次
七、5（1，1，3，4，5，5，6，9）		插入時與5，6，9進行比較三次
	共比較12次
           

希爾排序

又稱“縮小增量排序”，是直接插入排序的改進

做法：

将記錄序列分割成若幹子列，然後分别進行直接插入排序。

< 3，1，4，1，5，9，6，5>  從小到大
k增量設為：4，2，1（自定，一般為n/2）即移動要比較的位置 例如：k=2，i = 1，則比較位置為 3.
一、 3，1，4，1，5，9，6，5 均 a<b無需移動 k =4
二、3，1，4，1，5，5，6，9 移動5和9 k = 2
三、1，1，3，4，5，5，6，9 插入排序 k = 1
           

冒泡排序

做法：

首先将第一個記錄的關鍵字和第二個記錄的關鍵字進行比較，若為逆序（a>b）,則交換這兩個記錄的值，然後比較第二個和第三個記錄的關鍵字，直至n-1個記錄與n個記錄比較過為止。

冒泡排序可以從前往後（1-2，2-3），也可以從後往前（n-（n-1），（（n-1）-（n-2）））

<3，1，4，1，5，9，6，5> 從小到大
第一遍排序結果
1，3，4，1，5，9，6，5
1，3，4，1，5，9，6，5
1，3，1，4，5，9，6，5
1，3，1，4，5，9，6，5
1，3，1，4，5，9，6，5
1，3，1，4，5，6，9，5
1，3，1，4，5，6，5，9
第一遍結束的标志為關鍵字最大記錄交換到第n的位置
随即開始第二趟冒泡排序，最大關鍵字交換到n-1的位置
           

歸并排序

做法：

是将兩個或兩個以上的有序檔案合并為一個新的有序檔案。

< 3，1，4，1，5，9，6，5> 
一、[1,3],[1,4],[5,9],[5,6] 	比較四次
二、[1,1,3,4],[5,5,6,9]		前半部分比較三次，後半部分比較三次
三、[1,1,3,4,5,5,6,9]		5 分别與前半部分比較一次
共比較12次
           

簡單選擇排序

做法：

通過n-i（1<=i<=n）在次關鍵字之間比較，從n-i+1個記錄中選出最小的記錄，并和第i個記錄交換，當i等于n時所有記錄有序排序。

即 3 和[1，4，1，5，9，6，5]中最小的進行交換 -1.

< 3，1，4，1，5，9，6，5>  從小到大
一、1，3，4，1，5，9，6，5  	1-3交換
二、1，1，4，3，5，9，6，5	1-3交換
三、1，1，3，4，5，9，6，5	3-4交換
四、1，1，3，4，5，5，6，9	5-9交換
	中間省略不交換循環
           

快速排序

做法：

通過一趟排序将待排序的記錄劃分為兩部分，稱為前半區和後半區，前半區中的記錄均不大于後半區的關鍵字，然後分别繼續進行快速排序，進而有序。

當i，j相等時結束排序。i，j 初始為第一個和最後一個記錄。樞軸記錄一般為第一個關鍵字的值。

< 3，1，4，1，2，9，6，5>  從小到大，標明3為樞軸即pivot
一、從右往左找到小于pivot的值
二、從左往右找到大于pviot的值
三、當都停止移動時，交換i，j的值
四、随即按照以上步驟繼續移動，直至i=j，停止檢索，将pivot的值和i=j的位置的值交換。
第一輪結束：pivot的左邊均比pivot小，右邊均比pivot大。
随後遞歸進行。
 3，1，4，1，2，9，6，5
 一、 3，1，2，1，4，9，6，5		i=2，j=4
 二、i=j=3，交換位置得 1，1，2，3，4，9，6，5	第一輪結束。
 三、重複以上步驟直至完成排序。
           

堆排序

什麼是堆：

1.必須是完全二叉樹

2.父節點的值必須大于子節點

堆的相關知識：https://www.bilibili.com/video/av47196993?from=search&seid=16388479098851201312

具體堆排序在24分鐘，但是建議看完所有視訊，講的不錯

堆排序實作：

首先滿足堆的條件，則将根節點和最後一個節點資料交換并将最後一個節點剔除，單獨儲存到數組。

接着進行堆化，讓其滿足根節點為最大值，在将根節點與最後一個節點的值進行交換，剔除最後一個節點，将其加入到之前的數組，重複以上步驟，直至排序完成。

基數排序

類似于隊列，從個位，往上，将個位數值相同的放到一個隊列裡，先進先出，比較的位數按照最大的進行比較即1441，512，12則需從個十百千依次比較，入隊，出隊，其餘位補零即0012，0512.

可視化展示：https://www.bilibili.com/video/av33889058?from=search&seid=7331912349404153369

相關資料算法看：https://blog.csdn.net/qq_25233621/article/details/80993174