极客教程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中编写我自己的排序函数？