最近买了本算法书看，发现算法书上写的Java代码简洁又容易理解，属于比较好的那种，对于有些自己写不好的排序，可以拿出来背背。

归并排序

归并排序基于归并这个简单的操作，即将两个有序的数组归并成一个更大的有序数组。

public class mergeSortAlgorithms {

    private int[] copy;

    public void mergeSort(int[] nums, int lo, int hi) {
        if (lo >= hi) return;

        int mid = lo + ((hi - lo) >> 1);

        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);

        merge(nums, lo, mid, hi);

    }

    //原地归并的抽象方法
    private void merge(int[] nums, int lo, int mid, int hi) {
        //将nums[lo..mid] 和 nums[mid+1..hi]归并
        int i = lo, j = mid + 1;

        for (int k = lo; k <= hi; k++) {    //将原数组复制一份到copy[lo..hi]
            copy[k] = nums[k];
        }

        for (int k = lo; k <= hi; k++) {    //归并回到a[lo..hi]
            if (i > mid) nums[k] = copy[j++];

            else if (j > hi) nums[k] = copy[i++];

            else if (copy[j] < copy[i]) nums[k] = copy[j++];

            else nums[k] = copy[i++];

        }
    }
}

快速排序

快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个子数组都有序时整个数组也就自然有序了。在第一种情况下，递归调用发生在处理整个数组之前；第二种情况下，递归调用发生在处理整个数组之后。在归并排序中，一个数组被等分为两半；在快速排序中，切分的位置取决于数组的内容。

public void quickSort(int nums[], int lo, int hi) {
    if (lo >= hi) return;

    int pivot = partition(nums, lo, hi);  //pivot是切分位置，这本书给了两种思路，一是在partition中Random，二是在排序前shuffle数组

    quickSort(nums, lo, pivot - 1);   //将左半部分nums[lo..j+1]排序
    quickSort(nums, pivot + 1, hi);   //将右半部分nums[j+1..hi]排序

}

//快排的切分
private int partition(int[] nums, int lo, int hi) {
    //将数组切分为nums[lo..i-1],nums[i],nums[i+1..hi]
    int i = lo;
    int j = hi + 1;
    int v = nums[lo];
    //扫描左右，检查扫描是否结束并交换元素
    while (true) {
        while (nums[++i] >= v) if (i == hi) break;
        while (nums[--j] <= v) if (j == lo) break;
        if (i >= j) break;
        swap(nums, i, j);
    }
    swap(nums, lo, j);    //将v = nums[j]放入正确的位置
    return j;           //nums[lo..j-1] <= nums[j] <= nums[j+1..hi]达成
}

private void swap(int[] nums, int lo, int hi) {
    int tmp = nums[lo];
    nums[lo] = nums[hi];
    nums[hi] = tmp;
}

于2022.3.19更新以下这段

在我刷题的过程中，发现了一种更便于理解的partition()方法代码，思路是初始化两个指针，指针1初始化指向下标为-1的位置，指针2 初始化指向下标为0的位置，向右移动指针2，当指针2指向小于选中的数字时，指针1向右移动1位，并交换这两个位置的数字，执行这样的过程，直到指针2再也遇不到小于选中数字的情况，扫描完毕，此时指针1向右再移动一格，然后交换两个指针指向的数字。

private int partition(int[] nums, int lo, int hi) {
    int random = new Random().nextInt(hi - lo + 1) + lo;// +1 是因为Random()的nextInt()中生成值是介于0（含）和指定值（不包括），右边是不包括的
    swap(nums, random, hi);
    int small = lo - 1;
    for (int i = lo; i < hi; i++) {
        if (nums[i] < nums[hi]) {
            small++;
            swap(nums, i, small);
        }
    }
    small++;
    swap(nums, small, hi);
    return small;
}

private void swap(int[] nums, int index1, int index2) {
    if (nums[index1] != nums[index2]) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}

于2024.3.13更新了喽

public static void QuickSort(int[] array, int lowIndex, int highIndex) {
    if (lowIndex >= highIndex)
        return;

    int pivot = partition(array, lowIndex, highIndex);
    QuickSort(array, lowIndex, pivot - 1);
    QuickSort(array, pivot + 1, highIndex);
}

private static int partition(int[] array, int lowIndex, int highIndex) {
    int pivotIndex = new Random().nextInt(highIndex - lowIndex) + lowIndex;
    int pivot = array[pivotIndex];
    swap(array, highIndex, pivotIndex);
    int leftPointer = lowIndex;
    int rightPointer = highIndex - 1;
    while (leftPointer < rightPointer) {
        while (array[leftPointer] <= pivot && leftPointer < rightPointer) {
            leftPointer++;
        }
        while (array[rightPointer] >= pivot && leftPointer < rightPointer) {
            rightPointer--;
        }
        swap(array, leftPointer, rightPointer);
    }
    if (array[leftPointer] > array[highIndex]) {
        swap(array, leftPointer, highIndex);
    } else {
        leftPointer = highIndex;
    }

    return leftPointer;
}

private static void swap(int[] array, int index1, int index2) {
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;
}