常见排序算法Java版（待续）

冒泡排序O(n^2)

public class Main {
    public static void main(String[] args) {
        Random random = new Random();
        int[] nums = new int[]{random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100)};
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

选择排序O(n^2),

public class Main {

    static Random random = new Random();
    static int[] nums = new int[]{random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100)};


    public static void main(String[] args) {
        //选择排序：核心就是记录每一轮遍历的最小值的索引，进行交换
        for (int i = 0; i < nums.length; i++) {
            int idx = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[idx]) {
                    idx = j;
                }
            }
            swap(nums, i, idx);
        }
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

插入排序O(n^2)

   public class Main {

    static Random random = new Random();
    static int[] nums = new int[]{random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100)};


    public static void main(String[] args) {
        for (int i = 0; i < nums.length; i++) {
            int idx = i;
            for (int j = i - 1; j >= 0; j--) {
                if (nums[j] > nums[i]) {
                    nums[idx] = nums[j];
                    idx = j;
                } else {
                    break;
                }
            }
            nums[idx] = nums[i];
        }
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

快速排序O(nlogn)

	public class Main {

    static Random random = new Random();
    static int[] nums = new int[]{random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100), random.nextInt(100)};


    public static void main(String[] args) {
        quickSort(nums, 0, nums.length - 1);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    public static void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        //选择一个元素做基准值
        int base = nums[left];
        int i = left;
        int j = right;
        while (i < j) {
            //注意while的顺序不能颠倒，要确保找到比基准值小的数
            while (i < j && nums[j] >= base) {
                j--;
            }
            while (i < j && nums[i] <= base) {
                i++;
            }
            swap(nums, i, j);
        }
        swap(nums, left, i);
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42