前言

最近正在准备秋招面试，基础的算法当然要好好稳固一下啦，虽然以前写过排序算法，但是很久没写都快忘了，在这里记录，顺便好好复习一下。

基本思路

1. 确定基准数【一般选取数组中第一个值作为基准数】
2. 对数组进行遍历，将大于基准数的放在数组左边，小于基准数的放在数组右边。这样原数组就可以根据基准数分为左右两个数组。
3. 重复递归执行1,2 两个过程，直到数组中只存在一个元素。

动图展示

代码实现

/*
 by author: lvjianyou
*/
public class QuickSort2 {

    public static void sort(int[] arr,int start,int end){
        //新定义左右指针，方便用于移动。因为要进行递归，传过来的参数我们不能直接改变。
        int i,j,privt;
        i = start;
        j = end;
        //该方法要进行递归，所以需要有终止条件
        if(start<=end) return;
        //选取数组第一个元素作为基准数 ===== 对应第一步
        privt = arr[start];
        
        //将大于基准数的元素放到右边，将小于基准数的元素放到左边 ======对应第二步
        while(i<j){
            //先从右边进行判断，一定要先从右边判断，不能先从左边开始判断！
            //为什么？ 因为左边第一位数已经复制出来了，若从左边开始将会覆盖掉右边的数。
            while (i<j){
                if(arr[end]>privt){
                    end--;
                }else{
                    //右边数小于等于基准数，移动！
                    arr[i++] = arr[end];   //没有交换的操作，直接覆盖，第一位数已经复制出去了，所以覆盖无所谓。
                    break;
                }
            }
            //左边数进行遍历比较
            while(i<j){
                //左边数小于基准数
                if(arr[i]<privt){
                    //指针加1即可
                    i++;
                }else{
                    //左边数大于基准数，需要将数放到数组右边，并交换到右边进行遍历。
                    arr[j--] = arr[i];
                    break;
                }
            }
        }

        //交换结束,此时i==j，基准数归位
        arr[i] = privt;

        //重复执行该操作     =========对应第三步
        sort(arr,start,i-1);
        sort(arr,i+1,end);


    }
}

复制代码

复杂度分析

时间复杂度：平均为 O(nlogn),最坏时候的时间复杂度为 O(n^2)