跳到主要内容

Java 数组排序

在Java编程中,数组排序是一项基础且常用的操作。无论是处理用户数据、搜索信息还是执行各种算法,排序都扮演着重要角色。本文将详细介绍Java中对数组进行排序的多种方法,包括使用内置方法和实现自定义排序算法。

为什么需要学习数组排序?

排序是计算机科学中的基本操作,它允许我们以有序方式组织数据,从而使搜索和处理数据变得更加高效。在实际应用中,排序的场景非常常见:

  • 学生成绩排名
  • 商品价格从低到高展示
  • 姓名按字母顺序排列
  • 日期时间的先后顺序排序

Java 内置排序方法

Java提供了多种内置方法来对数组进行排序,这些方法简单易用且高效。

Arrays.sort() 方法

Arrays.sort() 是Java中最常用的数组排序方法,它位于java.util.Arrays包中。

基本类型数组排序

java
import java.util.Arrays;

public class BasicArraySorting {
public static void main(String[] args) {
// 整数数组排序
int[] numbers = {5, 2, 9, 1, 3, 6};

System.out.println("排序前:");
for (int num : numbers) {
System.out.print(num + " ");
}

// 对数组进行排序
Arrays.sort(numbers);

System.out.println("\n排序后:");
for (int num : numbers) {
System.out.print(num + " ");
}
}
}

输出结果:

排序前:
5 2 9 1 3 6
排序后:
1 2 3 5 6 9

字符串数组排序

java
import java.util.Arrays;

public class StringArraySorting {
public static void main(String[] args) {
// 字符串数组排序
String[] names = {"Tom", "Alice", "Bob", "John", "Mary"};

System.out.println("排序前:");
for (String name : names) {
System.out.print(name + " ");
}

// 对字符串数组进行排序 (按字母顺序)
Arrays.sort(names);

System.out.println("\n排序后:");
for (String name : names) {
System.out.print(name + " ");
}
}
}

输出结果:

排序前:
Tom Alice Bob John Mary
排序后:
Alice Bob John Mary Tom

部分数组排序

我们也可以只对数组的一部分进行排序:

java
import java.util.Arrays;

public class PartialArraySorting {
public static void main(String[] args) {
int[] numbers = {5, 2, 9, 1, 3, 6};

System.out.println("排序前:");
for (int num : numbers) {
System.out.print(num + " ");
}

// 只对索引1到4的元素进行排序
Arrays.sort(numbers, 1, 5);

System.out.println("\n部分排序后:");
for (int num : numbers) {
System.out.print(num + " ");
}
}
}

输出结果:

排序前:
5 2 9 1 3 6
部分排序后:
5 1 2 3 9 6
备注

Arrays.sort(array, fromIndex, toIndex) 方法会对数组从 fromIndex(包括)到 toIndex(不包括)之间的元素进行排序。

自定义排序顺序

使用 Comparator 排序对象数组

当我们需要对包含对象的数组进行排序时,我们可以使用 Comparator 接口定义排序规则。

java
import java.util.Arrays;
import java.util.Comparator;

public class CustomObjectSorting {
public static void main(String[] args) {
// 创建学生对象数组
Student[] students = {
new Student("张三", 85),
new Student("李四", 92),
new Student("王五", 78),
new Student("赵六", 88)
};

System.out.println("按成绩排序前:");
for (Student s : students) {
System.out.println(s);
}

// 使用Comparator按成绩从高到低排序
Arrays.sort(students, new Comparator<Student>() {
@Override
public int compare(Student s1, Student s2) {
return s2.getScore() - s1.getScore();
}
});

System.out.println("\n按成绩从高到低排序后:");
for (Student s : students) {
System.out.println(s);
}

// 使用Lambda表达式按姓名字母顺序排序
Arrays.sort(students, (s1, s2) -> s1.getName().compareTo(s2.getName()));

System.out.println("\n按姓名字母顺序排序后:");
for (Student s : students) {
System.out.println(s);
}
}

// 学生类
static class Student {
private String name;
private int score;

public Student(String name, int score) {
this.name = name;
this.score = score;
}

public String getName() {
return name;
}

public int getScore() {
return score;
}

@Override
public String toString() {
return "Student{" + "name='" + name + "', score=" + score + '}';
}
}
}

