Java快速排序、歸并排序及基數排序怎么實現

本篇內容主要講解“Java快速排序、歸并排序及基數排序怎么實現”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java快速排序、歸并排序及基數排序怎么實現”吧!

一、快速排序

1、基本介紹

以上面的數組為例分析快速排序。

首先要傳入三個值，數組arr[ ] ，最左邊下標left ，最右邊下標 right。然后將根據左右的下標值計算出中間值mid。

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

左右兩邊分別單獨循環，左邊找到比mid大的數，右邊找到比mid小的數。

兩邊分別找到符合條件的數后，進行交換。

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

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

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

2、代碼實現

//參數傳入數組arr ， 最左邊的下標left，最右邊的下標 right
public static void quickSort(int[] arr , int left , int right){
        //分別用臨時變量代替
        int l = left;
        int r = right;
        //中間的下標
        int middle = arr[(left + right) / 2];
        //臨時變量，用于交換數據
        int temp = 0;
        //進行循環，只要右邊的下標 l 小于 左邊的下標 r 就進行循環
        while (l < r){
            //左邊l 到 中間middle 單獨循環，找到比middle大的值
            while (arr[l] < middle){
                l += 1;
            }
            //中間middle 到 右邊 r 單獨循環，找到比middle小的值
            while (arr[r] > middle){
                r -= 1;
            }
            //退出循環，表示找到，不過先判斷 l 是否大于等于 r 
            //滿足就可以退出循環，不需要執行下面的代碼了
            if(l >= r){
                break;
            }
            //找到的數據進行交換
            temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            //此時進行判斷，如果arr[l] 等于middle  則 r--
            if(arr[l] == middle){
                r -= 1;
            }
            //如果  arr[r] 等于middle 則 l++
            if(arr[r] == middle){
                l += 1;
            }
        }
        //退出循環，l 會等于 r，此時要將兩者移位，l進行加一，r進行減一
        if(l == r){
            l += 1;
            r -= 1;
        }
        //第一輪完成后進行遞歸
        //重復上面的方法，向左遞歸
        if(left < r){
            //r 繼續往前移的，所以左下標為left ，右下標為 r
            quickSort(arr, left , r);
        }
        //重復上面的操作，向右遞歸
        if(right > l){
            //l 繼續往后移的，所以左下標為 l ，右下標為 right
            quickSort(arr, l , right);
        }
    }

二、歸并排序

1、基本介紹

2、代碼實現

? 首先實現合并

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

? 分隔和合并進行遞歸

public static void mergerSort(int[] arr, int left,int right, int[] temp){
        //判斷
        if (left < right){
            //求出中間值
            int mid = (left + right) / 2;
            //調用自己，向左遞歸
            mergerSort(arr, left, mid , temp);
            //調用自己，向右遞歸
            mergerSort(arr , mid + 1, right, temp);
            //調用merger進行合并
            merger(arr, left , mid, right, temp);
        }
    }

三、基數排序

1、基本介紹

首先我們需要10個數組，分別對應10個桶，每個桶有對應的下標。

然后按每個數的個位數大小放入對應的桶中，放好后，按桶的順序依次取出。

第二次是看每個數的十位，不及十位的就當做0，依舊是依次放入對應的桶中，并按順序取出。

第三次是看每個數的百位，重復上面的操作，最后得到的就是有序的數組。

2、代碼實現

public static void cardinalitySort(int[] arr){
        //首先找到數組中最大數的位數
        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個桶，每個桶大小為數組大小
        int[][] bucket = new int[10][arr.length];
        //定義一個數組來表示每個桶存放的數據
        int[] bucketcount = new int[10];
        //n是用來進行位數處理的
        for(int i = 1, n = 1; i <= maxLength ; i++,n *= 10){
            for(int j = 0; j < arr.length ; j++){
                //對每位數進行位處理，并放入桶中
                int elentData = arr[j] / n % 10;
                /*    
                  放對應的桶中,
                  bucketcount[elentData]表示對應的桶的數據,
                  假如第一個數為579，要放入bucketcount[9]（第九個桶）的第一個位置，
                  默認初始化為0，所以第一個數放入的位置是bucketcount[9] = 0
                */
                bucket[elentData][bucketcount[elentData]] = arr[j];
                //第一個數放完后，這個桶中數據進行++，
                //下次再放入這個桶時，bucketcount[9] = 1
                bucketcount[elentData]++;
            }
            int index = 0;
            //遍歷每一個桶
            for(int k = 0; k < bucketcount.length; k++){
                //第一次默認為bucketcount[k] = 0
                //所以如果第一個數為零，就說明這個桶為空
                if(bucketcount[k] != 0){
                    //有數據，則桶bucketcount[k]就會有對應數據多少的大小，進行遍歷
                    for(int l = 0; l < bucketcount[k] ; l++){
                        //放入原來的數組
                        arr[index++] = bucket[k][l];
                    }
                }
                //桶中的數放回原數組放完后，進行置空
                bucketcount[k] = 0;
            }
        }
    }

到此，相信大家對“Java快速排序、歸并排序及基數排序怎么實現”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！