排序算法匯總25592

《排序算法匯總25592》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、排序算法匯總importjava.util.Random;?/**?*排序測試類?*?*排序算法的分類如下：?*1.插入排序（直接插入排序、折半插入排序、希爾排序）；?*2.交換排序（冒泡泡排序、快速排序）；?*3.選擇排序（直接選擇排序、堆排序）；?*4.歸并排序；?*5.基數(shù)排序。?*?*關(guān)于排序方法的選擇：?*(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。?*　當(dāng)記錄規(guī)模較小時，直接插入排序較好；否則因為直接選擇移動的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序為宜。?*(2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人

2、、冒泡或隨機(jī)的快速排序為宜；?*(3)若n較大，則應(yīng)采用時間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。?*?*/publicclassSortTest{??????publicint[]createArray(){?????????????Randomrandom=newRandom();?????????????int[]array=newint[10];?????????????for(inti=0;i<10;i++){????????????????????array[i]=random.nextInt(100)

3、-random.nextInt(100);//生成兩個隨機(jī)數(shù)相減，保證生成的數(shù)中有負(fù)數(shù)?????????????}?????????????System.out.println("==========原始序列==========");?????????????printArray(array);?????????????returnarray;??????}??????publicvoidprintArray(int[]data){?????????????for(inti:data){????????????????????System

4、.out.print(i+"");?????????????}?????????????System.out.println();??????}??????privatevoidswap(int[]data,intx,inty){?????????????inttemp=data[x];?????????????data[x]=data[y];?????????????data[y]=temp;??????}???????/**???????*冒泡排序----交換排序的一種???????*方法：相鄰兩元素進(jìn)行比較，如有需要則進(jìn)行交換，每完

5、成一次循環(huán)就將最大元素排在最后（如從小到大排序），下一次循環(huán)是將其他的數(shù)進(jìn)行類似操作。???????*性能：比較次數(shù)O(n^2),n^2/2；交換次數(shù)O(n^2),n^2/4???????*???????*@paramdata要排序的數(shù)組???????*@paramsortType排序類型???????*@return???????*/??????publicvoidbubbleSort(int[]data,StringsortType){?????????????if(sortType.equals("asc")){//正排序，從小排到

6、大????????????????????//比較的輪數(shù)????????????????????for(inti=1;i

7、??????if(data[j]>data[j+1]){?????????????????????????????????????????//交換相鄰兩個數(shù)?????????????????????????????????????????swap(data,j,j+1);??????????????????????????????????}???????????????????????????}????????????????????}?????????????}elseif(sortType.equals("desc")){//倒排序，

8、從大排到小????????????????????//比較的輪數(shù)????????????????????for(inti=1;i