排序算法

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) {
        // 存放有序的数组
        int[] numbers = new int[nums.length];

        int index = 0;

        for(int i=0;i< nums.length;i++) {
            // 当前待插入元素
            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;
                            // 记录下当前节点
                            prefix = numbers[j];
                        } else {
                            temp = numbers[j];
                            // 将前一个节点的值赋值给当前节点
                            numbers[j] = prefix;
                            prefix = temp;
                        }
                    }
                }

                // 若查找到插入节点
                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];
                    // 记录最小值的下标
                    index = j;
                    // 需要交换
                    exchange = true;
                }
            }

           // 需要交换，则进行交换
           if (exchange) {
               nums[index] = nums[i];
               // 将第i轮较小的值赋值给下标为i的节点
               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) {

        // 定义基准
        int k = nums[start];
        // 左侧定位到的下标
        int left = start;
        // 右侧定位到的下标
        int right = end;
        // 存放临时数据
        int temp;

        boolean compareLeft = false;

        while (left != right) {
            if (compareLeft) {

                if (nums[left] > k) {
                    temp = nums[right];
                    nums[right] = nums[left];
                    nums[left] = temp;

                    // 基准被踢到左侧，需要和左侧数据比较
                    compareLeft = false;
                } else {
                    left ++;
                }

            } else {
                if (nums[right] < k) {
                    temp = nums[left];
                    nums[left] = nums[right];
                    nums[right] = temp;

                    // 基准被踢到右侧，需要和左侧数据比较
                    compareLeft = true;
                } else {
                    right --;
                }
            }
        }

        if (left -1 > start) {
            quickSort(nums, start, left -1);
        }

        if (right + 1 < end) {
            quickSort(nums, right+ 1, end);
        }

        return nums;
    }
}