输出结果:

按成绩排序前:
Student{name='张三', score=85}
Student{name='李四', score=92}
Student{name='王五', score=78}
Student{name='赵六', score=88}

按成绩从高到低排序后:
Student{name='李四', score=92}
Student{name='赵六', score=88}
Student{name='张三', score=85}
Student{name='王五', score=78}

按姓名字母顺序排序后:
Student{name='李四', score=92}
Student{name='王五', score=78}
Student{name='张三', score=85}
Student{name='赵六', score=88}

常见排序算法实现

除了使用Java内置的排序方法外,了解一些基本排序算法的原理和实现也很重要,这有助于加深对排序过程的理解。

冒泡排序

冒泡排序是最简单的排序算法之一,通过重复比较相邻的元素并在需要时交换它们来完成排序。

java
public class BubbleSort {
public static void main(String[] args) {
int[] array = {64, 34, 25, 12, 22, 11, 90};

System.out.println("排序前:");
printArray(array);

bubbleSort(array);

System.out.println("\n排序后:");
printArray(array);
}

// 冒泡排序实现
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换 arr[j] 和 arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

// 打印数组
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
}

输出结果:

排序前:
64 34 25 12 22 11 90
排序后:
11 12 22 25 34 64 90
提示

冒泡排序的时间复杂度为O(n²),不适用于大规模数据排序,但其原理简单易懂,适合初学者学习。

选择排序

选择排序的工作原理是在未排序的部分中找到最小元素,并将其与未排序部分的第一个元素交换位置。

java
public class SelectionSort {
public static void main(String[] args) {
int[] array = {64, 25, 12, 22, 11};

System.out.println("排序前:");
printArray(array);

selectionSort(array);

System.out.println("\n排序后:");
printArray(array);
}

// 选择排序实现
public static void selectionSort(int[] arr) {
int n = arr.length;

for (int i = 0; i < n - 1; i++) {
// 找到未排序部分的最小元素
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}

// 将最小元素与未排序部分的第一个元素交换
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}

// 打印数组
public static void printArray(int[] arr) {
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
}

输出结果:

排序前:
64 25 12 22 11
排序后:
11 12 22 25 64

排序算法的性能比较

不同的排序算法在不同情况下性能表现也不相同。以下是常见排序算法的性能比较:

警告

Java内置的 Arrays.sort() 方法为基本类型使用双轴快速排序(Dual-Pivot Quicksort)算法,而对于对象数组则使用改进的归并排序(TimSort)。在大多数情况下,内置排序方法的性能比自己实现的更好。

实际应用案例

案例1:学生成绩管理系统

java
import java.util.Arrays;
import java.util.Scanner;

public class StudentGradeSystem {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

System.out.print("请输入学生人数: ");
int n = scanner.nextInt();

String[] names = new String[n];
int[] scores = new int[n];

// 输入学生信息
for (int i = 0; i < n; i++) {
System.out.print("请输入第" + (i + 1) + "个学生的姓名: ");
names[i] = scanner.next();

System.out.print("请输入第" + (i + 1) + "个学生的成绩: ");
scores[i] = scanner.nextInt();
}

// 创建学生对象数组
Student[] students = new Student[n];
for (int i = 0; i < n; i++) {
students[i] = new Student(names[i], scores[i]);
}

// 按成绩从高到低排序
Arrays.sort(students, (s1, s2) -> s2.getScore() - s1.getScore());

// 显示排序后的结果
System.out.println("\n成绩排名:");
System.out.println("排名\t姓名\t成绩");
for (int i = 0; i < n; i++) {
System.out.println((i + 1) + "\t" + students[i].getName() + "\t" + students[i].getScore());
}

scanner.close();
}

static class Student {
private String name;
private int score;

public Student(String name, int score) {
this.name = name;
this.score = score;
}

public String getName() {
return name;
}

public int getScore() {
return score;
}
}
}

