Java 排序

每当我们听到排序算法出现时，如选择排序、冒泡排序、插入排序、弧度排序、桶状排序等，但如果我们仔细观察，这里没有要求我们使用任何一种算法。它是借助java中的线性和非线性数据结构进行的简单排序。因此，在Java中，我们可以在循环的帮助下用蛮力进行排序，并且有两种内置的方法来进行排序。

在Java中进行排序的方法

使用循环
使用数组类的sort()方法
使用集合类的sort方法
对子数组进行排序

让我们讨论一下这四种方法，并为每一种方法提出一个代码。

方法1： 使用循环

// Java Program to sort an elements
// by bringing Arrays into play
 
// Main class
class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
 
        // Custom input array
        int arr[] = { 4, 3, 2, 1 };
 
        // Outer loop
        for (int i = 0; i < arr.length; i++) {
 
            // Inner nested loop pointing 1 index ahead
            for (int j = i + 1; j < arr.length; j++) {
 
                // Checking elements
                int temp = 0;
                if (arr[j] < arr[i]) {
 
                    // Swapping
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
 
            // Printing sorted array elements
            System.out.print(arr[i] + " ");
        }
    }
}

输出

1 2 3 4

时间复杂度： O(N2 )

辅助空间： O(1)

方法2： 使用Arrays类的sort()方法

Arrays.Sort()方法适用于原始数据类型的数组，默认为升序排序。

例子1

// Java program to demonstrate working of
// sort() method of Arrays class
 
// Importing Arrays class from java.util package
import java.util.Arrays;
 
// Main class
public class GFG {
 
    // Main driver method
    public static void main(String[] args)
    {
        // Custom input array
        int[] arr = { 13, 7, 6, 45, 21, 9, 101, 102 };
 
        // Calling the sort() method present
        // inside Arrays class
        Arrays.sort(arr);
 
        // Printing and display sorted array
        System.out.printf("Modified arr[] : %s",
                          Arrays.toString(arr));
    }
}

输出

Modified arr[] : [6, 7, 9, 13, 21, 45, 101, 102]

时间复杂度： O(N log N)

辅助空间： O(1)

例子2

// A sample Java program to sort an array
// in descending order using Arrays.sort().
import java.util.Arrays;
import java.util.Collections;
 
public class GFG {
    public static void main(String[] args)
    {
        // Note that we have Integer here instead of
        // int[] as Collections.reverseOrder doesn't
        // work for primitive types.
        Integer[] arr = { 13, 7, 6, 45, 21, 9, 2, 100 };
 
        // Sorts arr[] in descending order
        Arrays.sort(arr, Collections.reverseOrder());
 
        System.out.printf("Modified arr[] : %s",
                          Arrays.toString(arr));
    }
}

输出

Modified arr[] : [100, 45, 21, 13, 9, 7, 6, 2]

时间复杂度： O(N log N)

辅助空间： O(1)

方法3： 使用集合类的sort()方法

Collections.sort()适用于对象集合，如ArrayList和LinkedList。

例子

// Java program to demonstrate working of Collections.sort()
import java.util.*;
 
public class GFG {
    public static void main(String[] args)
    {
        // Create a list of strings
        ArrayList<String> al = new ArrayList<String>();
        al.add("Geeks For Geeks");
        al.add("Friends");
        al.add("Dear");
        al.add("Is");
        al.add("Superb");
 
        /* Collections.sort method is sorting the
        elements of ArrayList in ascending order. */
        Collections.sort(al);
 
        // Let us print the sorted list
        System.out.println("List after the use of"
                           + " Collection.sort() :\n" + al);
    }
}

输出

List after the use of Collection.sort() :
[Dear, Friends, Geeks For Geeks, Is, Superb]

时间复杂度： O(N log N)

辅助空间： O(1)

例2

// Java program to demonstrate working of Collections.sort()
// to descending order.
import java.util.*;
 
public class GFG {
    public static void main(String[] args)
    {
        // Create a list of strings
        ArrayList<String> al = new ArrayList<String>();
        al.add("Geeks For Geeks");
        al.add("Friends");
        al.add("Dear");
        al.add("Is");
        al.add("Superb");
 
        /* Collections.sort method is sorting the
        elements of ArrayList in ascending order. */
        Collections.sort(al, Collections.reverseOrder());
 
        // Let us print the sorted list
        System.out.println("List after the use of"
                           + " Collection.sort() :\n" + al);
    }
}

输出

List after the use of Collection.sort() :
[Superb, Is, Geeks For Geeks, Friends, Dear]

时间复杂度： O(N log N)

辅助空间： O(1)

方法4： 只对一个子数进行排序

// Java program to sort a subarray
// using Arrays.sort()
 
// Importing Arrays class from java.util package
import java.util.Arrays;
 
// Main class
public class GFG {
 
    // Main drive method
    public static void main(String[] args)
    {
        // Custom input array
        int[] arr = { 13, 7, 6, 45, 21, 9, 2, 100 };
 
        // Sort subarray from index 1 to 4, i.e.,
        // only sort subarray {7, 6, 45, 21} and
        // keep other elements as it is.
        Arrays.sort(arr, 1, 5);
 
        // Printing sorted array
        System.out.printf("Modified arr[] : %s",
                          Arrays.toString(arr));
    }
}

输出

Modified arr[] : [13, 6, 7, 21, 45, 9, 2, 100]

时间复杂度： O(N log N)

辅助空间： O(1)

注意

Java在sort()中使用哪种排序算法？
以前，Java的Arrays.sort方法对基元数组使用Quicksort，对对象数组使用Merge排序。在Java的最新版本中，Arrays.sort方法和Collection.sort()使用Timsort。
默认情况下是按升序排序的。
如何对数组或列表进行降序排序？

可以在Collections.reverseOrder()的帮助下完成。
如何在Java中编写我自己的排序函数？