跳到主要内容

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中的数组排序技术，为更复杂的数据处理打下基础。