快排算法

这里对快速排序做一下总结（之前在写时间复杂度和空间复杂度时候想到的。）

1. 思想

快排的思想就是说，选定数组中第一个数参考值 key ，然后用两个指针，分别从前往后，从后往前，把比 key 大的放在后边，比 key 小的放在前边。两个指针相遇之后，把 key 和 这个停止点的值交换。至此完成一趟排序，到这里，比key大的都在key后面，比key小的都在key前面。
对 key 左边的子组迭代，对key右边的子组迭代，直到子组只含有一个数字为止。
这里用图来给出直观的展示：

快排图示

2. 代码

public class QuickSort {

    public void sort(int[] nums,int start,int end) {
        // 递归停止条件
        if(start>end) return;
        int left=start,right=end,key=nums[start];
        int temp=0;
        while(left<right){
            // 这里顺序很重要，要先从右边找。为了避免找过了的情况，还要限制 left<right
            while(left<right && nums[right]>=key)
                right--;
            while (left<right && nums[left]<=key)
                left++;
            temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            }

        nums[start] = nums[left];
        nums[left] = key;

        sort(nums,start,left-1);  // 这里对子组求一个递归即可
        sort(nums,left+1,end);
        }

    public static void main(String args[]){
        int a[] = {6,1,2,7,9,3,4,5,10,8};
        QuickSort q = new QuickSort();
        q.sort(a,0,a.length-1);
        for(int i=0;i<a.length;i++){
            System.out.print(a[i]);
        }
    }
}

3. 关键点

• 是递归的，对子数组
• 递归停止条件是 start>end
• 一趟中，要从右向左找
• 同时为了避免找过了的情况，还要限制 left<right 指针

时间复杂度 nlogn