跳转至

Java 插入排序代码解析

简介

插入排序（Insertion Sort）是一种简单直观的排序算法，特别适用于少量数据的排序。它的工作原理是将未排序数据插入到已排序序列的合适位置。在 Java 编程中，掌握插入排序算法的代码实现对于理解排序算法的基本原理以及提升算法设计能力都非常有帮助。本文将深入探讨 Java 中插入排序代码的相关知识，包括基础概念、使用方法、常见实践以及最佳实践。

目录

  1. 插入排序基础概念
  2. Java 中插入排序的使用方法
  3. 常见实践示例
  4. 最佳实践建议
  5. 小结
  6. 参考资料

插入排序基础概念

插入排序就像人们整理扑克牌一样。假设有一副未排序的扑克牌，我们每次从这副牌中拿出一张牌，然后将它插入到已经整理好的那部分牌中的合适位置。在计算机术语中，数组被分为两个部分：已排序部分和未排序部分。一开始，已排序部分只有数组的第一个元素，其余元素都在未排序部分。然后，依次从未排序部分取出元素，将其插入到已排序部分的正确位置，直到整个数组都被排序。

Java 中插入排序的使用方法

以下是 Java 实现插入排序的基本代码示例：

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        System.out.println("排序前数组:");
        for (int num : arr) {
            System.out.print(num + " ");
        }

        insertionSort(arr);

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

代码解析

  1. 外层循环：从数组的第二个元素开始（索引为 1），依次遍历整个未排序部分。每次循环，将当前元素作为 key。
  2. 内层循环：从 key 的前一个元素开始，向前遍历已排序部分。如果当前已排序元素大于 key，则将该元素向后移动一位。
  3. 插入 key：当内层循环结束时，找到 key 应该插入的位置，将 key 插入到该位置。

常见实践示例

对自定义对象数组排序

假设我们有一个 Person 类，包含 age 属性，我们想要按照年龄对 Person 对象数组进行排序。

class Person {
    private int age;
    private String name;

    public Person(int age, String name) {
        this.age = age;
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "age=" + age +
                ", name='" + name + '\'' +
                '}';
    }
}

public class InsertionSortCustomObject {
    public static void insertionSort(Person[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            Person key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j].getAge() > key.getAge()) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        Person[] people = {
                new Person(25, "Alice"),
                new Person(20, "Bob"),
                new Person(30, "Charlie")
        };

        System.out.println("排序前数组:");
        for (Person person : people) {
            System.out.println(person);
        }

        insertionSort(people);

        System.out.println("排序后数组:");
        for (Person person : people) {
            System.out.println(person);
        }
    }
}

对字符串数组按字典序排序

public class InsertionSortString {
    public static void insertionSort(String[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            String key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j].compareTo(key) > 0) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        String[] strings = {"banana", "apple", "cherry"};

        System.out.println("排序前数组:");
        for (String str : strings) {
            System.out.print(str + " ");
        }

        insertionSort(strings);

        System.out.println("\n排序后数组:");
        for (String str : strings) {
            System.out.print(str + " ");
        }
    }
}

最佳实践建议

  1. 适用于小规模数据：插入排序在数据规模较小时性能较好，因为它的常数因子较小。如果数据量非常大，建议使用更高效的排序算法，如快速排序或归并排序。
  2. 部分有序数据：如果数据已经部分有序，插入排序的性能会显著提升。因为在这种情况下，内层循环的比较和移动操作会减少。
  3. 稳定性：插入排序是稳定的排序算法，这意味着相等元素的相对顺序在排序前后保持不变。在需要保持元素相对顺序的场景中，插入排序是一个不错的选择。

小结

本文详细介绍了 Java 中插入排序的基础概念、使用方法、常见实践以及最佳实践。插入排序作为一种简单而直观的排序算法，在小规模数据和部分有序数据的排序场景中具有一定的优势。通过理解和实践插入排序的代码实现，读者可以更好地掌握排序算法的基本原理，并在实际编程中灵活运用。

参考资料

  1. 《算法导论》（Introduction to Algorithms）