排序算法

排序算法

虽然实践中排序通常都会直接调用库方法，但是一些排序算法的思想还是要学习的，设计得很巧妙。

重点学习：快速排序、归并排序、堆排序。

约定

编写一个抽象排序类 Sort，其他所有排序算法类都继承此类，实现抽象方法 sort(T[] arr)。另外这个抽象类还包含了一些常用方法，例如 swap()、isSorted() 等，无需在继承类中重复编写。详见如下代码：

/**
 * 抽象排序类，所有具体排序类皆继承此类
 */
public abstract class Sort<T extends Comparable<T>> {
    /**
     * 排序方法，由具体排序类重写
     * 
     * @param arr 待排序数组
     */
    public abstract void sort(T[] arr);

    /**
     * 交换数组中的两个元素
     * 
     * @param arr 数组
     * @param i   第一个元素的下标
     * @param j   第二个元素的下标
     */
    protected void swap(T[] arr, int i, int j) {
        T temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 检查数组是否有序（从小到大）
     * 
     * @param arr 待检查数组
     * @return 数组已有序则返回 true；否则返回 false。
     */
    protected boolean isSorted(T[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i].compareTo(arr[i - 1]) < 0) {
                return false;
            }
        }
        return true;
    }
}

快速排序

参考：算法（第4版）

public class QuickSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(T[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int j = partition(arr, low, high);
        quickSort(arr, low, j - 1);
        quickSort(arr, j + 1, high);
    }

    private int partition(T[] arr, int low, int high) {
        // 选取第一个元素作为枢纽元
        T pivot = arr[low];
        int i = low, j = high + 1;
        while (true) {
            while (arr[++i].compareTo(pivot) < 0) {
                if (i == high) {
                    break;
                }
            }
            while (arr[--j].compareTo(pivot) > 0) {
                if (j == low) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
        }
        swap(arr, low, j);
        return j;
    }

    public static void main(String[] args) {
        QuickSort<Integer> quickSort = new QuickSort<>();
        Integer[] nums = { 49, 59, 88, 37, 98, 40, 20 };
        quickSort.sort(nums);
        System.out.println(Arrays.toString(nums));
    }
}

也可以把 partition 方法揉进去：

```





## 归并排序

写法一：参考：数据结构与算法分析：Java语言描述 - Mark Allen Weiss

```java
public class MergeSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] arr) {
        @SuppressWarnings("unchecked")
        T[] temp = (T[]) new Comparable[arr.length];
        mergeSort(arr, temp, 0, arr.length - 1);
    }

    /**
     * 归并排序
     * 
     * @param arr   待排序数组
     * @param temp  辅助数组
     * @param left  待排序区间左端点
     * @param right 待排序区间右端点（包含）
     */
    private void mergeSort(T[] arr, T[] temp, int left, int right) {
        // 递归出口：left >= right
        if (left < right) {
            int mid = left + (right - left) / 2;
            // 递归：对数组左半部分进行归并排序
            mergeSort(arr, temp, left, mid);
            // 递归：对数组右半部分进行归并排序
            mergeSort(arr, temp, mid + 1, right);
            // 合并两半有序数组
            merge(arr, temp, left, mid + 1, right);
        }
    }

    /**
     * 将分治的两半有序数组合并
     * 
     * @param arr      数组
     * @param temp     辅助数组
     * @param leftPos  左半部分起点索引
     * @param rightPos 右半部分起点索引
     * @param rightEnd 右半部分终点索引（包含）
     */
    private void merge(T[] arr, T[] temp, int leftPos, int rightPos, int rightEnd) {
        // 待合并区间内元素数量
        int size = rightEnd - leftPos + 1;
        // 左半部分终点索引
        int leftEnd = rightPos - 1;
        // 辅助数组索引
        int tempPos = leftPos;
        // 合并两半有序数组
        while (leftPos <= leftEnd && rightPos <= rightEnd) {
            // 注意这里 <=0 保证排序的稳定性，< 0 就不稳定了
            if (arr[leftPos].compareTo(arr[rightPos]) <= 0) {
                temp[tempPos++] = arr[leftPos++];
            } else {
                temp[tempPos++] = arr[rightPos++];
            }
        }
        while (leftPos <= leftEnd) {
            temp[tempPos++] = arr[leftPos++];
        }
        while (rightPos <= rightEnd) {
            temp[tempPos++] = arr[rightPos++];
        }
        // 将值赋回原数组
        for (int i = 0; i < size; i++, rightEnd--) {
            arr[rightEnd] = temp[rightEnd];
        }
    }

    public static void main(String[] args) {
        MergeSort<Integer> mergeSort = new MergeSort<Integer>();
        Integer[] nums = { 2, 3, 1, -5, 2, 3, 9 };
        System.out.println(mergeSort.isSorted(nums));
        mergeSort.sort(nums);
        System.out.println(mergeSort.isSorted(nums));
        System.out.println(Arrays.toString(nums));
    }
}

上面的写法看起有点冗长，可以把 merge 方法揉到 mergeSort 中，可读性可能要好很多。

写法二：

public void mergeSort(int[] nums, int left, int right, int[] temp) {
    if (left >= right) {
        return;
    }
    // 分治
    int mid = left + (right - left) / 2;
    mergeSort(nums, left, mid, temp);
    mergeSort(nums, mid + 1, right, temp);

    // 归并
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    while (j <= right) {
        temp[k++] = nums[j++];
    }

    // 复制回原数组
    for (int p = left; p <= right; p++) {
        nums[p] = temp[p];
    }
}

堆排序