Java快速排序與歸并排序及基數(shù)排序圖解示例

第Java快速排序與歸并排序及基數(shù)排序圖解示例目錄一、快速排序1、基本介紹2、代碼實(shí)現(xiàn)二、歸并排序1、基本介紹2、代碼實(shí)現(xiàn)三、基數(shù)排序1、基本介紹2、代碼實(shí)現(xiàn)

一、快速排序

1、基本介紹

以上面的數(shù)組為例分析快速排序。

首先要傳入三個(gè)值，數(shù)組arr[]，最左邊下標(biāo)left，最右邊下標(biāo)right。然后將根據(jù)左右的下標(biāo)值計(jì)算出中間值mid。

我們要做的就是將左邊的值大于mid的放到右邊，將右邊小于mid的值放到左邊。

左右兩邊分別單獨(dú)循環(huán)，左邊找到比mid大的數(shù)，右邊找到比mid小的數(shù)。

兩邊分別找到符合條件的數(shù)后，進(jìn)行交換。

然后繼續(xù)比較并交換，此刻l和mid都指向3，r指向5。

這時(shí)需要進(jìn)行判斷，如果arr[l]等于mid則r--，如果arr[r]等于mid則l++。此時(shí)又進(jìn)行判斷arr[l]是否等于arr[r]，等于則退出。第一輪就結(jié)束了。

第一次完以后，我們使用遞歸，遞歸會重復(fù)上面的操作，從而完成排序。

2、代碼實(shí)現(xiàn)

//參數(shù)傳入數(shù)組arr，最左邊的下標(biāo)left，最右邊的下標(biāo)right

publicstaticvoidquickSort(int[]arr,intleft,intright){

//分別用臨時(shí)變量代替

intl=left;

intr=right;

//中間的下標(biāo)

intmiddle=arr[(left+right)/2];

//臨時(shí)變量，用于交換數(shù)據(jù)

inttemp=0;

//進(jìn)行循環(huán)，只要右邊的下標(biāo)l小于左邊的下標(biāo)r就進(jìn)行循環(huán)

while(lr){

//左邊l到中間middle單獨(dú)循環(huán)，找到比middle大的值

while(arr[l]middle){

l+=1;

//中間middle到右邊r單獨(dú)循環(huán)，找到比middle小的值

while(arr[r]middle){

r-=1;

//退出循環(huán)，表示找到，不過先判斷l(xiāng)是否大于等于r

//滿足就可以退出循環(huán)，不需要執(zhí)行下面的代碼了

if(l=r){

break;

//找到的數(shù)據(jù)進(jìn)行交換

temp=arr[l];

arr[l]=arr[r];

arr[r]=temp;

//此時(shí)進(jìn)行判斷，如果arr[l]等于middle則r--

if(arr[l]==middle){

r-=1;

//如果arr[r]等于middle則l++

if(arr[r]==middle){

l+=1;

//退出循環(huán)，l會等于r，此時(shí)要將兩者移位，l進(jìn)行加一，r進(jìn)行減一

if(l==r){

l+=1;

r-=1;

//第一輪完成后進(jìn)行遞歸

//重復(fù)上面的方法，向左遞歸

if(leftr){

//r繼續(xù)往前移的，所以左下標(biāo)為left，右下標(biāo)為r

quickSort(arr,left,r);

//重復(fù)上面的操作，向右遞歸

if(rightl){

//l繼續(xù)往后移的，所以左下標(biāo)為l，右下標(biāo)為right

quickSort(arr,l,right);

}

二、歸并排序

1、基本介紹

2、代碼實(shí)現(xiàn)

?首先實(shí)現(xiàn)合并

publicstaticvoidmerger(int[]arr,intleft,intmid,intright,int[]temp){

inti=left;

intj=mid+1;

intt=0;//數(shù)組temp的下標(biāo)

//將arr數(shù)組按順序放入temp數(shù)組

while(i=midj=right){

//從中間分隔開，左邊和右邊相互比較

//如果左邊更小，先放入temp數(shù)組，否則右邊先放入

if(arr[i]arr[j]){

temp[t]=arr[i];

i++;

t++;

}else{

temp[t]=arr[j];

j++;

t++;

//有可能有一邊還沒放完，于是繼續(xù)循環(huán)放放入

//左邊沒放完

while(i=mid){

temp[t]=arr[i];

t++;

i++;

//右邊沒放完

while(j=right){

temp[t]=arr[j];

j++;

t++;

//將temp中數(shù)據(jù)拷入到arr

t=0;

intleftind=left;

//第一次（leftind，right）是（0,1）（2,3）（4,5）（6,7）

//第二次（leftind，right）是（0,3）（4,7）

//第三次（leftind，right）是（0,7）

while(leftind=right){

arr[leftind]=temp[t];

t++;

leftind++;

}

?分隔和合并進(jìn)行遞歸

publicstaticvoidmergerSort(int[]arr,intleft,intright,int[]temp){

//判斷

if(leftright){

//求出中間值

intmid=(left+right)/2;

//調(diào)用自己，向左遞歸

mergerSort(arr,left,mid,temp);

//調(diào)用自己，向右遞歸

mergerSort(arr,mid+1,right,temp);

//調(diào)用merger進(jìn)行合并

merger(arr,left,mid,right,temp);

}

三、基數(shù)排序

1、基本介紹

首先我們需要10個(gè)數(shù)組，分別對應(yīng)10個(gè)桶，每個(gè)桶有對應(yīng)的下標(biāo)。

然后按每個(gè)數(shù)的個(gè)位數(shù)大小放入對應(yīng)的桶中，放好后，按桶的順序依次取出。

第二次是看每個(gè)數(shù)的十位，不及十位的就當(dāng)做0，依舊是依次放入對應(yīng)的桶中，并按順序取出。

第三次是看每個(gè)數(shù)的百位，重復(fù)上面的操作，最后得到的就是有序的數(shù)組。

2、代碼實(shí)現(xiàn)

publicstaticvoidcardinalitySort(int[]arr){

//首先找到數(shù)組中最大數(shù)的位數(shù)

intmax=arr[0];

for(inti=1;iarr.length-1;i++){

if(arr[i]max){

max=arr[i];

intmaxLength=(max+"").length();

//定義10個(gè)桶，每個(gè)桶大小為數(shù)組大小

int[][]bucket=newint[10][arr.length];

//定義一個(gè)數(shù)組來表示每個(gè)桶存放的數(shù)據(jù)

int[]bucketcount=newint[10];

//n是用來進(jìn)行位數(shù)處理的

for(inti=1,n=1;i=maxLength;i++,n*=10){

for(intj=0;jarr.length;j++){

//對每位數(shù)進(jìn)行位處理，并放入桶中

intelentData=arr[j]/n%10;

放對應(yīng)的桶中,

bucketcount[elentData]表示對應(yīng)的桶的數(shù)據(jù),

假如第一個(gè)數(shù)為579，要放入bucketcount[9]（第九個(gè)桶）的第一個(gè)位置，

默認(rèn)初始化為0，所以第一個(gè)數(shù)放入的位置是bucketcount[9]=0

bucket[elentData][bucketcount[elentData]]=arr[j];

//第一個(gè)數(shù)放完后，這個(gè)桶中數(shù)據(jù)進(jìn)行++，

//下次再放入這個(gè)桶時(shí)，bucketcount[9]=1

bucketcount[elentData]++;

intindex=0;

//遍歷每一個(gè)桶

for(intk=0;kbucketcount.length;k++){

//第一次默認(rèn)為bucketcount[k]=0

//所以如果第一個(gè)數(shù)為零，就說明這個(gè)桶為空

if(buc