什么是快速排序

快速排序是一种效率很高的排序方式，假设对于某一数列进行增序排列，那么这个过程（快排）可以概括为：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

假设数列为{4,9,1,5,3,8,7,6,2}

我们先选取4为基准数，进行第二步排序可以得到的新数列为

{1,3,2,4,9,5,8,7,6}

那么此时可以得到2个字数列

{1,3,2},4,{9,5,8,7,6}

并且也确定了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
public static void QuickSort(int[] arr,int low ,int high ) {    //low代表数组第一个值的下表，high代表最后一个

    if (low >= high) {      //结束条件，传入函数的数组只有一个元素
        return;
    }
    int key = arr[low];        //选取关键字
    int i = low;
    int j = high;

    /*
    在i，j相遇之前
    j从数列尾部开始从右往左找，在不和i相遇的情况下找到一个比key小的数字后，i就开始从0开始从前往后找在在和j相遇之前如果找到一个比key大的值。那么交换他们的指向的值
    如果i，j相遇了，那么把i指向的元素赋给arr[low]，把key赋值给指向的元素.
    */
    while (i < j) {             
        while (arr[j] >= key && i < j) {
            j--;
        }
        while (arr[i] <= key && i < j) {
            i++;
        }
        if (i < j) {
            int tem = arr[i];      //交换值
            arr[i] = arr[j];
            arr[j] = tem;
        }

    }
    arr[low] = arr[i];      
    arr[i] = key;           
    QuickSort(arr, low, i - 1);        //处理子数组
    QuickSort(arr, i + 1, high);
}

算法时间复杂度

  • 快速排序最优的情况下时间复杂度为：O( nlogn )

（快速排序最优的情况就是每一次取到的元素都刚好平分整个数组）

  • 快速排序最差的情况下时间复杂度为：O( n^2 )

（最差的情况就是每一次取到的元素就是数组中最小/最大的，这种情况其实就是冒泡排序了）

  • 快速排序的平均时间复杂度也是：O(nlogn)

空间复杂度

最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况

最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况