排序的分類：

1.希爾排序

希爾排序是快速插入排序的改進(jìn)版，希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰被分成一組，算法便終止

基本思路：先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個(gè)組中。先在各組內(nèi)進(jìn)行直接插入排序；然后，取第二個(gè)增量d2<d1重復(fù)上述的分組和排序，直至所取的增量?=1(?<?…<d2<d1)，即所有記錄放在同一組中進(jìn)行直接插入排序?yàn)橹?#xff0c;一般是選取d1為數(shù)組的一半，d2為d1的一半以此類推..

具體代碼：

package Sort;public class Shell_sort {public static void main(String[] args) {// TODO Auto-generated method stubint[] a = {78,68,48,39,95,48,94,73};//希爾排序int d=a.length;while(d>1){d=d/2;for(int x=0;x<d;x++){//以d為公差分組，分成d個(gè)數(shù)組，每個(gè)數(shù)組為{a[i+d],a[i+2d],a[i+3d]....}for(int i=x+d;i<a.length;i=i+d){//按直接插入排序?qū)⑦@些數(shù)組排序（具體方法查看我的直接插入排序http://www.cnblogs.com/pipixiao/p/7674142.html）int temp=a[i];int j;for(j=i-d;j>=0&&a[j]>temp;j=j-d){a[j+d]=a[j];}a[j+d]=temp;}}}System.out.println("排序之后：");for(int i=0;i<a.length;i++){System.out.print(a[i]+" ");} } }

運(yùn)行結(jié)果：

?

2.堆排序

大根堆排序，小根堆排序。

大根堆排序：先構(gòu)建二叉樹（構(gòu)建的二叉樹必須滿足父節(jié)點(diǎn)必須大于其左右子節(jié)點(diǎn)，數(shù)組中第一個(gè)數(shù)字為a【0】其左右子節(jié)點(diǎn)的應(yīng)為a【1】，a【2】，以腳標(biāo)定義既是父節(jié)點(diǎn)為a【i】，其左右子節(jié)點(diǎn)分別為a【2i+1】，a【2i+2】），再將二叉樹中第一個(gè)數(shù)獲取放入另外一個(gè)空數(shù)組中，剩下的數(shù)重新形成一個(gè)新的數(shù)組，再重新建堆，重復(fù)上述步驟，直到原數(shù)組中數(shù)字被取完，得到的新數(shù)組，既是一個(gè)由大到小排序完成的數(shù)組

由此二叉樹可知2是5，6的父節(jié)點(diǎn)，將2，5，6三個(gè)位置的數(shù)比較大小，得到最大的數(shù)與2位置的交換，當(dāng)?shù)玫降臄?shù)就是2本身，不做交換，（1，3，4），（0，1，2）位置的數(shù)也應(yīng)該做同樣的步驟，這樣最終0位置獲得的數(shù)既是最大的數(shù)，然后將得到的數(shù)組中a【0】拿出，后面的數(shù)構(gòu)建新數(shù)組，重新再構(gòu)建樹。重復(fù)上述步驟

注意：這里可以看出構(gòu)建數(shù)循環(huán)的次數(shù)為3次即：for（int i=（a.lenght-1）/2-1，i>=0,i--);但是當(dāng)出現(xiàn)下面這種情況時(shí)很顯然這個(gè)條件不滿足，下面循環(huán)的次數(shù)為4次，我們可以不改變上述循環(huán)的原理上面加一點(diǎn)既：for（int i=（a.lenght-1）/2-1+（a.lenght-1）%2；i>=0;i--）其實(shí)對(duì)比不難看出當(dāng)數(shù)組的長度為偶數(shù)的時(shí)候，得到的二叉樹最后悔單出來一個(gè)位置，這里面比較的條件就會(huì)發(fā)生變化，而（a.lenght-1）%2可以得到長度為偶數(shù)則加一次循環(huán)，為奇數(shù)時(shí)不變。

構(gòu)建的數(shù)是這種情況的時(shí)候（3，7）位置的數(shù)比較的時(shí)候只有兩個(gè)數(shù)比較，所以這里出現(xiàn)了一個(gè)不同，就應(yīng)該加一個(gè)判斷條件（本次比較是否存在a【2i+2】這一項(xiàng)，如果不存在則比較的數(shù)只有a【i】與a【2i+1】）

具體代碼：

?

package Sort;import java.util.Arrays;public class HeapSort {public static void main(String[] args) {// TODO Auto-generated method stubint[] arr = {78,68,48,39,95,48,94,73};int[] a = new int[8];for(int i=0;i<a.length;i++){heap(arr);a[i]=arr[0];//將當(dāng)前數(shù)組第一個(gè)數(shù)獲取給數(shù)組aarr=Arrays.copyOfRange(arr,1,arr.length);//截取取arr數(shù)組的第一個(gè)數(shù)后面的所有數(shù)，重新給arr }for (int m = 0; m < a.length; m++) {//遍歷輸出數(shù)組a，數(shù)組a既是排序完成后的數(shù)組System.out.print(a[m]+" ");}}public static void heap(int[] arr){//創(chuàng)建堆int temp=0;for(int j=(arr.length-1)/2-1+(arr.length-1)%2;j>=0;j--){//獲取每次創(chuàng)建堆的循環(huán)條件if(2*j+2<=arr.length-1){//判斷當(dāng)前a[2*j+2]是否存在，存在則執(zhí)行a[j]、a[2*j+1]、a[2*j+2]比較，不存在則執(zhí)行a[j]、a[2*j+1]比較temp=arr[j]>arr[2*j+1]?(arr[j]>arr[2*j+2]?j:2*j+2):(arr[2*j+1]>arr[2*j+2]?2*j+1:2*j+2);//比較獲得最大數(shù)的腳標(biāo)}else{temp=arr[j]>arr[2*j+1]?j:2*j+1; }if(arr[j]==arr[temp]){//如果最大的數(shù)就是a[j]本身則退出進(jìn)行下一次比較continue;}else{//最大數(shù)不是a[j]則最大數(shù)與a[j]交換位置arr[j]=arr[j]^arr[temp];arr[temp]=arr[j]^arr[temp];arr[j]=arr[j]^arr[temp];}}}}

?運(yùn)行結(jié)果：

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/pipixiao/p/7687930.html

總結(jié)

以上是生活随笔為你收集整理的【知了堂学习笔记】java 编写几种常见排序算法3的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。