算法复习之——快速排序

原理分析

快速排序原理，简单来说就是一个分治和递归思想，我们可以分成两部分理解：

（1）在数组中找到一个基准数，让它左边的数都比它小，右边的数都比它大
（2）根据递归思想用（1）中的方法去分别处理这个基准数左边和右边的数组

这样我们就排好序了，难点就是如何将比基准数小的放在它的左边，比它大的放在右边。这篇文章的分析十分形象，可以看点击这里参考下，比我组织的语言好很多，最后附上源码。

程序实现

public static int[] QuickSort(int[] nums,int low,int high) {
        
        if(low>high) {
            return nums;
        }
        int start = low;
        int end = high;
        int key = nums[low];
        
        while(end > start) {
            //如果后面得数比基准数大，则继续往前比较
            while(nums[end]>=key && start<end) {
                end--;
            }
            //如果前面的数比基准数小，继续往后比较
            while(nums[start]<=key && start<end) {
                start++;
            }
            //前面两个循环跳出后，start依然小于end的话，则交换两个数的位置
            if(start<end) {
                int temp = nums[end];
                nums[end] = nums[start];
                nums[start] = temp;
            }
        }
        /*整个循环跳出，意味着end和start重合，也就是这个数左边不会有比基准数大的数，
        右边不会有比基准数小的数，这时我们将重合位置的数和基准数交换位置*/
        nums[low] = nums[start];
        nums[start] = key;
        //递归排序基准数左右的数
        QuickSort(nums, low, start-1);
        QuickSort(nums, start+1, high);
        return nums;
    }