排序算法原理與實(shí)現(xiàn)(java)

《排序算法原理與實(shí)現(xiàn)(java)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、Java程序員必知的8大排序<合肥軟件培訓(xùn)>[來(lái)源：本站

2、日期：2012年12月24日

3、瀏覽173次]字體:[大中小]8種排序之間的關(guān)系:1，直接插入排序（1）基本思想：在要排序的一組數(shù)中，假設(shè)前面(n-1)[n>=2]個(gè)數(shù)已經(jīng)是排好順序的，現(xiàn)在要把第n個(gè)數(shù)插到前面的有序數(shù)中，使得這n個(gè)數(shù)也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。（2）實(shí)例（3）用java實(shí)現(xiàn)//從小到大1packagecom.njue;12publicclassinsertSort{3publicinsertSort(){4inta[]={49,38,65,97

4、,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};5inttemp=0;6for(inti=1;i=0&&temp

5、h;i++)15System.out.println(a[i]);16}17}2，希爾排序（最小增量排序）（1）基本思想：算法先將要排序的一組數(shù)按某個(gè)增量d（n/2,n為要排序數(shù)的個(gè)數(shù)）分成若干組，每組中記錄的下標(biāo)相差d.對(duì)每組中全部元素進(jìn)行直接插入排序，然后再用一個(gè)較小的增量（d/2）對(duì)它進(jìn)行分組，在每組中再進(jìn)行直接插入排序。當(dāng)增量減到1時(shí)，進(jìn)行直接插入排序后，排序完成。（2）實(shí)例：（3）用java實(shí)現(xiàn)18publicclassshellSort{19publicshellSort(){20inta[]={1,54,6,3,78,34

6、,12,45,56,100};1doubled1=a.length;2inttemp=0;3while(true){4d1=Math.ceil(d1/2);5intd=(int)d1;6for(intx=0;x=0&&temp

7、ngth;i++)20System.out.println(a[i]);21}22}3.簡(jiǎn)單選擇排序（1）基本思想：在要排序的一組數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個(gè)數(shù)和最后一個(gè)數(shù)比較為止。（2）實(shí)例：（3）用java實(shí)現(xiàn)23publicclassselectSort{24publicselectSort(){25inta[]={1,54,6,3,78,34,12,45};1intposition=0;2for(inti=0;i

8、4intj=i+1;5position=i;6inttemp=a[i];7for(;j

9、僅當(dāng)滿足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)時(shí)稱之為堆。在這里只討論滿足前者條件的堆。由堆的定義可以看出，堆頂元素（即第一個(gè)元素）必為最大項(xiàng)（大頂堆）。完全二叉樹(shù)可以很直觀地表示堆的結(jié)構(gòu)。堆頂為根，其它為左子樹(shù)、右子樹(shù)。初始時(shí)把要排序的數(shù)的序列看作是一棵順序存儲(chǔ)的二叉樹(shù)，調(diào)整它們的存儲(chǔ)序，使之成為一個(gè)堆，這時(shí)堆的根節(jié)點(diǎn)的數(shù)最大。然后將根節(jié)點(diǎn)與堆的最后一個(gè)節(jié)點(diǎn)交換。然后對(duì)前面(n-1)個(gè)數(shù)重新調(diào)整使之成為堆。依此類推，直到只有兩個(gè)節(jié)點(diǎn)的堆，并對(duì)它們作交換，最后得到有n個(gè)節(jié)

10、點(diǎn)的有序序列。從算法描述來(lái)看，堆排序需要兩個(gè)過(guò)程，一是建立堆，二是堆頂與堆的最后一個(gè)元素交換位置。所以堆排序有兩個(gè)函數(shù)組成。一是建堆的滲透函數(shù)，二是反復(fù)調(diào)用滲透函數(shù)實(shí)現(xiàn)排序的函數(shù)。（2）實(shí)例：初始序列：46