學步園

　　排序演算法很多地方都會用到，近期又重新看了一遍演算法，並自己簡單地實現了一遍，特此記錄下來，為以後複習留點材料。下面學步園小編來講解下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)（選擇排序只需要一個額外空間用於數組元素交換）。

　　實現代碼：

　　Java怎樣實現常用排序

　　 /** 　　*SelectionSorting 　　*/ 　　SELECTION(newSortable(){ 　　public>voidsort(T[]array,booleanascend){ 　　intlen=array.length; 　　for(inti=0;i

　　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怎樣實現常用排序」的內容，希望對大家有用。更多資訊請關注學步園。學步園，您學習IT技術的優質平台!