public class SortAlgorithm {
    public static void main(String[] args) {
        int[] nums = {6, 1, 4, 2, 3, 9, 5, 8, 7};
        // 冒泡排序
         bubbleSort(nums);
        // 直接插入排序
         insertSort(nums);
        // 直接選擇排序
         directSelection(nums);
        // 快速選擇排序
        int[] numbers = quickSort(nums, 0, nums.length -1);
        System.out.print("快速選擇排序: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    public static void bubbleSort (int[] nums) {
        int temp;
        for (int i= 0;i <= nums.length; i++) {
            for (int j=i; j< nums.length-1; j++) {
                if (nums[j+1] < nums[j]) {
                    temp = nums[j+1];
                    nums[j+1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        System.out.print("冒泡排序: ");
        for (int num : nums) {
            System.out.print(num + " ");
        }
        System.out.println();
    }
    public static void insertSort(int[] nums) {
        // 存放有序的數(shù)組
        int[] numbers = new int[nums.length];
        int index = 0;
        for(int i=0;i< nums.length;i++) {
            // 當(dāng)前待插入元素
            int current = nums[i];
            // 存放臨時變量
            int prefix = 0;
            int temp = 0;
            // 未找到插入點
            boolean suc = false;
            // 插入第一個元素
            if (i == 0) {
                numbers[index] = current;
            } else {
                for(int j = 0; j < numbers.length; j++) {
                    // 找到待插入的點
                    if (numbers[j] > current || suc) {
                        // 未找到插入點
                        if (!suc) {
                            index = j;
                            suc = true;
                            // 記錄下當(dāng)前節(jié)點
                            prefix = numbers[j];
                        } else {
                            temp = numbers[j];
                            // 將前一個節(jié)點的值賦值給當(dāng)前節(jié)點
                            numbers[j] = prefix;
                            prefix = temp;
                        }
                    }
                }
                // 若查找到插入節(jié)點
                if (suc) {
                    numbers[index] = current;
                } else {
                    numbers[i] = nums[i];
                }
            }
        }
        System.out.print("直接插入排序: ");
        for (int number : numbers) {
            System.out.print(number + " ");
        }
        System.out.println();
    }
    public static void directSelection(int[] nums) {
        int index = 0;
        for(int i=0; i < nums.length; i++) {
            // 默認不需要交換
            boolean exchange = false;
            int temp = nums[i];
            for(int j=i; j< nums.length; j++) {
                if (nums[j] < temp) {
                    // 尋找最小的值
                    temp = nums[j];
                    // 記錄最小值的下標(biāo)
                    index = j;
                    // 需要交換
                    exchange = true;
                }
            }
           // 需要交換，則進行交換
           if (exchange) {
               nums[index] = nums[i];
               // 將第i輪較小的值賦值給下標(biāo)為i的節(jié)點
               nums[i] = temp;
           }
        }
        System.out.print("直接選擇排序: ");
        for (int number : nums) {
            System.out.print(number + " ");
        }
        System.out.println();
    }
    public static int[] quickSort(int[] nums, int start, int end) {
        // 定義基準(zhǔn)
        int k = nums[start];
        // 左側(cè)定位到的下標(biāo)
        int left = start;
        // 右側(cè)定位到的下標(biāo)
        int right = end;
        // 存放臨時數(shù)據(jù)
        int temp;
        boolean compareLeft = false;
        while (left != right) {
            if (compareLeft) {
                if (nums[left] > k) {
                    temp = nums[right];
                    nums[right] = nums[left];
                    nums[left] = temp;
                    // 基準(zhǔn)被踢到左側(cè)，需要和左側(cè)數(shù)據(jù)比較
                    compareLeft = false;
                } else {
                    left ++;
                }
            } else {
                if (nums[right] < k) {
                    temp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = temp;
                    // 基準(zhǔn)被踢到右側(cè)，需要和左側(cè)數(shù)據(jù)比較
                    compareLeft = true;
                } else {
                    right --;
                }
            }
        }
        if (left -1 > start) {
            quickSort(nums, start, left -1);
        }
        if (right + 1 < end) {
            quickSort(nums, right+ 1, end);
        }
        return nums;
    }
}