八大排序

快速排序

public static void main(String[] args) {
    int[] nums = {5, 7, 3, 1, 9, 6, 4, 2, 8};
    quick_sort(nums, 0, nums.length - 1);
    for (int i = 0; i < nums.length; i++) {
        System.out.print(nums[i] + " ");
    }
}

private static void quick_sort(int[] nums, int low, int high) {
    if (high <= low) {
        return;
    }
    int pivot = nums[high];
    int i = low;
    for (int j = low; j < high; j++) {
        if (nums[j] < pivot) {
            swap(nums, i, j);
            i ++;
        }
    }
    swap(nums, i, high);
    quick_sort(nums, low, i - 1);
    quick_sort(nums, i + 1, high);
}

public static void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

归并排序

public static void main(String[] args) {
        int[] nums = {5, 7, 3, 1, 9, 6, 4, 2, 8};
        int[] t = new int[nums.length];
        merge_sort(t, nums, 0, nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }

public static void merge_sort(int[] t, int[] nums, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = (left + right) / 2;
    merge_sort(t, nums, left, mid);
    merge_sort(t, nums, mid + 1, right);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right) {
        if (nums[i] <= nums[j]) {
            t[k ++] = nums[i ++];
        } else {
            t[k ++] = nums[j ++];
        }
    }
    while (i <= mid) {
        t[k ++] = nums[i ++];
    }
    while (j <= right) {
        t[k ++] = nums[j ++];
    }
    for (k = 0, i = left; i <= right;) {
        nums[i ++] = t[k ++];
    }
}

堆排序

建立大根堆，小根堆就改个小于号就行

public static void heapify(int[] nums, int cur) {
    int mx = cur, n = nums.length;
    int l = 2 * cur + 1;//当前节点的左儿子
    int r = 2 * cur + 2;
    if (l < n && nums[l] > nums[mx]) {//如果左儿子比当前节点大
        mx = l;//标记更大的
    }
    if (r < n && nums[r] > nums[mx]) {
        mx = r;
    }
    if (mx != cur) {//存在更大的
        swap(nums, cur, mx);
        heapify(nums, mx);//递归往下处理儿子节点
    }
}
public static void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}
public static void main(String[] args) {
    int[] nums = new int[]{5, 86, 12, 35, 53, 6, 10, 80, 99};
    for (int i = nums.length / 2 - 1; i >= 0; i--) {//从第一个非叶子节点开始比较，也就是35
        heapify(nums, i);
    }
    Arrays.stream(nums).forEach(System.out::println);
}

加上排序：每次把堆顶与数组最后一个元素交换，然后数组长度 - 1，对前面的继续建堆，再交换。。。

public class Solution {
    public static void main(String[] args) {
        int[] nums = {1, 2, 5, 9, 2, 3, 6, 8, 1};
        hsort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }

    private static void hsort(int[] nums, int len) {
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(nums, i, len);
        }
        for (int i = len - 1; i > 0; i--) { //迭代排序
            swap(nums, i, 0);  // 把堆顶元素(最大值)放到当前范围末尾
            heapify(nums, 0, i);  // 堆的有效范围减少1，继续维护堆结构
        }
    }
    private static void heapify(int[] nums, int cur, int len) {
        int left = cur * 2 + 1;
        int right = cur * 2 + 2;
        int largest = cur;
        if (left < len && nums[left] > nums[largest]) {
            largest = left;
        }
        if (right < len && nums[right] > nums[largest]) {
            largest = right;
        }
        if (largest != cur) {
            swap(nums, cur, largest);
            heapify(nums, largest, len);
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

public class Solution {
    public static void main(String[] args) {
        int[] nums = {1, 2, 5, 9, 2, 3, 6, 8, 1};
        hsort(nums, nums.length);
        System.out.println(Arrays.toString(nums));
    }

    private static void hsort(int[] nums, int len) {
        if (len < 1) {
            return;
        }
        for (int i = len / 2 - 1; i >= 0; i--) {
            heapify(nums, i, len);
        }
        swap(nums, len - 1, 0);  // 把堆顶元素(最大值)放到当前范围末尾
        hsort(nums, len - 1);//递归排序
    }
    private static void heapify(int[] nums, int cur, int len) {
        int left = cur * 2 + 1;
        int right = cur * 2 + 2;
        int largest = cur;
        if (left < len && nums[left] > nums[largest]) {
            largest = left;
        }
        if (right < len && nums[right] > nums[largest]) {
            largest = right;
        }
        if (largest != cur) {
            swap(nums, cur, largest);
            heapify(nums, largest, len);
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

}

计数排序

思想就是将输入的数据值转化为键存储在额外开辟的数组空间中，要求输入的数据必须是有确定范围的整数，可以用数组每个元素减去数组中元素的最小值作为在额外数组的index，额外数组的长度就是max - min + 1

滑动子数组的美丽值，这道题用到了计数排序+滑动窗口

冒泡排序

public static void bubbleSort(int[] nums) {
    for (int i = 0; i < nums.length - 1; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] < nums[j]) {
                swap(nums, i, j);
            }
        }
    }
}

选择排序

每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置

public static void chooseSort(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        int t = i;
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] < nums[t]) {
                t = j;
            }
        }
        swap(nums, i, t);
    }
}

插入排序

前面是已排序序列，把后面未排序的数字依次插入到已排序序列的对应位置

public static void insertSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
            swap(nums, j, j - 1);
        }
    }
}