java 合并排序算法、冒泡排序算法、選擇排序算法、插入排序算法、快速排序算法的描述
2019-11-26 16:19:31
供稿：網友
算法是在有限步驟內求解某一問題所使用的一組定義明確的規則。通俗點說，就是計算機解題的過程。在這個過程中，無論是形成解題思路還是編寫程序，都是在實施某種算法。前者是推理實現的算法，后者是操作實現的算法。
一個算法應該具有以下五個重要的特征：
1.有窮性： 一個算法必須保證執行有限步之后結束；
2.確切性： 算法的每一步驟必須有確切的定義；
3.輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始情況；
4.輸出：一個算法有一個或多個輸出，以反映對輸入數據加工后的結果。沒有輸出的算法是毫無意義的；
5.可行性： 算法原則上能夠精確地運行，而且人們用筆和紙做有限次運算后即可完成。
合并排序（MERGE SORT）是又一類不同的排序方法，合并的含義就是將兩個或兩個以上的有序數據序列合并成一個新的有序數據序列，因此它又叫歸并算法。它的基本思想就是假設數組A有N個元素，那么可以看成數組A是又N個有序的子序列組成，每個子序列的長度為1，然后再兩兩合并，得到了一個 N/2 個長度為2或1的有序子序列，再兩兩合并，如此重復，值得得到一個長度為N的有序數據序列為止，這種排序方法稱為2―路合并排序。
例如數組A有7個數據，分別是： 49 38 65 97 76 13 27，那么采用歸并排序算法的操作過程如圖7所示：
初始值 [49] [38] [65] [97] [76] [13] [27]
看成由長度為1的7個子序列組成
第一次合并之后 [38 49] [65 97] [13 76] [27]
看成由長度為1或2的4個子序列組成
第二次合并之后 [38 49 65 97] [13 27 76]
看成由長度為4或3的2個子序列組成
第三次合并之后 [13 27 38 49 65 76 97]
圖6 歸并排序算法過程圖
合并算法的核心操作就是將一維數組中前后相鄰的兩個兩個有序序列合并成一個有序序列。合并算法也可以采用遞歸算法來實現，形式上較為簡單,但實用性很差。
合并算法的合并次數是一個非常重要的量,根據計算當數組中有3到4個元素時,合并次數
是2次,當有5到8個元素時,合并次數是3次,當有9到16個元素時,合并次數是4次，按照這一規律，當有N個子序列時可以推斷出合并的次數是
X（2>=N,符合次條件的最小那個X）。
冒泡算法描述：
在解釋冒泡排序算法之前，先來介紹把10個數（放在數組A中）中最大的那個數放在最后位置上的一種算法。算法描述如下：
（1）從數組A[1]到A[10]，把相臨的兩個數兩兩進行比較。即A[1]和A[2]比較，比較完后A[2]再與A[3]比較，……最后是A[9]和A[10]比較。
(2)在每次進行比較的過程中，如果前一個數比后一個數大，則對調兩個數，也就是說把較大的數調到后面，較小的調到前面。比如在第一次的比較中，如果A[1]比A[2]大則A[1]和A[2]的值就互換。下圖用6個數據來說明以上的算法。
假設6個數據是：A[]=5 7 4 3 8 6
A[1] A[2] A[3] A[4] A[5] A[6]
5 7 4 3 8 6 第一次，A[1]=5和A[2]=7比較，7>5，不進行對調。
5 7 4 3 8 6 第二次，A[2]=7和A[3]=4比較，4<7，進行對調，
那么第二次比較完后的數據是5 4 7 3 8 6
5 4 7 3 8 6 第三次，A[3]=7和A[4]=3比較，3<7，進行對調，
那么第三次比較完后的數據是5 4 3 7 8 6
5 4 3 7 8 6 第四次，A[4]=7和A[5]=8比較，8>7,不進行對調。
5 4 3 7 8 6 第五次，A[6]=6和A[5]=8比較，6<8，進行對調，
那么第五次也就是最后一次的結果是
5 4 3 7 6 8
*******************************************************
選擇排序算法描述：
在介紹選擇排序法之前先介紹一種把最小的數放在第一個位置上的算法，當然也可以用前面所講的冒泡排序法，現在我們改用一種新的算法：其指導思想是先并不急于調換位置，先從A[1]開始逐個檢查，看哪個數最小就記下該數所在的位置P，等一躺掃描完畢，再把A[P]和A[1]對調，這時A[1]到A[10]中最小的數據就換到了最前面的位置。算法的步驟如下：
1）、先假設A[1]中的數最小，記下此時的位置P=1；
2）、依次把A[P]和A[I]（I從2變化到10）進行比較，每次比較時，若A[I]的數比A[P]中的數小，則把I的值賦給P，使P總是指向當前所掃描過的最小數的位置，也就是說A[P]總是等于所有掃描過的數最小的那個數。在依次一一比較后，P就指向10個數中最小的數所在位置，即A[P]就是10個數中最小的那個數；
3）把A[P]和A[1]的數對調，那么最小的數就在A[1]中去了，也就是在最前面了。
如果現在重復此算法，但每重復一次，進行比較的數列范圍就向后移動一個位置。即第二遍比較時范圍就從第2個數一直到第N個數，在此范圍內找最小的數的位置P，然后把A[P]與A[2]對調，這樣從第2個數開始到第N個數中最小數就在A[2]中了，第三遍就從第3個數到第N個數中去找最小的數，再把A[P]與A[3]對調……此過程重復N-1次后，就把A數組中N個數按從小到大的順序排好了。這種排序的方法就是選擇排序法
*****************************************************************
插入排序算法描述：
通過學習上述兩種方法可以了解排序的基本思想，也可以對任何一個無序數組作出從大到?。ń敌颍┗驈男〉酱螅ㄉ颍┑呐帕小，F在假設有一個已經有序的數據序列，要求在這個已經排好的數據序列中插入一個數，但要求插入后此數據序列仍然有序，這個時候就要用到一種新的排序方法――插入排序法,插入排序的基本操作就是將一個數據插入到已經排好序的有序數據中,從而得到一個新的、個數加一的有序數據。
題目：A數組中有N個數據，按從小到大的順序排列，輸入一個數X，把X的值插入到數組A中，使得插入后的A數組仍然按從小到大排列。
那么這個問題的解決算法就是：
1）、通過比較大小找到X應插入的位置，假如應該放在第I個位置；
2）、把從I開始的（包括I）的所有數組元素依次向后移動一個位置，即A[I+1]：=A[I]；
快速排序是對冒泡排序的一種改進。它的基本思想是：通過一躺排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一不部分的所有數據都要小，然后再按次方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
假設要排序的數組是A[1]……A[N]，首先任意選取一個數據（通常選用第一個數據）作為關鍵數據，然后將所有比它的數都放到它前面，所有比它大的數都放到它后面，這個過程稱為一躺快速排序。一躺快速排序的算法是：
1）、設置兩個變量I、J，排序開始的時候I：=1，J：=N；
2）以第一個數組元素作為關鍵數據，賦值給X，即X：=A[1]；
3）、從J開始向前搜索，即由后開始向前搜索（J：=J-1），找到第一個小于X的值，兩者交換；
4）、從I開始向后搜索，即由前開始向后搜索（I：=I+1），找到第一個大于X的值，兩者交換；
5）、重復第3、4步，直到I=J；
例如：待排序的數組A的值分別是：（初始關鍵數據X：=49）
A[1] A[2] A[3] A[4] A[5] A[6] A[7]：
49 38 65 97 76 13 27
進行第一次交換后： 27 38 65 97 76 13 49
( 按照算法的第三步從后面開始找
進行第二次交換后： 27 38 49 97 76 13 65
( 按照算法的第四步從前面開始找>X的值，65>49,兩者交換，此時I：=3 )
進行第三次交換后： 27 38 13 97 76 49 65
( 按照算法的第五步將又一次執行算法的第三步從后開始找
進行第四次交換后： 27 38 13 49 76 97 65
( 按照算法的第四步從前面開始找大于X的值，97>49,兩者交換，此時J：=4 )
此時再執行第三不的時候就發現I=J，從而結束一躺快速排序，那么經過一躺快速排序之后的結果是：27 38 13 49 76 97 65，即所以大于49的數全部在49的后面，所以小于49的數全部在49的前面。
快速排序就是遞歸調用此過程――在以49為中點分割這個數據序列，分別對前面一部分和后面一部分進行類似的快速排序，從而完成全部數據序列的快速排序，最后把此數據序列變成一個有序的序列，根據這種思想對于上述數組A的快速排序的全過程如圖6所示：
初始狀態 {49 38 65 97 76 13 27}
進行一次快速排序之后劃分為 {27 38 13} 49 {76 97 65}
分別對前后兩部分進行快速排序 {13} 27 {38}
結束 結束 {49 65} 76 {97} 49 {65} 結束
結束
*************************************************************************
圖6 快速排序全過程
快速排序的算法描述
1）、設有N（假設N=10）個數，存放在S數組中；
2）、在S[1。。N]中任取一個元素作為比較基準，例如取T=S[1]，起目的就是在定出T應在排序結果中的位置K，這個K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的數都小于S[K]，在S[K]以后的數都大于S[K]；
3）、利用分治思想（即大化小的策略）可進一步對S[1。。K-1]和S[K+1。。N]兩組數據再進行快速排序直到分組對象只有一個數據為止。
如具體數據如下，那么第一躺快速排序的過程是：
數組下標： 1 2 3 4 5 6 7 8 9 10
45 36 18 53 72 30 48 93 15 36
I J
（1） 36 36 18 53 72 30 48 93 15 45
（2） 36 36 18 45 72 30 48 93 15 53
（3） 36 36 18 15 72 30 48 93 45 53
（4） 36 36 18 15 45 30 48 93 72 53
（5） 36 36 18 15 30 45 48 93 72 53
