相关排序算法（冒泡，选择，插入，归并，快速，堆）

public class AllSort {
    // 冒泡排序，n-1趟，每次确定最大的
    public static void bubbleSort(int[] nums) {
        int n = nums.length;
        for (int i = n - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) swap(nums, j, j + 1);
            }
        }
    }

    // 选择排序，每次选择最小的进行交换
    public static void selectionSort(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n - 1; i++) {
            // 找到每个位置上最小的元素
            int minIndex = i;
            for (int j = i + 1; j <= n - 1; j++) {
                if (nums[j] < nums[minIndex]) minIndex = j;
            }
            swap(nums, minIndex, i);
        }
    }

    // 插入排序
    public static void insertionSort(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            for (int j = i; j > 0; j--) {
                if (nums[j] < nums[j - 1]) {
                    swap(nums, j, j - 1);
                }
            }
        }
    }

    // 归并排序，分而治之
    public static void mergeSort(int[] nums, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);
        merge(nums, lo, hi);
    }

    public static void merge(int[] nums, int lo, int hi) {
        int[] tmpArrr = new int[hi - lo + 1];
        int mid = lo + (hi - lo) / 2;
        int left = lo, right = mid + 1;
        int index = 0;
        while (left <= mid && right <= hi) {
            tmpArrr[index++] = nums[left] < nums[right] ? nums[left++] : nums[right++];
        }
        while (left <= mid) {
            tmpArrr[index++] = nums[left++];
        }
        while (right <= hi) {
            tmpArrr[index++] = nums[right++];
        }
        for (int i = 0; i < tmpArrr.length; i++) {
            nums[lo + i] = tmpArrr[i];
        }
    }

    // 快速排序，注意符号
    public static void quickSort(int[] nums, int lo, int hi) {
        if (lo >= hi) return;
        int pivot = partition(nums, lo, hi);
        quickSort(nums, lo, pivot - 1);
        quickSort(nums, pivot + 1, hi);
    }

    public static int partition(int[] nums, int lo, int hi) {
        swap(nums, lo, (int) (lo + Math.random() * (hi - lo + 1)));
        int pivot = nums[lo];
        // 注意符号
        while (lo < hi) {
            while (lo < hi && pivot <= nums[hi]) hi--;
            nums[lo] = nums[hi];
            while (lo < hi && nums[lo] <= pivot) lo++;
            nums[hi] = nums[lo];
        }
        nums[lo] = pivot;
        return lo;
    }

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

    // 堆排序，因为这里索引值是从0开始的，所以父节点的索引值为(index - 1) / 2，左孩子和右孩子的索引值分别为2 * index + 1, 2 * index + 2
    public static void heapSort(int[] arr) {
        int size = arr.length;
        for (int i = 0; i < size; i++) {
            // 构造大根堆
            heapInsert(arr, i);
        }
        // 将最大的元素放到最后，即最大的元素位置已经确定下来
        swap(arr, 0, --size);
        // 对剩下的n-1个元素进行调整
        while (size > 0) {
            heapify(arr, 0, size);
            swap(arr, 0, --size);
        }
    }

    // 上滤
    public static void heapInsert(int[] arr, int index) {
        // 如果到了0位置，那么自然也不满足循环的条件，因此会跳出循环
        while (arr[index] > arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    // 下滤， 0-size-1的位置形成堆，由于index的值发生改变需要下滤，即size用于表示标识是否越界
    public static void heapify(int[] arr, int index, int size) {
        int left = 2 * index + 1;
        while (left < size) {
            // 取出左右孩子中大的那个下标
            int largest = left + 1 < size && arr[left + 1] > arr[left]
                    ? left + 1
                    : left;
            if (arr[index] > arr[largest]) break;
            swap(arr, index, largest);
            index = largest;
            left = index * 2 + 1;
        }
    }

    public static void main(String[] args) {
        int[] nums ={9, 65, 2, 7, 55, 6, 1};
        quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}