Java中快速排序優(yōu)化技巧之隨機取樣、三數(shù)取中和插入排序

更新時間：2023年09月25日 11:46:38 作者：謙虛的荊南芒果

快速排序是一種常用的基于比較的排序算法,下面這篇文章主要給大家介紹了關于Java中快速排序優(yōu)化技巧之隨機取樣、三數(shù)取中和插入排序的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下

前言

快速排序（Quick Sort）是一種高效的排序算法，它的平均時間復雜度為O(n log n)。然而，在某些情況下，快速排序可能表現(xiàn)不佳，特別是在輸入數(shù)據(jù)近乎有序或包含大量重復元素時。為了解決這些問題，我們可以對快速排序進行一些優(yōu)化。本文將介紹Java語言中如何使用隨機取樣、三數(shù)取中和插入排序等優(yōu)化技巧來提高快速排序的性能。

快速排序基礎

快速排序的基本思想是選擇一個基準元素（pivot），將數(shù)組分成兩個子數(shù)組，小于基準的元素放在左邊，大于基準的元素放在右邊，然后對這兩個子數(shù)組遞歸地進行排序。

public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
}
private static void quick(int[] arr,int start,int end){
        if (start>=end){
            return;
        }
        int pivot=partition(arr,start,end);
        quick(arr,start,pivot-1);
        quick(arr,pivot+1,end);
}
private static int partition(int[] arr,int left,int right ){
        int tmp=arr[left];
        while (left<right){
            while (left<right&&arr[right]>=tmp){
                right--;
            }
            arr[left]=arr[right];
            while (left<right&&arr[left]<=tmp){
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=tmp;
        return left;
}

優(yōu)化1：隨機取樣

在快速排序中，如果每次選擇的基準元素都是數(shù)組的最左邊或最右邊，那么在輸入數(shù)據(jù)接近有序時，性能會下降。為了解決這個問題，我們可以隨機選擇基準元素。

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;
}

隨機選擇基準元素可以減小快速排序在特定輸入下的性能波動。

優(yōu)化2：三數(shù)取中

另一個性能優(yōu)化的方法是選擇中位數(shù)作為基準元素。這可以避免最壞情況下的快速排序性能下降。

private static void quick(int[] arr,int start,int end){
        if (start>=end){
            return;
        }
        //三數(shù)取中法
        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]<right){
            if (arr[mid]<arr[left]){
                return left;
            }else if (arr[mid]>arr[right]){
                return right;
            }else {
                return mid;
            }
        }else {
            //arr[left]>right
            if (arr[mid]<arr[right]){
                return right;
            }else if (arr[mid]>arr[left]){
                return left;
            }else {
                return mid;
            }
        }
}

三數(shù)取中的方法可以有效地避免快速排序的最壞情況，提高了算法的穩(wěn)定性。

優(yōu)化3：插入排序

對于小規(guī)模的數(shù)組，快速排序的遞歸開銷可能會變得顯著。在這種情況下，使用插入排序可以提高性能。

private static void quick(int[] arr,int start,int end){
        if (start>=end){
            return;
        }
        if(end-start+1<=14){
            //插入排序
            insertSort2(arr, start, end);
            return;
        }
        //三數(shù)取中法
        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]<right){
            if (arr[mid]<arr[left]){
                return left;
            }else if (arr[mid]>arr[right]){
                return right;
            }else {
                return mid;
            }
        }else {
            //arr[left]>right
            if (arr[mid]<arr[right]){
                return right;
            }else 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<right){
            while (left<right&&arr[right]>=tmp){
                right--;
            }
            arr[left]=arr[right];
            while (left<right&&arr[left]<=tmp){
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=tmp;
        return left;
    }

注意：代碼里的小于14長度是我自己規(guī)定的，各位友友可以自己定義小數(shù)組的長度~~

插入排序在小規(guī)模數(shù)組上的性能通常比快速排序更好~~

總結：

在Java中，優(yōu)化快速排序的方法包括隨機取樣、三數(shù)取中和插入排序。這些優(yōu)化可以改善快速排序在各種輸入情況下的性能表現(xiàn)，使其成為一種強大而高效的排序算法。通過合理地選擇這些優(yōu)化技巧，可以根據(jù)實際需求來提高算法的性能。喜歡的友友可以關注一下博主噢??

到此這篇關于Java中快速排序優(yōu)化技巧之隨機取樣、三數(shù)取中和插入排序的文章就介紹到這了,更多相關Java隨機取樣、三數(shù)取中和插入排序內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: