快速排序简单记录

快速排序是一个经典的排序算法，网上很多解释感觉都比较难以理解，经常看完之后过几天就忘了，这里主要简单谈下自己对快排算法的理解，并提供相对应的代码。

首先，快排是基于分治法的思想。算法主要有两个部分构成：
Merge 和 Partition .

Partition 部分是这个算法的核心，主要做的事情就是选择数组中一个数字当成关键字Key，然后将数组中所有比这个数小的数字移到Key的左边，将数组中比这个数字大的所有数字移动到Key的右边。

具体实现代码如下:

    public int partition(int[] nums, int left, int right){
        int key = nums[right];
        int startIndex = left;
        int smallIndex = startIndex;
        while(startIndex <= right-1){
            if(nums[startIndex]<key){
                if(startIndex!=smallIndex){
                   swap(nums,startIndex,smallIndex);
                }
                smallIndex++;
            }
            startIndex++;
        }
        if(smallIndex!=right) {
            swap(nums,smallIndex,right);
        }
        return smallIndex;
    }

这部分代码理解起来容易，具体实现却没有那么直白。我的做法是选择数组中最右边的那个数字做为Key, 然后用一个startIndex来从left到right-1遍历数组，把数组中所有比Key小的数字放在数组最左边, 并且用一个smallIndex来记录数组最左边可以放比Key小的数字的位置。这样当遍历完数组后，只要把key放到smallIndex的右边，就能保证数组中key左边的所有的元素比key小，key右边的所有元素比key大.

Merge 部分只需要根据 partition函数返回的 index，将数组划分成 left 到 index-1 部分和 index+1 到 right 部分，并且递归地调用MergeSort这个函数，这样当这两部分切分到只有一个元素或者为空的时候，把所有结果拼接起来，返回的结果就是Sort好的数组.

完整的代码实现如下：

  public void quickSort(int[] nums,int left,int right){
        if(nums==null || left>=right) return;
        int index = partition(nums,left,right);
        quickSort(nums,left,index-1);
        quickSort(nums,index+1,right);

    }

    public int partition(int[] nums, int left, int right){
        int key = nums[right];
        int startIndex = left;
        int smallIndex = startIndex;
        while(startIndex <= right-1){
            if(nums[startIndex]<key){
                if(startIndex!=smallIndex){
                   swap(nums,startIndex,smallIndex);
                }
                smallIndex++;
            }
            startIndex++;
        }
        if(smallIndex!=right) {
            swap(nums,smallIndex,right);
        }
        return smallIndex;
    }

    public void swap(int[] nums, int key1, int key2){
        int temp = nums[key1];
        nums[key1] = nums[key2];
        nums[key2] = temp;
        return;
    }