基于分治政策的排序算法：合并排序和快速排序

參考教材：算法設計與分析（第3版） 王曉東 編著 清華大學出版社

首先介紹什麼是分治法？

分治法的基本思想是将一個規模為n的問題分解成k個規模較小的子問題，這些子問題互相獨立且與原問題相同。遞歸地解決這些子問題，然後将各子問題的解合并得到原問題的解。

合并排序

合并排序算法是用分治政策實作對n個元素進行排序的算法。其基本思想是：将待排序元素分成大小大緻相同的2個子集合，分别對2個子集合進行排序，最終将排好序的子集合合并成為所要求的排好序的集合。

代碼：

public class MergeSort {
    /**
     * @param int[] 未排序數組
     * @return int[] 排完序數組
     */
    private int[] sort(int[] nums, int low, int high) {
        int mid = (low + high) / ;
        if (low < high) {
            // 左邊
            sort(nums, low, mid);
            // 右邊
            sort(nums, mid + , high);
            // 左右歸并
            merge(nums, low, mid, high);
        }
        return nums;
    }

    private void merge(int[] nums, int low, int mid, int high) {
        int[] temp = new int[high - low + ];
        int i = low;// 左指針
        int j = mid + ;// 右指針
        int k = ;
        // 把較小的數先移到新數組中
        while (i <= mid && j <= high) {
            if (nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        // 把左邊剩餘的數移入數組
        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        // 把右邊邊剩餘的數移入數組
        while (j <= high) {
            temp[k++] = nums[j++];
        }
        // 把新數組中的數覆寫nums數組
        for (int k2 = ; k2 < temp.length; k2++) {
            nums[k2 + low] = temp[k2];
        }
    }

    public int[] sortMerge(int[] array) {
        return sort(array, , array.length - );
    }

    public static void main(String[] args) {
        int[] a = { , , , , , , , , , , , , , , -, -, -, - };
        new MergeSort().sortMerge(a);
        for (int i : a) {
            System.out.print(i + " ");
        }
    }
}

           

測試資料運作結果：

快速排序

快速排序算法是基于分治政策的另一個排序算法。其基本思想是，對于輸入的子數組a[ p : r ]，按以下三個步驟進行排序。

1. 分解（divide）：以a[ p ]為基準元素将a[ p : r ]劃分成3段a[ p : q - 1 ]，a[ q ]和a[ q + 1 : r ]，使得a[ p : q - 1 ]中任何元素都小于等于a[ q ]，a[ q + 1 : r ]中任何元素都大于等于a[ q ]。下标q在劃分過程中确定。
2. 遞歸求解（conquer）：通過遞歸調用快速排序算法，分别對a[ p : q - 1 ]和a[ q + 1 : r ]進行排序。
3. 合并（merge）。

代碼：

public class QuickSort {
    /**
     * @param int[] 未排序數組
     * @return int[] 排完序數組
     */
    public int[] sortQuick(int[] array) {
        return quickSort(array, , array.length - );
    }

    private int[] quickSort(int[] arr, int low, int heigh) {
        if (low < heigh) {
            int division = partition2(arr, low, heigh);
            quickSort(arr, low, division - );// 對左半段排序
            quickSort(arr, division + , heigh);// 對右半段排序
        }
        return arr;
    }

    // 分水嶺,基位,左邊的都比這個位置小,右邊的都大
    private int partition(int[] arr, int low, int heigh) {
        int base = arr[low]; // 用子表的第一個記錄做樞軸(分水嶺)記錄
        while (low < heigh) { // 從表的兩端交替向中間掃描
            while (low < heigh && arr[heigh] >= base) {
                heigh--;
            }
            // base 指派給 目前 heigh 位,base 挪到(互換)到了這裡,heigh位右邊的都比base大
            swap(arr, heigh, low);
            while (low < heigh && arr[low] <= base) {
                low++;
            }
            // 遇到左邊比base值大的了,換位置
            swap(arr, heigh, low);
        }
        // now low = heigh;
        return low;
    }

    // 第二種partition，本質一樣，代碼略有不同
    private int partition2(int[] arr, int low, int heigh) {
        int i = low, j = heigh + ;
        int base = arr[low];
        // 将<base的元素交換到左邊區域
        // 将>base的元素交換到右邊區域
        while (true) {
            // 從左往右找，找到第一個比base大的，記錄位置i，即arr[i]>base
            while (arr[++i] < base && i < heigh)
                ;
            // 從右往左找，找到第一個比base小的，記錄位置j，即arr[j]<base
            while (arr[--j] > base)
                ;
            // 判斷是否有交換的必要
            if (i >= j)
                break;
            swap(arr, i, j);
        }
        // 将base放入正确位置，即arr[low]與arr[j]互換位置
        arr[low] = arr[j];
        arr[j] = base;
        // 現在j左邊的全部小于j右邊的，傳回下标j
        return j;
    }

    private void swap(int[] arr, int a, int b) {
        int temp;
        temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int[] a = { , , , , , , , , , , , , , , -, -, -, - };
        new QuickSort().sortQuick(a);
        for (int i : a) {
            System.out.print(i + " ");
        }
    }
}
           

我的收藏品：java常用的7大排序算法彙總