欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間:2022年09月24日 14:33:26   作者:小黎的培培筆錄  
快速排序是基于二分的思想,對(duì)冒泡排序的一種改進(jìn)。主要思想是確立一個(gè)基數(shù),將小于基數(shù)的數(shù)放到基數(shù)左邊,大于基數(shù)的數(shù)字放到基數(shù)的右邊,然后在對(duì)這兩部分進(jìn)一步排序,從而實(shí)現(xiàn)對(duì)數(shù)組的排序

一、快速排序

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é)束了。

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

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

//參數(shù)傳入數(shù)組arr , 最左邊的下標(biāo)left,最右邊的下標(biāo) right
public static void quickSort(int[] arr , int left , int right){
        //分別用臨時(shí)變量代替
        int l = left;
        int r = right;
        //中間的下標(biāo)
        int middle = arr[(left + right) / 2];
        //臨時(shí)變量,用于交換數(shù)據(jù)
        int temp = 0;
        //進(jìn)行循環(huán),只要右邊的下標(biāo) l 小于 左邊的下標(biāo) r 就進(jìn)行循環(huán)
        while (l < r){
            //左邊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),表示找到,不過(guò)先判斷 l 是否大于等于 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 會(huì)等于 r,此時(shí)要將兩者移位,l進(jìn)行加一,r進(jìn)行減一
        if(l == r){
            l += 1;
            r -= 1;
        }
        //第一輪完成后進(jìn)行遞歸
        //重復(fù)上面的方法,向左遞歸
        if(left < r){
            //r 繼續(xù)往前移的,所以左下標(biāo)為left ,右下標(biāo)為 r
            quickSort(arr, left , r);
        }
        //重復(fù)上面的操作,向右遞歸
        if(right > l){
            //l 繼續(xù)往后移的,所以左下標(biāo)為 l ,右下標(biāo)為 right
            quickSort(arr, l , right);
        }
    }

二、歸并排序

1、基本介紹

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

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

public static void merger(int[] arr , int left ,int mid , int right , int[] temp){
        int i = left;
        int j = mid + 1;
        int t = 0;//數(shù)組temp的下標(biāo)
        //將arr數(shù)組按順序放入temp 數(shù)組
        while (i <= mid  && j <= right){
            //從中間分隔開(kāi),左邊和右邊相互比較
            //如果左邊更小,先放入temp數(shù)組,否則右邊先放入
            if(arr[i] < arr[j]){
                temp[t] = arr[i];
                i++;
                t++;
            }else {
                temp[t] = arr[j];
                j++;
                t++;
            }
        }
        //有可能有一邊還沒(méi)放完,于是繼續(xù)循環(huán)放放入
        //左邊沒(méi)放完
        while (i <= mid){
            temp[t] = arr[i];
            t++;
            i++;
        }
        //右邊沒(méi)放完
        while (j <= right){
            temp[t] = arr[j];
            j++;
            t++;
        }
        //將temp中數(shù)據(jù)拷入到arr
        t = 0;
        int leftind = 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)行遞歸

public static void mergerSort(int[] arr, int left,int right, int[] temp){
        //判斷
        if (left < right){
            //求出中間值
            int mid = (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ù)組,分別對(duì)應(yīng)10個(gè)桶,每個(gè)桶有對(duì)應(yīng)的下標(biāo)。

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

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

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

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

public static void cardinalitySort(int[] arr){
        //首先找到數(shù)組中最大數(shù)的位數(shù)
        int max = arr[0];
        for(int i = 1; i < arr.length - 1; i++ ){
            if(arr[i] > max){
                max = arr[i];
            }
        }
        int maxLength = (max + "").length();
        //定義10個(gè)桶,每個(gè)桶大小為數(shù)組大小
        int[][] bucket = new int[10][arr.length];
        //定義一個(gè)數(shù)組來(lái)表示每個(gè)桶存放的數(shù)據(jù)
        int[] bucketcount = new int[10];
        //n是用來(lái)進(jìn)行位數(shù)處理的
        for(int i = 1, n = 1; i <= maxLength ; i++,n *= 10){
            for(int j = 0; j < arr.length ; j++){
                //對(duì)每位數(shù)進(jìn)行位處理,并放入桶中
                int elentData = arr[j] / n % 10;
                /*    
                  放對(duì)應(yīng)的桶中,
                  bucketcount[elentData]表示對(duì)應(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]++;
            }
            int index = 0;
            //遍歷每一個(gè)桶
            for(int k = 0; k < bucketcount.length; k++){
                //第一次默認(rèn)為bucketcount[k] = 0
                //所以如果第一個(gè)數(shù)為零,就說(shuō)明這個(gè)桶為空
                if(bucketcount[k] != 0){
                    //有數(shù)據(jù),則桶bucketcount[k]就會(huì)有對(duì)應(yīng)數(shù)據(jù)多少的大小,進(jìn)行遍歷
                    for(int l = 0; l < bucketcount[k] ; l++){
                        //放入原來(lái)的數(shù)組
                        arr[index++] = bucket[k][l];
                    }
                }
                //桶中的數(shù)放回原數(shù)組放完后,進(jìn)行置空
                bucketcount[k] = 0;
            }
        }
    }

到此這篇關(guān)于Java快速排序與歸并排序及基數(shù)排序圖解示例的文章就介紹到這了,更多相關(guān)Java快速排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評(píng)論