数组排序

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int amount = sc.nextInt();
        int[] nums = new int[amount];
        for (int i = 0; i < amount; i++) {
            int num = sc.nextInt();
            nums[i] = num;
        }
        int sort = sc.nextInt();
        quick(nums, sort);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }

    //选择排序
    public static void select(int[] nums, int sort) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return;
        }
        //0~n 0
        //1~n 1
        //i~-n i
        //n-1~n n-1
        for (int i = 0; i < nums.length; i++) {
            int tmp = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (sort == 0 && nums[j] < nums[tmp]) {
                    tmp = j;
                }
                if (sort == 1 && nums[j] > nums[tmp]) {
                    tmp = j;
                }
            }
            swap(nums, i, tmp);
        }
    }

    //冒泡排序
    public static void bubbo(int[] nums, int sort) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return;
        }
        // 0 n-1 n-1
        // 0 n-2 n-2
        // 0 end end
        // 0 0   0
        for (int end = nums.length - 1; end >= 0; end--) {
            //0 1 1
            //1 2 2
            //one second second
            //n-2 n-1 n-1
            for (int second = 1; second <= nums.length - 1; second++) {
                if (sort == 0 && nums[second] < nums[second - 1]) {
                    swap(nums, second, second - 1);
                }
                if (sort == 1 && nums[second] > nums[second - 1]) {
                    swap(nums, second, second - 1);
                }
            }
        }
    }

    //插入
    public static void insert(int[] nums, int sort) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            int tmp = i;
            while (tmp - 1 >= 0 && nums[tmp - 1] > nums[tmp] && sort == 0) {
                swap(nums, tmp, tmp - 1);
                tmp--;
            }
            while (tmp - 1 >= 0 && nums[tmp - 1] < nums[tmp] && sort == 1) {
                swap(nums, tmp, tmp - 1);
                tmp--;
            }
        }
    }

    //快排
    public static void quick(int[] nums, int sort) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return;
        }
        quickProcess1(nums, sort, 0, nums.length - 1);
    }

    public static void quickProcess1(int[] nums, int sort, int left, int right) {
        if (left >= right) {
            return;
        }

        int len = right - left + 1;
        int random = (int) (Math.random() * len + left);
        swap(nums, right, random);
        int[] mids = quickProcess2(nums, sort, left, right);
        quickProcess1(nums, sort, left, mids[0] - 1);
        quickProcess1(nums, sort, mids[1] + 1, right);
    }

    public static int[] quickProcess2(int[] nums, int sort, int left, int right) {
        int standard = nums[right];
        int p1 = left - 1;
        int p2 = right;
        int index = left;
        while (index < p2) {
            if (nums[index] < standard) {
                if (sort == 0) {
                    swap(nums, ++p1, index++);
                } else {
                    swap(nums, --p2, index);
                }
            } else if (nums[index] > standard) {
                if (sort == 0) {
                    swap(nums, --p2, index);
                } else {
                    swap(nums, ++p1, index++);
                }
            } else {
                index++;
            }
        }
        swap(nums, right, p2);
        return new int[]{p1 + 1, p2};
    }

    //归并
    public static void merge(int[] nums, int sort) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return;
        }
        mergeProcess1(nums, sort, 0, nums.length - 1);
    }

    public static void mergeProcess1(int[] nums, int sort, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1);
        mergeProcess1(nums, sort, left, mid);
        mergeProcess1(nums, sort, mid + 1, right);
        mergeProcess2(nums, sort, left, mid, right);
    }

    public static void mergeProcess2(int[] nums, int sort, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int index = 0;

        int p1 = left;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= right) {
            if (sort == 0) {
                if (nums[p2] < nums[p1]) {
                    tmp[index++] = nums[p2++];
                } else {
                    tmp[index++] = nums[p1++];
                }
            } else {
                if (nums[p2] > nums[p1]) {
                    tmp[index++] = nums[p2++];
                } else {
                    tmp[index++] = nums[p1++];
                }
            }
        }
        while (p1 <= mid) {
            tmp[index++] = nums[p1++];
        }
        while (p2 <= right) {
            tmp[index++] = nums[p2++];
        }

        for (int i = 0; i < tmp.length; i++) {
            nums[left + i] = tmp[i];
        }
    }

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