選擇排序

思想

n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果：①初始狀態：無序區為R[1..n]，有序區為空。②第1趟排序在無序區R[1..n]中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R[1]交換，使R[1..1]和R[2..n]分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。……③第i趟排序

第i趟排序開始時，當前有序區和無序區分別為R[1..i-1]和R(i..n）。該趟排序從當前無序區中選出關鍵字最小的記錄R[k]，將它與無序區的第1個記錄R交換，使R[1..i]和R分別變為記錄個數增加1個的新有序區和記錄個數減少1個的新無序區。

排序實例初始關鍵字[4938659776132749]

第一趟排序后13[38659776492749]

第二趟排序后1327[659776493849]

第三趟排序后132738[9776496549]

第四趟排序后13273849[76976549]

第五趟排序后1327384949[976576]

第六趟排序后132738494965[9776]

第七趟排序后13273849496576[97]

最后排序結果1327384949657697

Java實現代碼如下：

結果驗證正確。

冒泡法

原理

冒泡排序算法的運作如下：比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。針對所有的元素重復以上的步驟，除了最后一個。持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。算法分析算法穩定性冒泡排序就是把小的元素往前調或者把大的元素往后調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩定排序算法。

Java實現代碼：

插入排序

插入排序（InsertionSort）的算法描述是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。

算法描述一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下：從第一個元素開始，該元素可以認為已經被排序取出下一個元素，在已經排序的元素序列中從后向前掃描如果該元素（已排序）大于新元素，將該元素移到下一位置重復步驟3，直到找到已排序的元素小于或者等于新元素的位置將新元素插入到該位置后重復步驟2~5如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一個變種，稱為二分查找排序。

Java示例代碼如下：

希爾排序

希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然后算法再取越來越小的步長進行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了（此時插入排序較快）。假設有一個很小的數據在一個已按升序排好序的數組的末端。如果用復雜度為O(n2)的排序（冒泡排序或插入排序），可能會進行n次的比較和交換才能將該數據移至正確位置。而希爾排序會用較大的步長移動數據，所以小數據只需進行少數比較和交換即可到正確位置。一個更好理解的希爾排序實現：將數組列在一個表中并對列排序（用插入排序）。重復這過程，不過每次用更長的列來進行。最后整個表就只有一列了。將數組轉換至表是為了更好地理解這算法，算法本身僅僅對原數組進行排序（通過增加索引的步長，例如是用i+=step_size而不是i++）。

例如，假設有這樣一組數[13149433822559946523452773253910]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，

這樣他們就應該看起來是這樣：

然后我們對每列進行排序：將上述四行數字，依序接在一起時我們得到：[10147325231327943339255994658245].這時10已經移至正確位置了，然后再以3為步長進行排序：排序之后變為：最后以1步長進行排序（此時就是簡單的插入排序了）。

在實際使用過程中，帶排序的數據肯定不是只有十個，但是上述的思想。其實排序只是插入排序的一種優化。

快速排序思想：從待排序記錄序列中選取一個記錄(通常選取第一個記錄)為樞軸其關鍵字設為k1，然后將其余關鍵字小于k1的記錄移到前面去，而將關鍵字大于k1的記錄移到后面，結果將待排序序列分成了兩個子表最后將關鍵字為k1的記錄查到其分界線的位置處.算法步驟：假設待劃分序列為r[left],r[left+1],.......r[right],具體實現上述劃分過程時，可以設兩個指針i和j，他們的初值分別為left,right.首先將基準記錄r[left]移至變量x中，是r[left]，即r[i]相當于空單元，然后反復進行如下兩個掃描過程，直到i和j相遇（1）j從右向左掃描，直到r[j].key（2）i從左向后掃描，直到r[i].key>x.key時，將r[i]移至空單元r[j],此時r[i]相當于空單元。當i和j相遇時，r[i](或r[j])相當與空單元，且r[i]左邊所有記錄的關鍵字均不大于基準記錄的關鍵字，而r[i]右邊所有記錄的關鍵字均不小于基準記錄的關鍵字，最后將基準記錄移至r[i]中，就完成了一次劃分過程。最后對子表進行遞歸調用排序函數進行排序。Java示例代碼如下：

歸并排序歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（DivideandConquer）的一個非常典型的應用。值得注意的是歸并排序是一種穩定的排序方法。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。歸并操作歸并操作(merge)，也叫歸并算法，指的是將兩個順序序列合并成一個順序序列的方法。如設有數列{6，202，100，301，38，8，1}初始狀態：6,202,100,301,38,8，1第一次歸并后：{6,202},{100,301},{8,38},{1}，比較次數：3；第二次歸并后：{6,100,202,301}，{1,8,38}，比較次數：4；第三次歸并后：{1,6,8,38,100,202,301},比較次數：4；總的比較次數為：3+4+4=11,；逆序數為14；算法描述歸并操作的工作原理如下：第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置重復步驟3直到某一指針超出序列尾將另一序列剩下的所有元素直接復制到合并序列尾Java示例代碼如下：