image.png

归并排序

public static int[] mergeSort(int[] nums) {
    if (nums == null || nums.length < 2) {
        return nums;
    }

    int mid = nums.length / 2;
    int[] left = Arrays.copyOfRange(nums, 0, mid);
    int[] right = Arrays.copyOfRange(nums, mid, nums.length);
    return merge(mergeSort(left), mergeSort(right));
}

private static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    for (int index = 0, i = 0, j = 0; index < result.length; index++ ) {

        if (i >= left.length) {
            result[index] = right[j++];
        } else if (j >= right.length) {
            result[index] = left[i++];
        } else if (left[i] <= right[j]) {
            result[index] = left[i++];
        } else {
            result[index] = right[j++];
        }

    }
    return result;
}

快速排序

public static void quickSort(int[] nums) {
    if (nums == null || nums.length < 2) {
        return;
    }

    sort(nums, 0, nums.length - 1);

}

private static void sort(int[] nums, int left, int right) {
    if (left >= right) {
        return;
    }
    int base = nums[left];
    int L = left;
    int R = right;
    while (L < R) {
        while (nums[R] >= base && R > L) {
            R--;
        }
        while (nums[L] <= base && R > L) {
            L++;
        }
        if (L < R) {
            int temp = nums[L];
            nums[L] = nums[R];
            nums[R] = temp;
        }

    }
    nums[left] = nums[L];
    nums[L] = base;
    sort(nums, left, L - 1);
    sort(nums, L + 1, right);
}

堆排序

public static void heapSort(int[] nums) {
    if (nums == null || nums.length < 2) {
        return;
    }

    for (int i = nums.length / 2; i >= 0; i--) {
        adjustHeap(nums, i, nums.length);
    }

    for(int i = nums.length-1; i > 0; i--){
        int temp = nums[i];
        nums[i] = nums[0];
        nums[0] = temp;
        adjustHeap(nums,0, i);
    }

}

private static void adjustHeap(int[] nums, int parent, int length) {

    int temp = nums[parent];
    for (int i = parent * 2 + 1; i < length; i = 2 * i + 1) {

        if (i + 1 < length && nums[i + 1] > nums[i]) {
            i++;
        }

        if (nums[i] > temp) {
            nums[parent] = nums[i];
            parent = i;
        } else {
            break;
        }
    }
    nums[parent] = temp;
}