十大排序：快速排序

​
​

活动地址：CSDN21天学习挑战赛

package tenSort;

/*
 * 快速排序
 * 思路：选择中轴元素，比它小的放左，比它大的放右（代码过程很像 小丑在扔三个小球）
 * 特点：时间：O(nlogn)、空间：O(logn)、非稳定
 * 适用：广泛（最快）
 */
public class Quick {
    private static void sort(int[] nums, int start, int end) {
// 终止条件
        if (start >= end) return;
// 核心代码
// temp记录标记点，left和right在移动；
// 此时left位置相当于空出，可以放置
        int left = start;
        int right = end;
        int temp = nums[left];
// 抛三个球
        while (left < right) {
            while (left < right && nums[right] >= temp) // 位置符合
                right--;
            nums[left] = nums[right]; // 位置不符：放到左边空位，并把自己当前位置空出
            while (left < right && nums[left] <= temp) // 位置符合
                left++;
            nums[right] = nums[left]; // 位置不符：放到右边空位，并把自己当前位置空出
        }
        nums[left] = temp; // 退出while时left == right，这是个空位，把temp标记点的数放入
// 递归：现在以left/right为边界，左边是比它小的，右边是比它大的
        sort(nums, start, left - 1);
        sort(nums, left + 1, end);
    }

    // 测试代码
    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, 7, 8, 2, 9, 6, 0, 5, 4};
        sort(nums, 0, nums.length - 1);
        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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41