Quick Sort

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

基本思想

1.在一列数组中取一个数作为基数

2.分区过程，先从右边开始小于这个基数的值放在左边，在从左边开始把大于基数的值放入右边

3.递归基数左边和右边区间重复第二部，直到只有一个值结束

图解

初始值

右边找小于基数的数值

  • 挖坑，因为我们要交换位置所以要挖一个坑出来

  • 把基数放入到坑中我们这里选6位基数，然后在右边找数填左边的坑。

  • 右边开始找找到3比基数6小，交换它们的位置。

左边找大于基数的数值

  • 左边开始找到了7大于基数的数字，交换位置后的值。

重复以上步骤，知道i和j相等的时候结束第一次排序

  • 分区排序完后的值

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
static void quick(int s[], int l, int r) {
        //保证区间起码有一位数
        if (l < r) {
            int i = l;
            int j = r;
            int x = s[l];
            //i<j保证 left的i和right的j不会重合
            while (i < j) {
                //找小于等于x的数,如果是大于就j--继续往前走。
                while (i < j && s[j] >= x) {
                    j--;
                }
                if (i < j) {
                    s[i] = s[j];
                }
                //找大于等于x的数，如果小于就i++继续往前走
                while (i < j && s[i] <= x) {
                    i++;
                }
                if (i < j) {
                    s[j] = s[i];
                }
            }
            s[i] = x;
            quick(s, l, i - 1);
            quick(s, i + 1, r);
        }
    }
1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
       int[] array = new int[]{9, 6, 8, 7, 1, 100, 3, 2, 0, 14};
       quick(array, 0, array.length - 1);

       for (int i : array) {
           System.out.println(i);

       }
   }

博客参考

博客参考