快速排序（Quicksort）是对冒泡排序算法的一种改进。
 基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1 算法步骤

1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

效果图：
 

2 复杂度

最优时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)

最坏的情况是待排序数组是逆序的，此时需要比较次数最多，最坏情况下的时间复杂度为 O ( n 2 ) O(n^2) O(n2)

空间复杂度为 O ( 1 ) O(1) O(1)

3 稳定性

不稳定的，数据的相对顺序会发生改变。
 

4 代码实现

private static void quickSort(int[] ary){
    quickSort(ary, 0, ary.length - 1);
    System.out.println("quick sort:"+ Arrays.toString(ary));
}

private static void quickSort(int[] ary, int left, int right){
    if(left < right){
        //
        int ind = partition(ary, left, right);
        quickSort(ary, left, ind - 1);
        quickSort(ary, ind + 1, right);
    }
}

private static int partition(int[] ary, int left, int right){
    int base = left;
    int ind = left + 1;
    for(int i = ind; i <= right; i++){
        if(ary[i] < ary[base]){
            swap(ary, i, ind);
            ind ++;
        }
    }
    swap(ary, base, ind - 1);
    return ind - 1;
}
//交换位置
private static void swap(int[] ary, int left, int right){
    if(left != right){
        int tmp = ary[left];
        ary[left] = ary[right];
        ary[right] = tmp;
    }
}

欢迎大家关注、评论、点赞、打赏。
你们的支持是我坚持的动力。Thank you!