java的常見排序方法

第頁(yè)共頁(yè)java的常見排序方法java的常見排序方法復(fù)制代碼代碼如下:package.test;importjava.util.Random;/***排序測(cè)試類**排序算法的分類如下：1.插入排序〔直接插入排序、折半插入排序、希爾排序〕；2.交換排序〔冒泡泡排序、快速排序〕；*3.選擇排序〔直接選擇排序、堆排序〕；4.歸并排序；5.基數(shù)排序。**關(guān)于排序方法的選擇：(1)假設(shè)n較小(如n≤50)，可采用直接插入或直接選擇排序。*當(dāng)記錄規(guī)模較小時(shí)，直接插入排序較好；否那么因?yàn)橹苯舆x擇挪動(dòng)的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序?yàn)橐恕?(2)假設(shè)文件初始狀態(tài)根本有序(指正序)，那么應(yīng)選用直接插人、冒泡或隨機(jī)的快速排序?yàn)橐耍?(3)假設(shè)n較大，那么應(yīng)采用時(shí)間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。**/publicclassSort{/***初始化測(cè)試數(shù)組的方法**@return一個(gè)初始化好的數(shù)組*/publicint[]createArray{Randomrandom=newRandom;int[]array=newint[10];for(inti=0;i<10;i++){array[i]=random.nextInt(100)-random.nextInt(100);//生成兩個(gè)隨機(jī)數(shù)相減，保證生成的數(shù)中有負(fù)數(shù)}System.out.println(“==========原始序列==========”);printArray(array);returnarray;}/***打印數(shù)組中的元素到控制臺(tái)**@paramsource*/publicvoidprintArray(int[]data){for(inti:data){System.out.print(i+“”);}System.out.println;}/***交換數(shù)組中指定的兩元素的位置**@paramdata*@paramx*@paramy*/privatevoidswap(int[]data,intx,inty){inttemp=data[x];data[x]=data[y];data[y]=temp;}/***冒泡排序交換排序的一種*方法：相鄰兩元素進(jìn)展比擬，如有需要那么進(jìn)展交換，每完成一次循環(huán)就將最大元素排在最后〔如從小到大排序〕，下一次循環(huán)是將其他的數(shù)進(jìn)展類似操作。*性能：比擬次數(shù)O(n2),n2/2；交換次數(shù)O(n2),n2/4**@paramdata*要排序的數(shù)組*@paramsortType*排序類型*@return*/publicvoidbubbleSort(int[]data,StringsortType){if(sortType.equals(“asc”)){//正排序，從小排到大//比擬的輪數(shù)for(inti=1;i<data.length;i++){//將相鄰兩個(gè)數(shù)進(jìn)展比擬，較大的'數(shù)往后冒泡for(intj=0;j<data.length-i;j++){if(data[j]》data[j+1]){//交換相鄰兩個(gè)數(shù)swap(data,j,j+1);}}}}elseif(sortType.equals(“desc”)){//倒排序，從大排到小//比擬的輪數(shù)for(inti=1;i<data.length;i++){//將相鄰兩個(gè)數(shù)進(jìn)展比擬，較大的數(shù)往后冒泡for(intj=0;j<data.length-i;j++){if(data[j]<data[j+1]){//交換相鄰兩個(gè)數(shù)swap(data,j,j+1);}}}}else{System.out.println(“您輸入的排序類型錯(cuò)誤！”);}printArray(data);//輸出冒泡排序后的數(shù)組值}/***直接選擇排序法選擇排序的一種*方法：每一趟從待排序的數(shù)據(jù)元素中選出最小〔或最大〕的一個(gè)元素，順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。*性能：比擬次數(shù)O(n2),n2/2*交換次數(shù)O(n),n*交換次數(shù)比冒泡排序少多了，由于交換所需CPU時(shí)間比比擬所需的CUP時(shí)間多，所以選擇排序比冒泡排序快。*但是N比擬大時(shí)，比擬所需的CPU時(shí)間占主要地位，所以這時(shí)的性能和冒泡排序差不太多，但毫無疑問肯定要快些。**@paramdata*要排序的數(shù)組*@paramsortType*排序類型*@return**/publicvoidselectSort(int[]data,StringsortType){if(sortType.equals(“asc”)){//正排序，從小排到大intindex;for(inti=1;i<data.length;i++){index=0;for(intj=1;j<=data.length-i;j++){if(data[j]》data[index]){index=j;}}//交換在位置data.length-i和index(最大值)兩個(gè)數(shù)swap(data,data.length-i,index);}}elseif(sortType.equals(“desc”)){//倒排序，從大排到小intindex;for(inti=1;i<data.length;i++){index=0;for(intj=1;j<=data.length-i;j++){if(data[j]<data[index]){index=j;}}//交換在位置data.length-i和index(最大值)兩個(gè)數(shù)swap(data,data.length-i,index);}}else{System.out.println(“您輸入的排序類型錯(cuò)誤！”);}printArray(data);//輸出直接選擇排序后的數(shù)組值}/****插入排序**方法：將一個(gè)記錄插入到已排好序的有序表〔有可能是空表〕中,從而得到一個(gè)新的記錄數(shù)增1的有序表。*性能：比擬次數(shù)O(n2),n2/4*復(fù)制次數(shù)O(n),n2/4*比擬次數(shù)是前兩者的一般，而復(fù)制所需的CPU時(shí)間較交換少，所以性能上比冒泡排序進(jìn)步一倍多，而比選擇排序也要快。**@paramdata*要排序的數(shù)組*@paramsortType*排序類型*/publicvoidSort(int[]data,StringsortType){if(sortType.equals(“asc”)){//正排序，從小排到大//比擬的輪數(shù)for(inti=1;i<data.length;i++){//保證前i+1個(gè)數(shù)排好序for(intj=0;j<i;j++){if(data[j]》data[i]){//交換在位置j和i兩個(gè)數(shù)swap(data,i,j);}}}}elseif(sortType.equals(“desc”)){//倒排序，從大排到小//比擬的輪數(shù)for(inti=1;i<data.length;i++){//保證前i+1個(gè)數(shù)排好序for(intj=0;j<i;j++){if(data[j]<data[i]){//交換在位置j和i兩個(gè)數(shù)swap(data,i,j);}}}}else{System.out.println(“您輸入的排序類型錯(cuò)誤！”);}printArray(data);//輸出插入排序后的數(shù)組值}/****反轉(zhuǎn)數(shù)組的方法**@paramdata*數(shù)組*/publicvoidreverse(int[]data){intlength=data.length;inttemp=0;//臨時(shí)變量for(inti=0;i<length/2;i++){temp=data[i];data[i]=data[length-1-i];data[length-1-i]=temp;}printArray(data);//輸出到轉(zhuǎn)后數(shù)組的值}/****快速排序**快速排序使用分治法〔Divideandconquer〕策略來把一個(gè)序列〔list〕分為兩個(gè)子序列〔sub-lists〕。**步驟為：*1.從數(shù)列中挑出一個(gè)元素，稱為“基準(zhǔn)”〔pivot〕，*2.重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面〔一樣的數(shù)可以到任一邊〕。在這個(gè)分割之后，該基準(zhǔn)是它的最后位置。這個(gè)稱為分割〔partition〕操作。*3.遞歸地〔recursive〕把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。**遞回的最底部情形，是數(shù)列的大小是零或一，也就是永遠(yuǎn)都已經(jīng)被排序好了。雖然一直遞回下去，但是這個(gè)算法總會(huì)完畢，因?yàn)樵诿看蔚牡瞚teration〕中，它至少會(huì)把一個(gè)元素?cái)[到它最后的位置去。**@paramdata*待排序的數(shù)組*@paramlow*@paramhigh*@seeSortTest#qsort(int[],int,int)*@seeSortTest#qsort_desc(int[],int,int)**/publicvoidquickSort(int[]data,StringsortType){if(sortType.equals(“asc”)){//正排序，從小排到大qsort_data,0,data.length-1);}elseif(sortType.equals(“desc”)){//倒排序，從大排到小qsort_desc(data,0,data.length-1);}else{System.out.println(“您輸入的排序類型錯(cuò)誤！”);}}/****快速排序的詳細(xì)實(shí)現(xiàn)，排正序**@paramdata*@paramlow*@paramhigh*/privatevoidqsort_intdata[],intlow,inthigh){inti,j,x;if(low<high){//這個(gè)條件用來完畢遞歸i=low;j=high;x=data[i];while(i<j){while(i<j--data[j]》x){j--;//從右向左找第一個(gè)小于x的數(shù)}if(i<j){data[i]=data[j];i++;}while(i<j--data[i]<x){i++;//從左向右找第一個(gè)大于x的數(shù)}if(i<j){data[j]=data[i];j--;}}data[i]=x;qsort_data,low,i-1);qsort_data,i+1,high);}}/****快速排序的詳細(xì)實(shí)現(xiàn)，排倒序**@paramdata*@paramlow*@paramhigh**/privatevoidqsort_desc(intdata[],intlow,inthigh){inti,j,x;if(low<high){//這個(gè)條件用來完畢遞歸i=low;j=high;x=data[i];while(i<j){while(i<j--data[j]<x){j--;//從右向左找第一個(gè)小于x的數(shù)}if(i<j){data[i]=data[j];i++;}while(i<j--data[i]》x){i++;//從左向右找第一個(gè)大于x的數(shù)}if(i<j){data[j]=data[i];j--;}}data[i]=x;qsort_desc(data,low,i-1);qsort_desc(data,i+1,high);}}/****二分查找特定整數(shù)在整型數(shù)組中的位置(遞歸)**查找線性表必須是有序列表**@paramdataset*@paramdata*@parambeginIndex*@returnindex**////2，但是效率會(huì)高些return-1;if(data<dataset[midIndex]){returnbinarySearch(dataset,data,beginIndex,midIndex-1);}elseif(data》dataset[midIndex]){}else{returnmidIndex;}}/****二分查找特定整數(shù)在整型數(shù)組中的位置(非遞歸)**查找線性表必須是有序列表**@paramdataset*@paramdata*@returnindex**/publicintbinarySearch(int[]dataset,intdata){intbeginIndex=0;intmidIndex=-1;return-1;//(beginIndex+if(data<dataset[midIndex]){}elseif(data》dataset[midIndex]){beginIndex=midIndex+1;}else{returnmidIndex;}}return-1;}publicstaticvoidmain(String[]args){SortsortTest=newSort;int[]array=sortTest.createArray;System.out.println(“==========冒泡排序后(正序)==========”);sortTest.bubbleSort(array,“asc”);System.out.println(“==========冒泡排序后(倒序)==========”);sortTest.bubbleSort(array,“desc”);array=sortTest.createArray;System.out.println(“==========倒轉(zhuǎn)數(shù)組后==========”);sortTest.reverse(array);array=sortTest.createArray;System.out.println(“==========選擇排序后(正