Java中快速排序的优化技巧：随机取样、三数取中和插入排序

优化1：随机取样

在快速排序中，如果每次选择的基准元素都是数组的最左边或最右边，那么在输入数据接近有序时，性能会下降。为了解决这个问题，我们可以随机选择基准元素。

private static void quick(int[] arr,int start,int end){        if (start>=end){            return;        }        int randomIndex = getRandomIndex(start, end);        swap(arr, start, randomIndex);        int pivot=partition(arr,start,end);        quick(arr,start,pivot-1);        quick(arr,pivot+1,end);}public int getRandomIndex(int low, int high) {    Random rand = new Random();    return rand.nextInt(high - low + 1) + low;}

随机选择基准元素可以减小快速排序在特定输入下的性能波动。

优化2：三数取中

另一个性能优化的方法是选择中位数作为基准元素。这可以避免最坏情况下的快速排序性能下降。

private static void quick(int[] arr,int start,int end){        if (start>=end){            return;        }        //三数取中法        int index=midThree(arr,start,end);        int tmp=arr[start];        arr[start]=arr[index];        arr[index]=tmp;        int pivot=partition1(arr,start,end);        quick(arr,start,pivot-1);        quick(arr,pivot+1,end);}private static int midThree(int[] arr,int left,int right){        int mid=(left+right)/2;        if (arr[left]arr[right]){                return right;            }else {                return mid;            }        }else {            //arr[left]>right            if (arr[mid]arr[left]){                return left;            }else {                return mid;            }        }}

三数取中的方法可以有效地避免快速排序的最坏情况，提高了算法的稳定性。

优化3：插入排序

对于小规模的数组，快速排序的递归开销可能会变得显著。在这种情况下，使用插入排序可以提高性能。

private static void quick(int[] arr,int start,int end){        if (start>=end){            return;        }        if(end-start+1<=14){            //插入排序            insertSort2(arr, start, end);            return;        }        //三数取中法        int index=midThree(arr,start,end);        int tmp=arr[start];        arr[start]=arr[index];        arr[index]=tmp;        int pivot=partition(arr,start,end);        quick(arr,start,pivot-1);        quick(arr,pivot+1,end);    }    public static void insertSort2(int[] arr,int start,int end){        for (int i = start; i <= end; i++) {            int temp=arr[i];            int j=i-1;            while (j>=0&&arr[j]>temp){                arr[j+1]=arr[j];                j--;            }            arr[j+1]=temp;        }    }    private static int midThree(int[] arr,int left,int right){        int mid=(left+right)/2;        if (arr[left]arr[right]){                return right;            }else {                return mid;            }        }else {            //arr[left]>right            if (arr[mid]arr[left]){                return left;            }else {                return mid;            }        }    }    private static int partition(int[] arr,int left,int right ){        int tmp=arr[left];        while (left=tmp){                right--;            }            arr[left]=arr[right];            while (left