快速排序，Java实现快速排序以及泛型设计快速排序

本文主要介绍了三版快速排序，第三版是最终版本，也是优化后性能最佳的版本。

1、快排的时间复杂度为O(nlogn)。是原地排序算法，空间复杂度为O(1)，是不稳定排序算法。

2、之所以快是因为不断的划分，类似于归并排序法，但是归并是每次取一半，快排是不一定取一半，可能左边多右边少，也可能右边多左边少。

3、对于未经过任何优化过的快速排序，数组越有序排序的效率越低，因为当数组完全有序会生成一个深度为元素个数的栈，很有可能超出系统栈的深度。可以通过随机数选取来优化这样的问题。

4、快速排序算法是一种随机算法。随机分配每个区间

快速排序的大致思想：先进行一次快排分为左右的空间，然后递归左右两个子空间，直到右边界<=左边界。

核心在于Partition函数，为了让每次选择的那个元素在应该呆在的位置。这个元素的下标就是其左边的元素都是小于它的，右面的都是大于它的

大致思想：如上图所示，

1、每次选取一个特定的元素v，操作指针j和i。

2、i是扫描的元素，如果i指向的元素<标志元素V，则让指针j++并且交换i和j对应元素的值，结束的条件是i大于当前元素的最右边界限

3、当i>最右边元素的值时，交换下标j和L对应的元素，使其保证arr[l,j-1]是小于标志点元素V的，arr[j+1,r]是大于标志元素V的。最终返回j点的索引。

4、之后进行递归分别对j左边和j右边的元素分别进行快排，从而达到递归的效果。

public class QuickSort {
    public QuickSort() {
    }

    //单路快速排序，无法实现对数据全为一样的数组进行快排
    public static > void sort(E arr[]) {
        Random random = new Random();
        sort(arr, 0, arr.length - 1, random);
    }

    private static > void sort(E arr[], int l, int r, Random random) {
        if (l >= r) return;
        int flagIndex = partition(arr, l, r, random); //flagIndex就是左边的都小于它，右边的都大于它
        sort(arr, l, flagIndex - 1, random);//此处传参为index-1因为不对标志元素进行排序
        sort(arr, flagIndex + 1, r, random);
    }

    //l+1~j是小于的区间 j~i-1是大于的，j是一个分界点i~r是还未处理的元素
    private static > int partition(E[] arr, int l, int r, Random random) {
//        避免当数组为完全有序时，调用系统栈次数为元素的个数，使其系统栈溢出
        int index = random.nextInt(r - l + 1) + l;
        swap(arr, l, index);
        int j = l;//j只得就是大于和小于的分界点
        E flag = arr[l];
        for (int i = l + 1; i <= r; i++) {
            if (arr[i].compareTo(flag) < 0) {
                j++;
                swap(arr, j, i);
            }
        }
        swap(arr, l, j);
        return j;
    }
}

第二版快速排序主要是优化第一版本对数组元素完全相同或重复元素较多时的效率下降问题，双路排序将与标志元素相同的元素均匀分布在大于和小于数据的两端。

 如上图所示，

1、起初橙色和紫色是空区间，i从L+1开始，j从r+1开始，

2、直到i找到>=v的元素，j找到<=v的元素停止。或者i>j,j

3、交换i和j下标对应的元素

4、一直遍历直到i.j时退出循环。

5、最后在arr[l,j-1]是<=flag的，arr[j+1，r]是>=目标元素的。

    //二路快速排序，实现可以对完全相同数组的排序，应对所有问题，但是对有大量重复数据的性能不如三路快排
    public static > void sort2Ways(E arr[]) {
        Random random = new Random();
        sort2Ways(arr, 0, arr.length - 1, random);
    }

    private static > void sort2Ways(E arr[], int l, int r, Random random) {
        if (l >= r) return;
        int flagIndex = partition2Ways(arr, l, r, random);
        sort2Ways(arr, l, flagIndex - 1, random);//此处传参为index-1因为不对标志元素进行排序
        sort2Ways(arr, flagIndex + 1, r, random);
    }

    private static > int partition2Ways(E[] arr, int l, int r, Random random) {
//        避免当数组为完全有序时，调用系统栈次数为元素的个数，使其系统栈溢出
        int index = random.nextInt(r - l + 1) + l;
        swap(arr, l, index);
        //就变在了这个while循环，i指的是要开始遍历的元素，j是大于区间的第一个元素
        int i = l + 1, j = r;
        //尽管是两层，但是是O(n)级别的
        //l+1~i-1是小于等于的元素 i~j-1是要扫描的元素，j~r是大于等于的元素
        while (true) {
            //寻找比目标元素大于等于的元素，用于放左边
            while (i <= j && arr[i].compareTo(arr[l]) < 0)
                i++;
            //寻找比目标元素小于等于的元素，用于放右边
            while (j >= i && arr[j].compareTo(arr[l]) > 0)
                j--;

            if (i >= j) break; //退出的条件

            //无论有没有最终都是将这两个元素交换一下，并且将等于flag的元素进行一次交换
            //性能低下体现在这里，当两个元素都等于flag的时候还是要进行一次交换
            //假设有三个等于flag的元素，，它就会把另外两个加入到大于和小于的区间里，大于和小于的区间元素越多，最后递归的深度就会越深，此时的性能就会越差
            swap(arr, i, j);
            i++;
            j--;
        }
        swap(arr, l, j);
        return j;
    }

三路排序与二路排序的唯一区别在于三路排序每次递归的过程中不会将每次与flag的元素再次进行递归，进一步最大的优化了效率。是快速排序的最终版本。

1、可以应对完全有序的数组。

2、可以处理元素全部相同的数组。

3、没有开辟额外的内存空间。

4、当数据完全有序时，时间复杂度为O(n)只需要遍历一遍数组即可。

1、在每次排序之后arr[l,lt-1]是flag元素的。

 2、每次对(l,lt-1)和(gt,r)进行递归操作，而对于(lt,gt)的这一段==flag的不再进行递归操作。

//三路快速排序,解决数据中包含大量重复数据。相当于对二路的一种优化，主要优化等于flag的部分
    
    public static > void sort3Ways(E arr[]) {
        Random random = new Random();
        sort3Ways(arr, 0, arr.length - 1, random);
    }

    private static > void sort3Ways(E arr[], int l, int r, Random random) {
        if (l >= r) return;

        int index = random.nextInt(r - l + 1) + l;
        swap(arr, l, index);

        //[l+1,lt]是全部 0) {
                gt--;
                swap(arr, i, gt);
                //i++此处没有i++因为右面的元素都是未知元素，而左面的都是已经判断好了是小于flag的，所以只需要直接放到区间里直接判断即可
            } else {//arr[i]==flag
                i++;
            }
        }
        //将lt放到等于的那个区间里，此时[l,lt-1]小于的区间[lt,gt-1]等于的区间[gt,r]大于的区间
        swap(arr, l, lt);
        //核心改变处，只处理应该递归的那部分元素，而不是将全部元素都进去递归
        sort3Ways(arr, l, lt - 1, random);
        sort3Ways(arr, gt, r, random);
    }

 整个算法的优化过程：

1、单路排序法，无法解决完全相同的元素-->引入了随机数

2、单路无法应对完全相同或数组有序度较高问题以及所有元素都一样的数据----->>双路排序算法，将等于的平均分配在了两边

3、双路排序在完全相同的数据中，有重复递归现象--->三路排序算法