Java如何實現常用排序

這篇文章將為大家詳細講解有關Java如何實現常用排序，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

　　1.選擇排序

　　選擇排序的基本思想是遍歷數組的過程中，以i代表當前需要排序的序號，則需要在剩余的[i…n-1]中找出其中的最小值，然后將找到的最小值與i指向的值進行交換。因為每一趟確定元素的過程中都會有一個選擇最大值的子流程，所以人們形象地稱之為選擇排序。

　　舉個實例來看看：

　　初始：[38,17,16,16,7,31,39,32,2,11] 　　i=0:[2,17,16,16,7,31,39,32,38,11](0th[38]<->8th[2]) 　　i=1:[2,7,16,16,17,31,39,32,38,11](1st[38]<->4th[17]) 　　i=2:[2,7,11,16,17,31,39,32,38,16](2nd[11]<->9th[16]) 　　i=3:[2,7,11,16,17,31,39,32,38,16](無需交換) 　　i=4:[2,7,11,16,16,31,39,32,38,17](4th[17]<->9th[16]) 　　i=5:[2,7,11,16,16,17,39,32,38,31](5th[31]<->9th[17]) 　　i=6:[2,7,11,16,16,17,31,32,38,39](6th[39]<->9th[31]) 　　i=7:[2,7,11,16,16,17,31,32,38,39](無需交換) 　　i=8:[2,7,11,16,16,17,31,32,38,39](無需交換) 　　i=9:[2,7,11,16,16,17,31,32,38,39](無需交換)

　　由例子可以看出，選擇排序隨著排序的進行（i逐漸增大），比較的次數會越來越少，但是不論數組初始是否有序，選擇排序都會從i至數組末尾進行一次選擇比較，所以給定長度的數組，選擇排序的比較次數是固定的：1+2+3+….+n=n*(n+1)/2，而交換的次數則跟初始數組的順序有關，如果初始數組順序為隨機，則在最壞情況下，數組元素將會交換n次，最好的情況下則可能0次（數組本身即為有序）。

　　由此可以推出，選擇排序的時間復雜度和空間復雜度分別為O(n2)和O(1)（選擇排序只需要一個額外空間用于數組元素交換）。

　　實現代碼：

　　/** 　　*SelectionSorting 　　*/ 　　SELECTION(newSortable(){ 　　public<TextendsComparable>voidsort(T[]array,booleanascend){ 　　intlen=array.length; 　　for(inti=0;i<len;i++){ 　　intselected=i; 　　for(intj=i+1;j<len;j++){ 　　intcompare=array[j].compareTo(array[selected]); 　　if(compare!=0&&compare<0==ascend){ 　　selected=j; 　　} 　　} 　　exchange(array,i,selected); 　　} 　　} 　　})

　　2.插入排序

　　插入排序的基本思想是在遍歷數組的過程中，假設在序號i之前的元素即[0..i-1]都已經排好序，本趟需要找到i對應的元素x的正確位置k，并且在尋找這個位置k的過程中逐個將比較過的元素往后移一位，為元素x“騰位置”，最后將k對應的元素值賦為x，插入排序也是根據排序的特性來命名的。

　　以下是一個實例，紅色標記的數字為插入的數字，被劃掉的數字是未參與此次排序的元素，紅色標記的數字與被劃掉數字之間的元素為逐個向后移動的元素，比如第二趟參與排序的元素為[11,31,12]，需要插入的元素為12，但是12當前并沒有處于正確的位置，于是我們需要依次與前面的元素31、11做比較，一邊比較一邊移動比較過的元素，直到找到第一個比12小的元素11時停止比較，此時31對應的索引1則是12需要插入的位置。

關于“Java如何實現常用排序”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。