示例输入和输出:

请输入学生人数: 3
请输入第1个学生的姓名: 张三
请输入第1个学生的成绩: 85
请输入第2个学生的姓名: 李四
请输入第2个学生的成绩: 92
请输入第3个学生的姓名: 王五
请输入第3个学生的成绩: 78

成绩排名:
排名 姓名 成绩
1 李四 92
2 张三 85
3 王五 78

案例2:商品价格排序

java
import java.util.Arrays;
import java.util.Scanner;

public class ProductSorting {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);

System.out.print("请输入商品数量: ");
int n = scanner.nextInt();

Product[] products = new Product[n];

// 输入商品信息
for (int i = 0; i < n; i++) {
System.out.print("请输入第" + (i + 1) + "个商品的名称: ");
String name = scanner.next();

System.out.print("请输入第" + (i + 1) + "个商品的价格: ");
double price = scanner.nextDouble();

products[i] = new Product(name, price);
}

// 按价格从低到高排序
Arrays.sort(products, (p1, p2) -> Double.compare(p1.getPrice(), p2.getPrice()));

System.out.println("\n商品价格从低到高排序:");
for (Product p : products) {
System.out.printf("%s - ¥%.2f\n", p.getName(), p.getPrice());
}

// 按价格从高到低排序
Arrays.sort(products, (p1, p2) -> Double.compare(p2.getPrice(), p1.getPrice()));

System.out.println("\n商品价格从高到低排序:");
for (Product p : products) {
System.out.printf("%s - ¥%.2f\n", p.getName(), p.getPrice());
}

scanner.close();
}

static class Product {
private String name;
private double price;

public Product(String name, double price) {
this.name = name;
this.price = price;
}

public String getName() {
return name;
}

public double getPrice() {
return price;
}
}
}

示例输入和输出:

请输入商品数量: 4
请输入第1个商品的名称: 手机
请输入第1个商品的价格: 2999.99
请输入第2个商品的名称: 电脑
请输入第2个商品的价格: 5999.00
请输入第3个商品的名称: 耳机
请输入第3个商品的价格: 299.50
请输入第4个商品的名称: 键盘
请输入第4个商品的价格: 499.00

商品价格从低到高排序:
耳机 - ¥299.50
键盘 - ¥499.00
手机 - ¥2999.99
电脑 - ¥5999.00

商品价格从高到低排序:
电脑 - ¥5999.00
手机 - ¥2999.99
键盘 - ¥499.00
耳机 - ¥299.50

总结

Java数组排序是编程中的基础操作,掌握它能让我们更高效地处理数据。我们学习了以下内容:

  1. 使用Java内置的 Arrays.sort() 方法排序基本类型和对象数组
  2. 使用 Comparator 接口实现自定义排序
  3. 常见排序算法的实现(冒泡排序、选择排序)
  4. 排序算法的性能比较
  5. 实际应用案例

随着你编程技能的提高,你会发现排序在数据处理中的重要性。尽管在大多数情况下使用内置的排序方法就足够了,但了解排序算法的原理对于理解计算机科学的基础概念非常有帮助。

练习

  1. 实现一个程序,让用户输入一组整数,然后按照升序和降序分别输出排序结果。
  2. 创建一个"日期排序器",能够按照日期的先后顺序对多个日期进行排序。
  3. 实现插入排序算法,并与Arrays.sort()方法比较性能差异。
  4. 编写一个程序,对字符串数组按照字符串长度进行排序。
  5. 创建一个电影类,包含电影名称、上映年份和评分属性,然后实现按评分、按上映年份和按名称字母顺序三种不同的排序方式。

通过这些练习,你将更加熟悉Java中的数组排序技术,为更复杂的数据处理打下基础。