排序算法的一些优化和改进2

6、快速排序 O(nlogn)

   public static void sort(Comparable[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    
    //递归使用快速排序，对arr[left...right]的范围进行排序
    private static void quickSort(Comparable[] arr, int left, int right) {

        if (left >= right) {
            return;
        }

        int partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);

    }
    
    // 对arr[left...right]部分进行partition操作
    //返回partitionIndex 是的arr[left...partition-1]<arr[partitionIndex];  arr[partion+1...r]>arr[partitionIndex]
    private static int partition(Comparable[] arr, int left, int right) {

        Comparable v = arr[left];

        int partitionIndex = left;
        for (int i = left + 1; i <= right; i++) {
            if (arr[i].compareTo(v) < 0) {
                SortTestHelper.swap(arr, partitionIndex, i);
                partitionIndex++;
            }
        }

        arr[partitionIndex] = v;

        return partitionIndex;
    }

递归使用快速排序，对arr[left...right]的范围进行排序
对arr[left...right]部分进行partition操作
返回partitionIndex 是的arr[left...partition-1]<arr[partitionIndex]; arr[partion+1...r]>arr[partitionIndex]

快速排序也可以进行优化，当元素个数小于15的时候，比较接近有序状态，可以用针对有序队列排序效率高的插入排序进行优化,代码如下：

    //递归使用快速排序，对arr[left...right]的范围进行排序
    private static void quickSort(Comparable[] arr, int left, int right) {

        if (left >= right) {
            return;
        }

       if(right-left<=15){
          insertSort(arr,left,right);
       }

        int partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);

    }

    //插入排序 
    public static void insertSort(Comparable[] arr,int left,int right) {
        for (int i = left; i <=right; i++) {
            for (int j = i; j > left; j--) {
                if (arr[j].compareTo(arr[j - 1]) > 0) {
                    break;
                }

                SortTestHelper.swap(arr, j, j - 1);
            }
        }
    }

快速排序性能会比归并排序效率要高，但是有人对于接近有序队列，快速排序要比归并排序性能要差很多，归并排序每次平分的平衡性要比快速排序的要好，归并排序拆分的高度能保证是logn的，而快速排序并不能保证高度为logn，所以快速排序最坏的情况是退化为O(n^2)的。

快速排序不需要额外的空间。如果数据量大而且数据全部存放在内存中，那么

快速排序是首选的排序方法。具体的排序过程是先将元素分成两个区，所有小于某个元素的值在第一个区，其他元素在第二区。然后分别对这两个区进行快速排序，直到所分的区只剩下一个元素为止。

为了解决快速排序分割数组时，分布不均的问题，每次选择partitionIndex的时候，采用随机生成的方式 ,详见下面代码的：
SortTestHelper.swap(arr, left, (int) (Math.random() * (right - left + 1)) + left);
或者
Integer randomIndex = left+random.nextInt(right - left + 1);
SortTestHelper.swap(arr, left, randomIndex);

    // 对arr[left...right]部分进行partition操作
    //返回partitionIndex 是的arr[left...partition-1]<arr[partitionIndex];  arr[partion+1...r]>arr[partitionIndex]
    private static int partition(Comparable[] arr, int left, int right) {

        //Comparable v = arr[left];
        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        SortTestHelper.swap(arr, left, (int) (Math.random() * (right - left + 1)) + left);
        Comparable v = arr[left];
        int partitionIndex = 0;
        for (int i = left + 1; i <= right; i++) {
            if (arr[i].compareTo(v) < 0) {
                SortTestHelper.swap(arr, partitionIndex, i);
                partitionIndex++;
            }
        }

        arr[partitionIndex] = v;

        return partitionIndex;
    }

当需要排序的数据含有大量的重复元素的时候，快速排序的子序列的划分会极其不平衡，二分递归会退化为线性递归，递归深度接近于O(n)。为了解决这个问题，可以采用双排或者三排

快速排序 双排

private static int partition(Comparable[] arr, int left, int right) {
        //随机选一个 povit
        int swapLeft = (int) (Math.random() * (right - left + 1) + left);
        SortTestHelper.swap(arr, left, swapLeft);

        Comparable v = arr[left];
        int i = left + 1;
        int j = right;
        while (true) {
            while (i <= right && arr[i].compareTo(v) < 0) {
                i++;
            }
            while (j >= left+1 && arr[j].compareTo(v) > 0) {
                j--;
            }

            if (i >j) {
                break;
            }

            SortTestHelper.swap(arr, i, j);
            i++;
            j--;
        }
        SortTestHelper.swap(arr, left, j);
        return j;
    }

快速排序 三路快排思想

// 递归使用快速排序,对arr[l...r]的范围进行排序
    private static void quickSortThreeWays(Comparable[] arr, int left, int right) {

        if (left >= right) {
            return;
        }

        // 对于小规模数组, 使用插入排序
        if (right - left <= 15) {
            //优化代码
        }

        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        int swapLeft = (int) (Math.random() * (right - left + 1) + left);
        SortTestHelper.swap(arr, left, swapLeft);
        Comparable v = arr[left];

        int lt = left;  // arr[l+1...lt] < v
        int gt = right + 1; //  arr[gt...r] > v
        int et = left + 1;// arr[lt+1...i) == v

        while (et < gt) {

            if (arr[et].compareTo(v) < 0) {
                if (et != lt + 1) {
                    SortTestHelper.swap(arr, et, lt + 1);
                }
                et++;
                lt++;
                continue;
            }

            if (arr[et].compareTo(v) > 0) {
                SortTestHelper.swap(arr, et, gt - 1);
                gt--;
                continue;
            }
            //arr[et].compareTo(v) == 0
            et++;
        }

        SortTestHelper.swap(arr, left, lt);
        //et 的 不变
        quickSortThreeWays(arr, left, lt - 1);
        quickSortThreeWays(arr, gt, right);
    }