算法思想

采用分治的思想，步骤可以概括为：

1. 选取基准值pivot(一般默认选开始的位置)
2. 将小于pivot的数放在左边，大于pivot的数放在右边(挖坑填补法)
3. 对pivot左边和右边的序列分别递归执行步骤1、2

代码实现

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

public class Quicksort {
    public static void main(String[] args) {
        int[] array = new int[]{0,3,7,2,5,8,4,6,0,1};
        quicksort(array,0,array.length-1);
        for(int i=0;i<array.length;i++){
            System.out.println(array[i]);
        }
    }

    public static void quicksort(int[] array,int start, int end){
        if(start >= end) {
            return;
        }
        int left = start;
        int right = end;
        int pivot = array[start];


        while(left < right){
            //从右边找小于pivot的数
            while(right > left && array[right] >= pivot) {
                right--;
            }
            //找到交换，right位置的数填到left，right挖坑
            array[left] = array[right];

            //从左边找大于pivot的数
            while(left < right && array[left] <= pivot) {
                left++;
            }
            //找到交换，left位置的数填到right，left挖坑
            array[right] = array[left];
        }

        //此时left = right，最后一个坑填pivot
        array[right] = pivot;

        quicksort(array, start,left - 1);
        quicksort(array, right + 1, end);
    }
}

• 初始main第4行调用quicksort(array, 0, 9);
  • left为0，right为9，pivot为5
  • left为0，right为9，left小于right，进入15行if结构体
    • left为0，right为9，left小于right，进入16行while结构体
      • 17行的while条件中array[right] = array[9] = 3，小于pivot为5，退出while循环
      • 20行array[left] = array[right]，即array[0] = array[9]，此时array变成[3,2,4,1,6,8,10,7,9,3];
      • 22行的while循环一直到left = 4才停止，此时array[left] = array[4] = 6，大于pivot为5，退出while循环
      • 25行array[right] = array[left], 即array[9] = array[4]，此时array变成[3,2,4,1,6,8,10,7,9,6];
    • 此时left为4，right为9，left小于right，再次进入16行while结构体
      • 17行的while循环一直到left = right，都为4，此时不满足right > left，退出while循环
      • 20行array[left] = array[right]，即array[4] = array[4]，此时array还是[3,2,4,1,6,8,10,7,9,6];
      • 22行的while循环不满足left < right，退出while循环
      • 25行array[right] = array[left]，即array[4] = array[4]，此时array还是[3,2,4,1,6,8,10,7,9,6];
    • 此时left = right = 4，不满足循环条件，退出16行的while
    • 28行array[right] = pivot，即array[4] = 5，此时array变成[3,2,4,1,5,8,10,7,9,6]，此时小于5的值都在5的左边，大于5的值都在5的右边
    • 30行调用quicksort(array,0,5);
    • 31行调用quicksort(array,7,9);

复杂度

时间复杂度

• 最好情况O(nlogn)：当每次选择的基准值都是待排序列的中值时，总共需要递归O(logn)次，每层花费时间O(n)，即O(nlogn);
• 最差情况O(n²)：当每次选择的基准值都是待排序列的最值时，相当于直接插入排序，总共需要递归O(n)次，每层花费时间O(n)，即O(n²);
• 平均情况O(nlogn)

空间复杂度

概括来讲快排的每层都只使用了常数空间(一个空间用于保存pivot的值），因此空间复杂度等于递归调用的深度即最好为O(logn)，最差为O(n);

稳定性

• 不稳定：待排序列为[6,1,3,7,3](注意原来不加粗3在加粗3的左边)，经过一次排序后(以6为pivot)，序列变成[3,1,3,6,7]，最终排序结果为[1,3,3,6,7]，可以发现不加粗3到了加粗3的右边，相等元素之间相对位置发生了变化，因此快排是不稳定的

总结