Java歸并排序和快速排序怎么實現

本篇內容介紹了“Java歸并排序和快速排序怎么實現”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

歸并排序

// 歸并排序
    public static void mergeSort (int[] arr) {
        // 建一個臨時數據來存放數據
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }
    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) { // 如果起始下標跟結束下標差值小于1，則不進行操作
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid, temp); // 分組，將左邊分為一組，遞歸調用進行排序
            mergeSort(arr, mid+1, right, temp); // 將右邊分為一組
            merge(arr, left, mid, right, temp); //將左右分組合并
        }
    }
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left; // 定義左指針
        int j = mid + 1; // 定義右指針
        int t = 0; // 給temp臨時數組用的指針
        while (i <= mid && j <= right) { // 設置左右指針的移動邊界
            if (arr[i] <= arr[j]) { // 此處是升序，故誰小誰先賦給臨時數組
                temp[t++] = arr[i++];
            } else {
                temp[t++] = arr[j++];
            }
        }
        while (i <= mid) { // 如果左邊有剩余，則放在temp中
            temp[t++] = arr[i++];
        }
        while (j <= right) { // 如果右邊有剩余，依次放入temp中
            temp[t++] = arr[j++];
        }
        t = 0;
        // 此時temp中已經是arr數組中下標從left到right之間排好序的數據了，因為temp每次都是從0開始賦值，所以需將排好序的數放回arr的對應位置
        while (left <= right) {
            // 將left到right之間排好序的數據放回arr中，此時left到right之間的數就是最終排好序的數
            arr[left++] = temp[t++];
        }
    }

快速排序

// 快速排序
    public static void quickSort (int[] arr, int left, int right) {
        // 先將異常情況處理掉
        if (arr == null || arr.length < 2) {
            return;
        }
        if (right <= left) {
            return;
        }
        if (right - left == 1 && arr[left] <= arr[right]) {
            return;
        }
        // 取第一個數為基準數(基數取哪個都行，此處是為了方便)
        int index = arr[left];
        int i = left + 1; // 左指針
        int j = right; // 右指針
        while (i < j && i < right && j > left) { // 設置指針的移動邊界
            while (arr[j] > index && j > left) {j--;} // 找到從右邊數第一個比index小的數
            while (arr[i] < index && i < right) {i++;} // 找到從左邊數第一個比index大的數
            if (i < j) { // 交換這兩個數  如果i == j，說明二者定位到了同一個位置，則不用交換；如果i > j，說明二者已經相遇然后背向而行了，也不交換
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 執行完上面循環后，arr已經是左邊比index小，右邊比index大的數組了，只是基準數仍在基準位置left處，需放到它應該在的位置
        if (j != left && arr[j] != arr[left]) {
            // j最后停留位置的數，肯定是一個小于等于index的值，所以如果不是同一個位置的話，直接將二者調換一下位置即可
            int temp = arr[j];
            arr[j] = arr[left];
            arr[left] = temp;
        }
        quickSort(arr, left, j-1); // 將基準數左邊排序
        quickSort(arr, j+1, right); // 將基準數右邊排序
    }

“Java歸并排序和快速排序怎么實現”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！