题解 | #排序#

package sort;

public class MySort {

public static void main(String[] args) {
    int[] arr = new int[]{10, 7, 2, 6, 3, 4, 5, 9, 8};

// arr = sortByBubbling(arr);
arr = sortArray(arr);
}

/**
 * 冒泡排序
 */
public static int[] sortByBubbling(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            int tmp;
            if (arr[j] > arr[j + 1]) {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
    return arr;
}

/**
 * 快速排序 start
 * https://www.bilibili.com/video/BV117411x72U?from=search&seid=9811547839771013274
 * https://leetcode-cn.com/problems/sort-an-array/solution/dong-hua-mo-ni-yi-ge-po-dui-pai-wo-gao-l-i6mt/
 */
public static int[] sortArray(int[] nums) {

    quickSort(nums, 0, nums.length - 1);
    return nums;

}

public static void quickSort(int[] nums, int low, int high) {

    if (low < high) {
        int index = partition(nums, low, high);
        quickSort(nums, low, index - 1);
        quickSort(nums, index + 1, high);
    }

}

public static int partition(int[] nums, int low, int high) {
    int pivot = nums[low];
    while (low < high) {
        //移动high指针
        while (low < high && nums[high] >= pivot) {
            high--;
        }
        //填坑
        if (low < high) {
            nums[low] = nums[high];
        }
        while (low < high && nums[low] <= pivot) {
            low++;
        }
        //填坑
        if (low < high) {
            nums[high] = nums[low];
        }
    }
    //基准数放到合适的位置
    nums[low] = pivot;
    return low;
}

// 快速排序 end

/**
 * 堆排序
 */
public static int[] heapSort(int[] arr) {

    return arr;
}


/**
 * 归并排序
 */
public static int[] mergeSort(int[] arr) {

    return arr;
}

}