快捷導(dǎo)航

Java Arrays.sort()如何實(shí)現(xiàn)對(duì)int類型數(shù)組倒序排序

更新時(shí)間：2023年08月21日 09:59:02 作者：mp-ui

這篇文章主要介紹了Java Arrays.sort()如何實(shí)現(xiàn)對(duì)int類型數(shù)組倒序排序問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教

Java Arrays.sort()實(shí)現(xiàn)對(duì)int類型數(shù)組倒序排序

Java的Arrays.sort()僅支持對(duì)引用數(shù)據(jù)類型進(jìn)行自定義排序，如果是基本數(shù)據(jù)類型（如int類型），將無(wú)法使用Comparator進(jìn)行自定義排序。

可以使用下面的方法來(lái)實(shí)現(xiàn)

1.手動(dòng)實(shí)現(xiàn)排序算法。
2.先排序再reverse

int[] nums = new int[]{1,6,4,55,61,3,5,8,4,2,8,15,61,33};
	Arrays.sort(nums);
	for (int i = 0; i < nums.length/2; i++) {
	    int temp = nums[i];
	    nums[i] = nums[nums.length - 1 - i];
	    nums[nums.length - 1 - i] = temp;
	}
	System.out.println(Arrays.toString(nums));

3.轉(zhuǎn)換成Integer[]

    int[] nums = new int[]{1,6,4,55,61,3,5,8,4,2,8,15,61,33};
    Integer[] temp = new Integer[nums.length];
    for (int i = 0; i < temp.length; i++) {
        temp[i] = nums[i];
    }
    Arrays.sort(temp,(i,j)->(j-i));
    for (int i = 0; i < nums.length; i++) {
        nums[i] = temp[i];
    }
    System.out.println(Arrays.toString(nums));

Arrays.sort()用的是什么排序算法？怎么優(yōu)化？

Arrays.sort()用的是快速排序算法。相信大家對(duì)于這個(gè)都是了解的。

算法的思想

選擇基準(zhǔn)將數(shù)組一分為二，基準(zhǔn)前面的比基準(zhǔn)小，基準(zhǔn)后面的比基準(zhǔn)大，之后分別對(duì)這兩部分繼續(xù)之前的操作，已達(dá)到整個(gè)數(shù)組有序的目的。

算法內(nèi)容描述

先選擇一個(gè)基準(zhǔn)，指向數(shù)組開始的指針start和指向數(shù)組結(jié)束的指針end；
當(dāng)start小于end的時(shí)候，如果基準(zhǔn)的值小于end指向數(shù)組的值時(shí)，end往前移動(dòng)；
當(dāng)基準(zhǔn)的值不在小于end指向數(shù)組的值的時(shí)候，交換兩個(gè)指針指向的數(shù)組的值；
然后當(dāng)基準(zhǔn)的值大于start指向數(shù)組的值的時(shí)候，start往后移動(dòng)；
當(dāng)基準(zhǔn)的值不大于start指向數(shù)組的值的時(shí)候，交換兩個(gè)指針指向的數(shù)組的值；
返回基準(zhǔn)的位置并進(jìn)行遞歸操作完成排序。

代碼如下：

public class Test2 {
    public static void swap(int[] arr, int j, int i){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
    public static int partition(int arr[], int start, int end){
        assert(null != arr);
        int temp = arr[start];
        while(start < end){
            while(temp < arr[end] && start < end){
                end--;
            }
            swap(arr, start, end);
            while(temp > arr[start] && start < end){
                start++;
            }
            swap(arr, start, end);
        }
        System.out.println(Arrays.toString(arr) + "   " +  start);
        return start;
    }
    public static void partitionSort(int arr[], int start, int end){
        assert(null != arr);
        if(start < end){
            int midd = partition(arr, start, end);
            partitionSort(arr, start, midd - 1);
            partitionSort(arr, midd + 1, end);
        }
    }
    public static void main(String[] args) {
        int arr[] = {9,1,5,8,3,7,4,6,2};  
        Test2.partitionSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

執(zhí)行結(jié)果：

[2, 1, 5, 8, 3, 7, 4, 6, 9] 8
[1, 2, 5, 8, 3, 7, 4, 6, 9] 1
[1, 2, 4, 3, 5, 7, 8, 6, 9] 4
[1, 2, 3, 4, 5, 7, 8, 6, 9] 3
[1, 2, 3, 4, 5, 6, 7, 8, 9] 6
[1, 2, 3, 4, 5, 6, 7, 8, 9]

快速排序的優(yōu)化

①優(yōu)化基準(zhǔn)的選擇

上面的程序選擇的基準(zhǔn)是數(shù)組起始位置，但是跟明顯，我們并沒(méi)有達(dá)到想要的理想結(jié)果將數(shù)組劃分為兩部分，進(jìn)行遞歸操作；

所以就有了三數(shù)取中法來(lái)選取基準(zhǔn)，即取三個(gè)關(guān)鍵字先進(jìn)行排序，將中間數(shù)作為基準(zhǔn)，一般去開始，結(jié)束，和中間；

當(dāng)然也可以隨機(jī)選取；其實(shí)還有一種九數(shù)取中法，這里就不詳細(xì)介紹了，有興趣的可以自己了解一下。

下面是三數(shù)取中法的代碼：

public void medianOfThree(int[] arr, int start, int end){
        int m = start + (end - start) / 2;
        if(arr[start] > arr[end]){
            swap(arr, start, end);
        }
        if(arr[m] > arr[end]){
            swap(arr, end, m);
        }
        if(arr[m] > arr[start]){
            swap(arr, m, start);
        }
    }

②優(yōu)化不必要的交換

首先我們通過(guò)上面的代碼很容易發(fā)現(xiàn)在交換的過(guò)程中，有許多部分是沒(méi)必要交換的，于是我們通過(guò)賦值替代交換來(lái)省去沒(méi)必要的交換；

代碼如下：

public int partition3(int arr[], int start, int end){
        assert(null != arr);
        medianOfThree(arr, start, end);
        int temp = arr[start];
        while(start < end){
            while(temp < arr[end] && start < end){
                end--;
            }
            arr[start] = arr[end];
            while(temp > arr[start] && start < end){
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = temp;
        System.out.println(Arrays.toString(arr) + "   " +  start);
        return start;
    }

③優(yōu)化小數(shù)組時(shí)的排序方案

一般對(duì)于小數(shù)組排序，我們需要選擇插入排序，因?yàn)椴迦肱判蚴呛?jiǎn)單排序性能最高的。所以我們做如下修改：

public void partitionSort4(int arr[], int start, int end){
        assert(null != arr);
        if((end - start) > INSERT_SORT){
            int midd = partition3(arr, start, end);
            partitionSort3(arr, start, midd - 1);
            partitionSort3(arr, midd + 1, end);
        }else{
            insertSort(arr);
        }
    }

其中，INSERT_SORT選擇的大小眾說(shuō)紛紜，自我覺(jué)得在海量數(shù)據(jù)面前，選擇20跟選擇7沒(méi)有太大的差異吧。（這話如果有誤，望大家批評(píng)指正）

④優(yōu)化遞歸操作

我們都知道遞歸的額外花銷還是很大的，減少遞歸可以大大提高性能，故此做如下修改：

 public void partitionSort5(int arr[], int start, int end){
        assert(null != arr);
        int midd;
        if((end - start) > INSERT_SORT){
            while(start < end){
                midd = partition3(arr, start, end);
                partitionSort5(arr, start, midd - 1);
                start = midd + 1;
            }
        }else{
            insertSort(arr);
        }
    }