選擇排序

思想

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個的新無序區。

排序實例


初始關鍵字 [49 38 65 97 76 13 27 49]
第一趟排序后 13 [38 65 97 76 49 27 49]
第二趟排序后 13 27 [65 97 76 49 38 49]
第三趟排序后 13 27 38 [97 76 49 65 49]
第四趟排序后 13 27 38 49 [76 97 65 49 ]
第五趟排序后 13 27 38 49 49 [97 65 76]
第六趟排序后 13 27 38 49 49 65 [97 76]
第七趟排序后 13 27 38 49 49 65 76 [97]
最后排序結果 13 27 38 49 49 65 76 97

Java實現代碼如下：

?

package selectsort;public class Sort {public static void main(String[] args){int[] a = {8,77,66,99,2,7,4,6,100,34};int[] b ; b = selectsort(a);for(int i = 0; i < b.length; i++){System.out.println(b[i]);}}public static int[] selectsort(int[] p){int temp = 0;int minindex = 0;int[] array = p.clone();for(int i = 0; i < array.length; i++){minindex = i;for(int j = i+1; j < array.length; j++){if(array[minindex] > array[j] )minindex = j;}temp = array[i];array[i] = array[minindex];array[minindex] = temp;}return array;} }

結果驗證正確。

?

冒泡法

原理

冒泡排序算法的運作如下：
比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
針對所有的元素重復以上的步驟，除了最后一個。
持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
算法分析


算法穩定性


冒泡排序就是把小的元素往前調或者把大的元素往后調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以，如果兩個元素相等，我想你是不會再無聊地把他們倆交換一下的；如果兩個相等的元素沒有相鄰，那么即使通過前面的兩兩交換把兩個相鄰起來，這時候也不會交換，所以相同元素的前后順序并沒有改變，所以冒泡排序是一種穩定排序算法。

Java實現代碼：

?

package bubblesort;public class Bubblesort {public static void main(String[] args){int[] a = {8,77,66,99,2,7,4,6,100,34};int[] b;b = bubble(a);for(int i =0; i <b.length; i++ ){System.out.println(b[i]);}}public static int[] bubble(int[] a){int[] array = a.clone();for(int i = 0; i < array.length - 1; i++){for(int j = 0; j < array.length - 1 - i; j++){if(array[j] > array[j+1])sway(array,j,j+1);}}return array;}public static void sway(int[] b, int m, int n){int temp = b[m];b[m] = b[n];b[n] = temp;}}

插入排序

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

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

Java示例代碼如下：

?

package insertsort;public class Insert {public static void main(String[] args){int[] a = {500,77,66,99,2,7,4,6,100,34};int[] b;b = insert(a);for(int i =0; i <b.length; i++ ){System.out.println(b[i]);}}public static int[] insert(int[] c){int[] array = c.clone();for(int i = 1; i < array.length; i++){if(array[i] < array[i - 1]){int temp = array[i];int j = i;while((j>0)&&(array[j - 1] > temp)){array[j] = array[j - 1];j--;}array[j] = temp; }}return array;} }

希爾排序

?

希爾排序通過將比較的全部元素分為幾個區域來提升插入排序的性能。這樣可以讓一個元素可以一次性地朝最終位置前進一大步。然后算法再取越來越小的步長進行排序，算法的最后一步就是普通的插入排序，但是到了這步，需排序的數據幾乎是已排好的了（此時插入排序較快）。
假設有一個很小的數據在一個已按升序排好序的數組的末端。如果用復雜度為O(n2)的排序（冒泡排序或插入排序），可能會進行n次的比較和交換才能將該數據移至正確位置。而希爾排序會用較大的步長移動數據，所以小數據只需進行少數比較和交換即可到正確位置。
一個更好理解的希爾排序實現：將數組列在一個表中并對列排序（用插入排序）。重復這過程，不過每次用更長的列來進行。最后整個表就只有一列了。將數組轉換至表是為了更好地理解這算法，算法本身僅僅對原數組進行排序（通過增加索引的步長，例如是用i += step_size而不是i++）。
例如，假設有這樣一組數[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ]，如果我們以步長為5開始進行排序，我們可以通過將這列表放在有5列的表中來更好地描述算法，這樣他們就應該看起來是這樣：
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我們對每列進行排序：
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
將上述四行數字，依序接在一起時我們得到：[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].這時10已經移至正確位置了，然后再以3為步長進行排序：
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后變為：
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步長進行排序（此時就是簡單的插入排序了）。

?

?

package shellsort;public class shellsort {public static void main(String[] args){int[] a = {500,77,66,99,2,7,4,6,100,34};int[] b;b = shell(a);for(int i =0; i <b.length; i++ ){System.out.println(b[i]);}}public static int[] shell(int[] a){int[] array = a.clone();int len = array.length;int i = 0;int j = 0;int k = -1;int temp = -1;int gap = len;do{gap = gap / 3 + 1; for(i=gap; i<len; i+=gap){k = i;temp = array[k];for(j=i-gap; (j>=0) && (array[j]>temp); j-=gap){array[j+gap] = array[j];k = j;}array[k] = temp;}}while( gap > 1 );return array;} }

快速排序

思想：從待排序記錄序列中選取一個記錄(通常選取第一個記錄)為樞軸其關鍵字設為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<x.key時，將r[j]移至控單元r[i],此時r[j]相當于控單元。
（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示例代碼如下： package quicksort;public class Quick {public static void main(String[] args){int[] a = {500,77,66,99,2,7,4,6,100,34,1000,888,777,666,555,333,222,111,87,45,69,12,45,};QuickSort(a,a.length);for(int i =0; i <a.length; i++ ){System.out.println(a[i]);}}public static void swap(int[] array, int i, int j){int temp = array[i];array[i] = array[j];array[j] = temp;}public static int partition(int[] array, int low, int high){int pv = array[low];while( low < high ){while( (low < high) && (array[high] >= pv) ){high--;}swap(array, low, high);while( (low < high) && (array[low] <= pv) ){low++;}swap(array, low, high);}return low;}public static void QSort(int[] array, int low, int high){if( low < high ){int pivot = partition(array, low, high);QSort(array, low, pivot-1);QSort(array, pivot+1, high);}}public static void QuickSort(int[] array, int len) // O(n*logn){QSort(array, 0, len-1);}}
歸并排序
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。值得注意的是歸并排序是一種穩定的排序方法。
將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
歸并操作
歸并操作(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示例代碼如下： package MergeSortClass;public class MergeSortClass {private int[] SortOut;public void printSortedOutput() {for (int i = 0; i < this.SortOut.length; i++) {System.out.print(this.SortOut[i] + " ");}}public static void main(String[] args) {int[] in = { 2, 5, 3, 8, 6, 7, 1, 4, 0, 9 };MergeSortClass msTest = new MergeSortClass(in);msTest.printSortedOutput();}public MergeSortClass(int[] in){this.SortOut=this.MergeSort(in);}private int[] MergeSort(int[] i_list){if (i_list.length == 1) {return i_list;} else {int[] listL = new int[i_list.length / 2];int[] listR = new int[i_list.length - i_list.length / 2];int Center = i_list.length / 2;for (int i = 0; i < Center; i++) {listL[i] = i_list[i];}for (int i = Center, j = 0; i < i_list.length; i++, j++) {listR[j] = i_list[i];}int[] SortedListL=MergeSort(listL);int[] SortedListR=MergeSort(listR);int[] o_list = MergeTwoList(SortedListL, SortedListR);return o_list;}}private int[] MergeTwoList(int[] listL, int[] listR) {int i = 0, j = 0;int[] o_list = new int[listL.length + listR.length];int foot = 0;while (i < listL.length && j < listR.length) {if (listL[i] <= listR[j]) {o_list[foot] = listL[i];i++;} else {o_list[foot] = listR[j];j++;}foot++;}if (i == listL.length) {while (j < listR.length) {o_list[foot++] = listR[j++];}} else { // j==listR.lengthwhile (i < listL.length) {o_list[foot++] = listL[i++];}}return o_list;} }

轉載于:https://www.cnblogs.com/riasky/p/3455594.html

總結

以上是生活随笔為你收集整理的几种经典的数据排序及其Java实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。