总结——Java中sort函数的使用方法_java sort函数

JAVA中sort函数的使用方法

Arrays.sort() 方法按照策略实现了归并插入排序和优化后的快排，比普通快排更快!!!

在编程练习中，我们会经常用到排序，相比C和C++，使用Java提供的排序方法会更快捷，Java的Arrays类中有一个sort()方法，该方法是Arrays类的静态方法，在需要对数组进行排序时，非常的好用。

1、Arrays.sort(int[] a)

作用：对一个数组的所有元素进行排序，并且是按从小到大的顺序（从小到大排序）。

Leedcode题目：977.有序数组的平方

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

示例 2：

输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。

通过代码：（使用Java提供的Sort()方法，代码简洁，实现简单）

class Solution {
    public int[] sortedSquares(int[] A) {
        for(int i = 0; i < A.length; i++) {
            A[i] = A[i] * A[i];
        }
        Arrays.sort(A);
        return A;
    }
}
1
2
3
4
5
6
7
8
9

官方解决方案

方法一：排序

思路与算法

创建一个新的数组，它每个元素是给定数组对应位置元素的平方，然后排序这个数组。
Java

class Solution {
    public int[] sortedSquares(int[] A) {
        int N = A.length;
        int[] ans = new int[N];
        for (int i = 0; i < N; ++i)
            ans[i] = A[i] * A[i];

        Arrays.sort(ans);
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11

Python

class Solution(object):
    def sortedSquares(self, A):
        return sorted(x*x for x in A)
1
2
3

复杂度分析

• 时间复杂度：O(N log N)，其中 N 是数组 A 的长度。

• 空间复杂度：O(N)。

方法二：双指针

思路

因为数组 A 已经排好序了， 所以可以说数组中的负数已经按照平方值降序排好了，数组中的非负数已经按照平方值升序排好了。

举一个例子，若给定数组为 [-3, -2, -1, 4, 5, 6]，数组中负数部分 [-3, -2, -1] 的平方为 [9, 4, 1]，数组中非负部分 [4, 5, 6] 的平方为 [16, 25, 36]。我们的策略就是从前向后遍历数组中的非负数部分，并且反向遍历数组中的负数部分。

算法

我们可以使用两个指针分别读取数组的非负部分与负数部分 —— 指针 i 反向读取负数部分，指针 j 正向读取非负数部分。

那么，现在我们就在使用两个指针分别读取两个递增的数组了（按元素的平方排序）。接下来，我们可以使用双指针的技巧合并这两个数组。

Java

class Solution {
    public int[] sortedSquares(int[] A) {
        int N = A.length;
        int j = 0;
        while (j < N && A[j] < 0)
            j++;
        int i = j-1;

        int[] ans = new int[N];
        int t = 0;

        while (i >= 0 && j < N) {
            if (A[i] * A[i] < A[j] * A[j]) {
                ans[t++] = A[i] * A[i];
                i--;
            } else {
                ans[t++] = A[j] * A[j];
                j++;
            }
        }

        while (i >= 0) {
            ans[t++] = A[i] * A[i];
            i--;
        }
        while (j < N) {
            ans[t++] = A[j] * A[j];
            j++;
        }

        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

Python

class Solution(object):
    def sortedSquares(self, A):
        N = len(A)
        # i, j: negative, positive parts
        j = 0
        while j < N and A[j] < 0:
            j += 1
        i = j - 1

        ans = []
        while 0 <= i and j < N:
            if A[i]**2 < A[j]**2:
                ans.append(A[i]**2)
                i -= 1
            else:
                ans.append(A[j]**2)
                j += 1

        while i >= 0:
            ans.append(A[i]**2)
            i -= 1
        while j < N:
            ans.append(A[j]**2)
            j += 1

        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

复杂度分析

• 时间复杂度：O(N)，其中 N 是数组 A 的长度。
• 空间复杂度：O(N)。

2、Arrays.sort(int[] a, int fromIndex, int toIndex)

对数组中的部分元素进行排序（从小到大排序），即下标从fromIndex到toIndex-1的元素进行排序

public class Test{
    public static void main(String[] args) {

        int[] a = {9, 8, 7, 2, 3, 4, 1, 0, 6, 5};
        Arrays.sort(a, 0, 3);
        for(int i = 0; i < a.length; i ++) {
            System.out.print(a[i] + " ");
        }
    }
}

//运行结果如下：
//7 8 9 2 3 4 1 0 6 5 （只是把 9 8 7排列成了7 8 9）
1
2
3
4
5
6
7
8
9
10
11
12
13

3、public static void sort(T[] a,int fromIndex, int toIndex, Comparator<? super T> c)

可以实现从大到小排序
这里需要了解Java泛型和comparator接口

import java.util.Comparator;

public class Test{
    public static void main(String[] args) {
        //注意，要想改变默认的排列顺序，不能使用基本类型（int,double, char）
        //而要使用它们对应的包装类
        Integer[] a = {9, 8, 7, 2, 3, 4, 1, 0, 6, 5};
        //定义一个自定义类MyComparator的对象
        Comparator cmp = new MyComparator();
        Arrays.sort(a, cmp);
        for(int i = 0; i < a.length; i ++) {
            System.out.print(a[i] + " ");
        }
    }
}


//Comparator是一个接口，所以这里我们自己定义的类MyComparator要implents该接口，而不是extends Comparator

class MyComparator implements Comparator<Integer>{
    @Override
    public int compare(Integer o1, Integer o2) {
        //如果n1小于n2，我们就返回正值，如果n1大于n2我们就返回负值，
        //这样颠倒一下，就可以实现反向排序了
        if(o1 < o2) { 
            return 1;
        }else if(o1 > o2) {
            return -1;
        }else {
            return 0;
        }
    }
}

//运行结果如下：
//9 8 7 6 5 4 3 2 1 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

参考文章链接：https://blog.csdn.net/eff666/article/details/63692840