快速排序

思路：

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

复杂度分析：

其平均时间复杂度与归并排序均为O(nlogn)，但是归并排序除了递归调用间接使用了辅助空间栈，还需要额外的O(n)空间进行临时存储。从此角度归并排序略逊于快速排序，但是归并排序是一种稳定的排序算法，快速排序则不然。

所谓稳定排序，表示对于具有相同值的多个元素，其间的先后顺序保持不变。对于基本数据类型而言，一个排序算法是否稳定，影响很小，但是对于结构体数组，稳定排序就十分重要。

下面是三种快排实现，其中针对特殊的情况

（1）对已排序的序列进行快排

（2）对数字全部相同的一个序列进行快排

上面两种情况都会导致快排的时间复杂度达到O(n^2)，所以有了双轴快排和随机化快排

一、经典快排

public class QuickSort {
    /**
     * 快速排序算法
     */
    public static void quickSort(int[] list, int left, int right) {
        if (left < right) {
            // 分割数组，找到分割点
            int middle = partition(list, left, right);
            
            // 递归调用，对左子数组进行快速排序
            quickSort(list, left, middle - 1);
            // 递归调用，对右子数组进行快速排序
            quickSort(list, middle + 1, right);
        }
    }
    /**
     * 分割数组，找到分割点
     */
    public static int partition(int[] list, int left, int right) {
        // 用数组的最后一个元素作为基准数

        int less = -1; // less区，小于基准的元素都放在其左边
        while (left < right){
            if(list[left] < list[right]){
                less++;
                swap(list, less, left);
            }
            left++;
        }
        swap(list, less+1, right);// 将基准值放序列中间，完成partition过程

        return less+1;
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] list, int left, int right) {
        int temp;
        if (list != null && list.length > 0) {
            temp = list[left];
            list[left] = list[right];
            list[right] = temp;
        }
    }
}

二、双轴快排

双轴快排避免了由于待排序列是有序的，而导致时间复杂度达到O(n^2)的情况

public class QuickSort {
    /**
     * 快速排序算法
     */
    public static void quickSort(int[] list, int left, int right) {
        if (left < right) {
            // 分割数组，找到分割点
            int middle = partition(list, left, right);
            
            // 递归调用，对左子数组进行快速排序
            quickSort(list, left, middle - 1);
            // 递归调用，对右子数组进行快速排序
            quickSort(list, middle + 1, right);
        }
    }
    /**
     * 分割数组，找到分割点
     */
    public static int partition(int[] list, int left, int right) {
        // 选取第一个元素为基准

        int flag = list[left];
        while (left < right) {
            while (left < right && list[right] >= flag) {
                right--;
            }
            // 交换
            swap(list, left, right);

            while (left < right && list[left] <= flag) {
                left++;
            }
            // 交换
            swap(list, left, right);
        }
        // 返回分割点所在的位置
        return left;
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] list, int left, int right) {
        int temp;
        if (list != null && list.length > 0) {
            temp = list[left];
            list[left] = list[right];
            list[right] = temp;
        }
    }
}

三、随机化快排

随机数快排避免了由于待排序列是相同的数，而导致时间复杂度达到O(n^2)的情况

public class QuickSort {
    /**
     * 快速排序算法
     */
    public static void quickSort(int[] list, int left, int right) {
        if (left < right) {
            // 分割数组，找到分割点
            int middle = partition(list, left, right);
            
            // 递归调用，对左子数组进行快速排序
            quickSort(list, left, middle - 1);
            // 递归调用，对右子数组进行快速排序
            quickSort(list, middle + 1, right);
        }
    }

    /**
     * 分割数组，找到分割点
     */
    public static int partition(int[] list, int left, int right) {
        // 随机选取一个基准
        int length = right-left+1;
        int index = new Random(47).nextInt()%(length+left);
        // 将随机基准放到序列首部，之后以首部为基准进行快排
        swap(list, left, index);
        
        int flag = list[left];
        while (left < right) {
            while (left < right && list[right] >= flag) {
                right--;
            }
            // 交换
            swap(list, left, right);

            while (left < right && list[left] <= flag) {
                left++;
            }
            // 交换
            swap(list, left, right);
        }
        // 返回分割点所在的位置
        return left;
    }

    /**
     * 交换数组中两个位置的元素
     */
    public static void swap(int[] list, int left, int right) {
        int temp;
        if (list != null && list.length > 0) {
            temp = list[left];
            list[left] = list[right];
            list[right] = temp;
        }
    }
}

以上是我在学习过程中对于快排的总结，若有不足之处，欢迎评论。