快速排序

快排思路

基于冒泡排序，通过比较和交换。

1. 首先设定一个分界值，将小于等于分界值的放在左边，将大于分界值的放在右边；

2. 然后左边和右边的数据可以单独进行排序，也按照上述思路分为左右两部分；

3. 重复上述过程，这是一个递归排序。

时间复杂度：O(nLog2n) 最好情况：O(nLog2n) 最坏情况：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

复杂性：较复杂

Java实现

package com.wangjun.arithmetic;

import java.util.Arrays;

/*
 * 快速排序
 */
public class SortQuick {

    public static void main(String[] args) {
        int[] arr = {2,3,7,5,43,8,9,0,3,1};
        SortQuick ss = new SortQuick();
        ss.sortQuick(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void sortQuick(int[] arr) {
        sortHelper(arr, 0, arr.length - 1);
    }

    public void sortHelper(int[] arr, int start, int end) {
        int left = start;
        int right = end;
        int middle = arr[(left+right)/2];
        while(left < right) {
            /*
             * ? left不会越界么
             * 不会，因为它最多走到middle的位置，就相等了，不满足while条件；
             * 就算left和right都与middle相等然后交换了，剩下的交给递归去做
             */
            while(middle > arr[left]) {
                left++;
            }
            while(middle < arr[right]) {
                right--;
            }
            if(left < right) {
                int tem = arr[left];
                arr[left] = arr[right];
                arr[right] = tem;
                left++;
                right--;
            }
        }
        /*
         * ? 为啥要有这一步，为了完全隔开左右两边
         * 考虑到这种情况 7 5 3 排好序后是 3 5 7 这时left=right=1
         * 如果不让left++，那么左边和右边递归排序就重复了 5 这个值
         * 由于是同步的，右边先排好后，中间这个值可能已经不是5了
         * 还可能导致迭代死循环
         */
        if(left == right) {
            if(arr[left] > middle) { //处理边界值，保证左边都是小于等于middle的值，右边都是大于等于middle的值
                right--;
            }else {
                left++;
            }
        }
        if(left < end) {
            sortHelper(arr,left,end);
        }
        if(right > start) {
            sortHelper(arr, start, right);
        }
    }
}

写快排的时候可以分2步：

1. 写一个算法实现：取一个值，将小于它的放在左边，大于它的放在右边；

2. 将左右部分分别递归调用，注意下处理边界值就行了；