Java实现插入排序算法

简介

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是将数组分为已排序和未排序两部分，初始时已排序部分只有一个元素（即数组的第一个元素）。然后，算法从第二个元素开始，将未排序部分的每个元素插入到已排序部分的正确位置。插入排序对于少量数据的排序效率较高，并且在部分有序的数组上表现出色。本文将详细介绍如何使用Java实现插入排序算法，包括基础概念、使用方法、常见实践以及最佳实践。

基础概念

插入排序的基本思想是将数组分为两个子数组：已排序和未排序。在每一步中，从未排序部分选择一个元素，将其插入到已排序部分的正确位置。具体步骤如下：

从第一个元素开始，该元素可以认为已经被排序。
取出下一个元素，在已经排序的元素序列中从后向前扫描。
如果该元素（已排序）大于新元素，将该元素移到下一位置。
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
将新元素插入到该位置后。
重复步骤2~5，直到整个数组被排序。

使用方法

在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;

            // 将已排序部分中大于key的元素向后移动一个位置
            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 + " ");
        }
    }
}

代码解释

insertionSort方法接受一个整数数组arr作为参数。
外层循环for (int i = 1; i < n; i++)从数组的第二个元素开始，逐步处理未排序部分的元素。
内层循环while (j >= 0 && arr[j] > key)从已排序部分的末尾开始向前扫描，将大于key的元素向后移动一个位置。
当找到合适的位置后，将key插入到该位置。

常见实践

对不同类型数据排序

插入排序算法不仅可以用于整数数组，还可以用于其他类型的数据，只要这些数据实现了Comparable接口。例如，对字符串数组进行排序：

public class StringInsertionSort {
    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[] arr = {"banana", "apple", "cherry", "date"};
        System.out.println("原始数组:");
        for (String str : arr) {
            System.out.print(str + " ");
        }

        insertionSort(arr);

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

对自定义对象排序

如果要对自定义对象进行排序，需要让自定义对象实现Comparable接口，并在接口方法中定义比较规则。例如，对一个包含学生信息的类进行排序：

class Student implements Comparable<Student> {
    private String name;
    private int age;

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

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public int compareTo(Student other) {
        return this.age - other.age; // 按年龄升序排序
    }
}

public class StudentInsertionSort {
    public static void insertionSort(Student[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            Student 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) {
        Student[] students = {
            new Student("Alice", 20),
            new Student("Bob", 18),
            new Student("Charlie", 22)
        };

        System.out.println("原始数组:");
        for (Student student : students) {
            System.out.println("Name: " + student.getName() + ", Age: " + student.getAge());
        }

        insertionSort(students);

        System.out.println("\n排序后的数组:");
        for (Student student : students) {
            System.out.println("Name: " + student.getName() + ", Age: " + student.getAge());
        }
    }
}

最佳实践

优化插入排序

对于部分有序的数组，插入排序的性能较好。为了进一步提高插入排序的效率，可以采用二分查找来确定插入位置，而不是线性扫描。这种优化后的算法称为二分插入排序（Binary Insertion Sort）。

public class BinaryInsertionSort {
    public static void binaryInsertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int left = 0, right = i - 1;

            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (arr[mid] < key) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            // 将元素向后移动，为插入key腾出位置
            for (int j = i - 1; j >= left; j--) {
                arr[j + 1] = arr[j];
            }
            arr[left] = 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 + " ");
        }

        binaryInsertionSort(arr);

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

适用于小数据量

插入排序在数据量较小时性能较好，通常在数据量小于某个阈值（如16）时，可以直接使用插入排序。在实现更复杂的排序算法（如归并排序、快速排序）时，可以将插入排序作为子算法来处理小数组，以提高整体性能。

小结

插入排序是一种简单且直观的排序算法，适用于少量数据或部分有序的数据。通过将数组分为已排序和未排序两部分，并逐步将未排序部分的元素插入到已排序部分的正确位置，实现数组的排序。在Java中实现插入排序算法时，可以根据不同的数据类型和需求进行适当的扩展和优化。同时，了解插入排序的最佳实践，如二分插入排序和与其他排序算法结合使用，可以进一步提高排序效率。

参考资料

《算法导论》（Introduction to Algorithms）
维基百科 - 插入排序
Oracle Java教程