您現在的位置是：首頁 > 棋牌
八大排序演算法（交換排序：氣泡排序與快速排序；選擇排序：簡單選擇排序與堆排序，這四種排序已經完成）與三大查詢方法
- 由 紙鶴視界 發表于 棋牌
- 2022-08-20
堆頂怎麼調整
八大排序方法
分類
：
內部排序：
指將需要處理的所有資料都載入到內部儲存器中進行排序。
外部排序法：
資料量過大，無法全部載入到記憶體中，需要藉助外部儲存進行排序。
效能比較
交換排序
氣泡排序
氣泡排序（Bubble Sorting）的基本思想是：透過對待排序序列從前向後（從下標較小的元素開始），依次比較相鄰元素的值，若發現逆序則交換，使值較大的元素逐漸從前移向後部，就象水底下的氣泡一樣逐漸向上冒。
倆倆比較，小的換在前，大的換在後面，依次向後迴圈這個過程
最佳化
因為排序的過程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序，因此要在排序過程中設定一個標誌flag判斷元素是否進行過交換。從而減少不必要的比較。（這裡說的最佳化，可以在氣泡排序寫好後，在進行）
// // 將前面額氣泡排序演算法，封裝成一個方法 public static void bubbleSort（int［］ arr） { // 氣泡排序 的時間複雜度 O（n^2）， 自己寫出 int temp = 0； // 臨時變數 boolean flag = false； // 標識變數，表示是否進行過交換 for （int i = 0； i < arr。length - 1； i++） { for （int j = 0； j < arr。length - 1 - i； j++） { // 如果前面的數比後面的數大，則交換 if （arr［j］ > arr［j + 1］） { flag = true； temp = arr［j］； arr［j］ = arr［j + 1］； arr［j + 1］ = temp； } } //System。out。println（“第” + （i + 1） + “趟排序後的陣列”）； //System。out。println（Arrays。toString（arr））； if （！flag） { // 在一趟排序中，一次交換都沒有發生過 break； } else { flag = false； // 重置flag！！！， 進行下次判斷 } } }
快速排序
快速排序
（Quicksort）是對氣泡排序的一種改進。
基本思想是：透過一趟排序將要排序的資料分割成獨立的兩部分，其中
一部分的所有資料
都
比另外一部分的所有資料
都要
小
，然後再按此方法
對這兩部分資料分
別進行
快速排序
，整個排序過程可以
遞迴進行
，以此
達到
整個
資料變成有序序列
。
過程
對6 1 2 7 9 3 4 5 10 8 進行排序
首先哨兵j開始出動。因為此處設定的基準數是最左邊的數，所以需要讓哨兵
j先出動
，這一點非常重要。哨兵
j
一步一步地
向左挪動
（即
j–-
），直到找到一個
小於6的數停
下來。
接下來
哨兵
i
再一步一步
向右挪動
（即
i++
），直到找到一個數
大於6的數停
下來。最後哨兵
j停在了數字5
面前，哨兵
i停在了數字7
面前。
交換
哨兵i和哨兵j所指向的
元素的值
。交換之後的序列如下。 6 1 2
5
9 3 4
7
10 8
到此，第一次交換結束。接下來開始哨兵
j繼續向左挪動
（再友情提醒，
每次必須是哨兵j先出發
）。他發現了
4
（比基準數6要小，滿足要求）
之後停
了下來。哨兵
i
也
繼續向右挪動
的，他發現了
9
（比基準數6要大，滿足要求）
之後停
了下來。此時
再次進行交換
，交換之後的序列如下： 6 1 2 5 4 3 9 7 10 8
當i和j指向的數相等時，交換基準數與該該數，到此第一輪“探測”結束。此時以基準數6為分界點，6左邊的數都小於等於6，6右邊的數都大於等於6。
回顧剛才的過程，其實哨兵j的使命就是要找小於基準數的數，而哨兵i的使命就是要找大於基準數的數，直到i和j碰頭為止。
透過上面的步驟，使基準數6已經歸位，它正好處在序列的第6位。此時我們已經將原來的序列，以6為分界點拆分成了兩個序列，左邊的序列是“3 1 2 5 4”，右邊的序列是“9 7 10 8”。
接下來還需要分別處理這兩個序列。使6左邊和右邊的序列有序，只要模擬剛才的方法分別處理6左邊和右邊的序列即可。
首先處理6左邊的序列現，左邊的序列是“3 1 2 5 4”。將這個序列以3為基準數進行調整，使得3左邊的數都小於等於3，3右邊的數都大於等於3。
因為j往又右挪到動，i往左挪到，會在2的時候碰面，所以2會與3進行互動。調整完畢之後的序列的順序應該是：“ 2 1 3 5 4”。現在3已經歸位。
接下來需要處理3左邊的序列“2 1”和右邊的序列“5 4”。對序列“2 1”以2為基準數進行調整，處理完畢之後的序列為“1 2”，到此2已經歸位。序列“1”只有一個數，也不需要進行任何處理。至此我們對序列“2 1”已全部處理完畢，得到序列是“1 2”。序列“5 4”的處理也仿照此方法，最後得到的序列如下：1 2 3 4 5 6 9 7 10 8
對於序列“9 7 10 8”也模擬剛才的過程，直到不可拆分出新的子序列為止。最終將會得到這樣的序列，如下：1 2 3 4 5 6 7 8 9 10
到此，排序完全結束。我們可以發現，快速排序的每一輪處理其實就是將這一輪的基準數歸位，直到所有的數都歸位為止，排序就結束了。下面是整個演算法的處理過程。
快速排序
之所比較快，因為相比氣泡排序，
每次交換是跳躍式的
。每次排序的時候設定一個基準點，將小於等於基準點的數全部放到基準點的左邊，將大於等於基準點的數全部放到基準點的右邊。這樣在每次交換的時候就不會像
氣泡排序
一樣
每次只能在相鄰的數之間進行交換
，交換的距離就大的多了。因此
總的比較和交換次數就少了，速度自然就提高了
。當然在最壞的情況下，仍可能是相鄰的兩個數進行了交換。因此快速排序的最差時間複雜度和氣泡排序是一樣的都是O（N2），它的平均時間複雜度為O（NlogN）。
程式碼
//方法1：便於理解public static void quickSort2（int［］ arr，int low，int high）{ int i，j，temp，t； if（low>high）{ return； } i=low；//起始位 j=high； //temp就是基準位 temp = arr［low］； while （i
選擇排序
選擇排序：每趟從待排序的記錄中選出關鍵字最小的記錄，順序放在已排序的記錄序列末尾，直到全部排序結束為止。
簡單選擇排序
從第一個元素i開始，預設該元素已經被排序；
取出下一個元素j，在已經排序的元素序列中從後往前掃描
如果下一個元素j，小於之前已經被排序完的序列的最後一個元素i，則將元素j移動到i的前面
重複步驟3，直到之前已經排序完的元素都比小於或者等於下一個元素j
將元素j插入到步驟4所找到的那個元素之後
重複2到5步驟
舉例：對 9 1 2 5 7 4 8 6 3 5進行簡單選擇排序
所以排序後為：1 2 3 4 5 5 6 7 8 9
堆排序
堆是具有以下性質的完全二叉樹
每個結點的值都大於或等於其左右孩子結點的值，稱為
大頂堆
；
每個結點的值都小於或等於其左右孩子結點的值，稱為
小頂堆
。
堆排序是將堆中的結點
按照寬度優先將其進行編號
，將這種邏輯結構對映到陣列中
下圖為大頂堆的對映
堆排序基本思想
：
將待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。
將其與末尾元素進行交換，此時末尾就為最大值。
然後將剩餘n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值。
反覆執行123，便能得到一個有序序列了
將4 6 8 5 9進行堆排序
第一步：將給出的無序序列
構成一個大頂堆
（
一般升序採用大頂堆，降序採用小頂堆
）
1。將無序序列構建為二叉樹，按照寬度優先進行構建
2。 從最後一個非葉子結點6開始，從左至右，從下至上進行調整。
3。找到第二個非葉節點4，由於［4，9，8］中9元素最大，4和9交換。
4。交換導致了子根［4，5，6］結構混亂，繼續調整，［4，5，6］中6最大，交換4和6。無需序列構已經造成了一個大頂堆。
第二步：將堆頂元素與末尾元素進行交換，使末尾元素最大。然後繼續調整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反覆進行交換、重建、交換。
1。將堆頂元素9和末尾元素4進行交換
2。重新調整結構，使其繼續滿足堆定義
3。再將堆頂元素8與末尾元素5進行交換，得到第二大元素8。
4。按照123步驟，繼續進行調整，交換，如此反覆進行，最終使得整個序列有序
堆排序參考連結
插入排序
直接插入排序
希爾排序
歸併排序
基數排序
三大查詢方法
順序查詢演算法
順序查詢的基本思想
：
從表的一端開始，順序掃描表，依次將掃描到的結點關鍵字和給定值（假定為a）相比較，
若當前結點關鍵字與a相等，則查詢成功；
若掃描結束後，仍未找到關鍵字等於a的結點，則查詢失敗。
說白了就是，從頭到尾，一個一個地比，找著相同的就成功，找不到就失敗。
很明顯的缺點就是
查詢效率低
。
適用
於
線性表的順序儲存結構
和
鏈式儲存結構
。
public
static
int
sequentialSearch
（
int
［
］
a
，
int
key
）
{
for
（
int
i
=
0
；
i
<
a
。
length
；
i
++
）
{
if
（
a
［
i
］
==
key
）
return
i
；
}
return
-
1
；
}
順序表查詢最佳化
因為每次迴圈時都需要對i是否越界，即是否小於等於n作判斷。事實上，還可以有更好一點的辦法，設定一個哨兵，可以解決不需要每次讓i與n作比較。看下面的改進後的順序查詢演算法程式碼。
public
static
int
sequentialSearch2
（
int
［
］
a
，
int
key
）
{
int
index
=
a
。
length
-
1
；
a
［
0
］
=
key
；
// 將下標為0的陣列元素設定為哨兵
while
（
a
［
index
］
！=
key
）
{
index
——
；
}
return
index
；
}
折半查詢
折半查詢（Binary Search）技術，又稱為二分查詢。它的前提是線性表中的記錄必須是關
鍵碼有序（通常從小到大有序）
，
線性表必須採用順序儲存
。
折半查詢的基本思想是
：
在有序表中，
取中間記錄
作
為比較物件
，
若給定值與中間記錄的關鍵字相等，則查詢成功；
若給定值小於中間記錄的關鍵字，則在中間記錄的左半區繼續查詢；
若給定值大於中間記錄的關鍵字，則在中間記錄的右半區繼續查詢。
不斷重複上 述過程，直到查詢成功，或所有查詢區域無記錄，查詢失敗為止。
public
static
int
binarySearch
（
int
［
］
a
，
int
key
）
{
int
low
，
mid
，
high
；
low
=
0
；
// 最小下標
high
=
a
。
length
-
1
；
// 最大小標
while
（
low
<
high
）
{
mid
=
（
high
+
low
）
/
2
；
// 折半下標
if
（
key
>
a
［
mid
］
）
{
low
=
mid
+
1
；
// 關鍵字比 折半值 大，則最小下標 調成 折半下標的下一位
}
else
if
（
key
<
a
［
mid
］
）
{
high
=
mid
-
1
；
// 關鍵字比 折半值 小，則最大下標 調成 折半下標的前一位
}
else
{
return
mid
；
// 當 key == a［mid］ 返回 折半下標
}
}
return
-
1
；
}
最終我們折半演算法的時間複雜度為O（logn），它顯然遠遠好於順序查詢的O（n）時間複雜度了。
二分查詢特別適用於那種一經建立就很少改動而又經常需要查詢的線性表。
分塊查詢
又稱索引順序查詢，這是順序查詢的一種改進方法，用於在分塊有序表中進行查詢 。
主表：儲存資料的表，長度n；
索引表：將主表分塊，每塊長s，找出每塊中的關鍵字最大值，並且儲存該塊中所有資料在主表中的索引
（1）分塊：將n個數據元素“按塊有序”劃分為m塊。
每一塊中的結點不必有序，但塊與塊之間必須“按塊有序”；即第1塊中任一元素的關鍵字都必須小於第2塊中任一元素的關鍵字；而第2塊中任一元素又都必須小於第3塊中的任一元素。每個塊中元素不一定是有序的。
（2）根據查詢值，和索引表中關鍵字（每塊中的最大關鍵字）比較，透過對分查詢/順序查詢，找到該值所在的塊範圍；
（3）在相應塊中，找到該值在主表中的位置。
平均查詢長度ASL<=O（log2（n/s））+s/2 （先對分查詢，或順序查詢）
，https：//blog。csdn。net/yyuggjggg/article/details/120807921