java實現(xiàn)的幾個常用排序算法詳細(xì)解讀

《java實現(xiàn)的幾個常用排序算法詳細(xì)解讀》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、Java實現(xiàn)的幾個常用排序算法詳細(xì)解讀排序算法很多地方都會用到，近期又重新看了一遍算法，并自己簡單地實現(xiàn)了一遍，特此記錄下來，為以后復(fù)習(xí)留點材料。廢話不多說，下面逐一看看經(jīng)典的排序算法：1.選擇排序選擇排序的基本思想是遍歷數(shù)組的過程中，以i代表當(dāng)前需要排序的序號，則需要在剩余的[i…n-1]中找出其中的最小值，然后將找到的最小值與i指向的值進(jìn)行交換。因為每一趟確定元素的過程中都會有一個選擇最大值的子流程，所以人們形象地稱之為選擇排序。舉個實例來看看：1.初始：[38,17,16,16,7,31,39,32,2,11]2.3.i=0:[2,17,1

2、6,16,7,31,39,32,38,11](0th[38]<->8th[2])4.5.i=1:[2,7,16,16,17,31,39,32,38,11](1st[38]<->4th[17])6.7.i=2:[2,7,11,16,17,31,39,32,38,16](2nd[11]<->9th[16])8.9.i=3:[2,7,11,16,17,31,39,32,38,16](無需交換)10.11.i=4:[2,7,11,16,16,31,39,32,38,17](4th[17]<->9th[16])12.13.i=5:[2,7,11,16,16

3、,17,39,32,38,31](5th[31]<->9th[17])14.15.i=6:[2,7,11,16,16,17,31,32,38,39](6th[39]<->9th[31])16.17.i=7:[2,7,11,16,16,17,31,32,38,39](無需交換)18.19.i=8:[2,7,11,16,16,17,31,32,38,39](無需交換)20.21.i=9:[2,7,11,16,16,17,31,32,38,39](無需交換)由例子可以看出，選擇排序隨著排序的進(jìn)行（i逐漸增大），比較的次數(shù)會越來越少，但是不論數(shù)組初始是否

4、有序，選擇排序都會從i至數(shù)組末尾進(jìn)行一次選擇比較，所以給定長度的數(shù)組，選擇排序的比較次數(shù)是固定的：1+2+3+….+n=n*(n+1)/2，而交換的次數(shù)則跟初始數(shù)組的順序有關(guān)，如果初始數(shù)組順序為隨機(jī)，則在最壞情況下，數(shù)組元素將會交換n次，最好的情況下則可能0次（數(shù)組本身即為有序）。由此可以推出，選擇排序的時間復(fù)雜度和空間復(fù)雜度分別為O(n2)和O(1)（選擇排序只需要一個額外空間用于數(shù)組元素交換）。實現(xiàn)代碼：1./**2.*SelectionSorting3.*/4.SELECTION(newSortable(){5.public

5、sComparable>voidsort(T[]array,booleanascend){6.intlen=array.length;7.for(inti=0;i

6、);17.}18.}19.})2.插入排序插入排序的基本思想是在遍歷數(shù)組的過程中，假設(shè)在序號i之前的元素即[0..i-1]都已經(jīng)排好序，本趟需要找到i對應(yīng)的元素x的正確位置k，并且在尋找這個位置k的過程中逐個將比較過的元素往后移一位，為元素x“騰位置”，最后將k對應(yīng)的元素值賦為x，插入排序也是根據(jù)排序的特性來命名的。以下是一個實例，紅色標(biāo)記的數(shù)字為插入的數(shù)字，被劃掉的數(shù)字是未參與此次排序的元素，紅色標(biāo)記的數(shù)字與被劃掉數(shù)字之間的元素為逐個向后移動的元素，比如第二趟參與排序的元素為[11,31,12]，需要插入的元素為12，但是12當(dāng)前并沒有處于正確

7、的位置，于是我們需要依次與前面的元素31、11做比較，一邊比較一邊移動比較過的元素，直到找到第一個比12小的元素11時停止比較，此時31對應(yīng)的索引1則是12需要插入的位置。1.初始：[11,31,12,5,34,30,26,38,36,18]2.3.第一趟：[11,31,12,5,34,30,26,38,36,18]（無移動的元素）4.5.第二趟：[11,12,31,5,34,30,26,38,36,18]（31向后移動）6.7.第三趟：[5,11,12,31,34,30,26,38,36,18]（11,12,31皆向后移動）8.9.第四趟：[5

8、,11,12,31,34,30,26,38,36,18]（無移動的元素）10.11.第五趟：[5,11,12,30,31,34,26,3