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

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

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

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

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

可以使用下面的方法來實現(xiàn)

1.手動實現(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()用的是快速排序算法。相信大家對于這個都是了解的。

算法的思想

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

算法內(nèi)容描述

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

代碼如下：

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)化基準的選擇

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

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

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

下面是三數(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)化不必要的交換

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

代碼如下：

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ù)組排序，我們需要選擇插入排序，因為插入排序是簡單排序性能最高的。所以我們做如下修改：

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選擇的大小眾說紛紜，自我覺得在海量數(shù)據(jù)面前，選擇20跟選擇7沒有太大的差異吧。（這話如果有誤，望大家批評指正）

④優(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);
        }
    }