Java 插入排序算法
最后修改时间：2025 年 4 月 16 日
排序算法简介
算法是解决问题或执行计算的逐步过程。 排序算法以特定顺序（通常是数值或词典顺序）排列列表的元素。 有效的排序对于优化其他算法非常重要。
常见的排序算法包括
- 插入排序
- 气泡排序
- 选择排序
- 归并排序
- 快速排序
- 堆排序
插入排序概述
插入排序是一种简单的排序算法，它一次构建一个最终排序的数组。 它对于小型数据集或几乎排序的数据集是有效的。 该算法的工作方式类似于您在手中整理扑克牌的方式。
插入排序在最坏和平均情况下具有 O(n²) 的时间复杂度，但在最佳情况下（当输入已排序时）具有 O(n) 的时间复杂度。 它是稳定的（不改变相等元素的相对顺序）并且是原地排序（只需要 O(1) 的额外空间）。
基本插入排序实现
这是整数升序插入排序的基本实现
InsertionSort.java
package com.zetcode;
public class InsertionSort {
public static void sort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements greater than key to one position ahead
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[] data = {12, 11, 13, 5, 6};
System.out.println("Unsorted array:");
printArray(data);
sort(data);
System.out.println("Sorted array (ascending):");
printArray(data);
}
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
此实现按升序对整数数组进行排序。 该算法迭代数组，将每个元素与之前的元素进行比较，并将其插入到正确的位置。 `printArray` 方法显示数组。
降序排序
要按降序排序，我们只需修改 while 循环中的比较
InsertionSortDesc.java
package com.zetcode;
public class InsertionSortDesc {
public static void sortDesc(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Move elements smaller than key to one position ahead
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[] data = {12, 11, 13, 5, 6};
System.out.println("Unsorted array:");
printArray(data);
sortDesc(data);
System.out.println("Sorted array (descending):");
printArray(data);
}
private static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}
唯一的更改是 while 循环条件中的比较运算符，从 > 更改为 <。 这使得算法按降序而不是升序排序。
使用插入排序对字符串进行排序
插入排序也可以对文本数据进行排序。 这是按升序对字符串进行排序的实现
StringInsertionSort.java
package com.zetcode;
public class StringInsertionSort {
public static void sortStrings(String[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
String key = arr[i];
int j = i - 1;
// Compare strings lexicographically
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[] names = {"John", "Alice", "Bob", "Eve", "David"};
System.out.println("Unsorted names:");
printArray(names);
sortStrings(names);
System.out.println("Sorted names (ascending):");
printArray(names);
}
private static void printArray(String[] arr) {
for (String str : arr) {
System.out.print(str + " ");
}
System.out.println();
}
}
此版本使用 String 类的 compareTo 方法来确定元素的顺序。 该算法的工作方式与数字相同，但按字典顺序比较字符串。
泛型插入排序实现
我们可以使用 Java 泛型创建一个更灵活的实现，它可以处理任何 Comparable 类型
GenericInsertionSort.java
package com.zetcode;
public class GenericInsertionSort {
public static <T extends Comparable<T>> void sort(T[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
T 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) {
// Sorting integers
Integer[] numbers = {12, 11, 13, 5, 6};
System.out.println("Unsorted numbers:");
printArray(numbers);
sort(numbers);
System.out.println("Sorted numbers:");
printArray(numbers);
// Sorting strings
String[] names = {"John", "Alice", "Bob", "Eve", "David"};
System.out.println("\nUnsorted names:");
printArray(names);
sort(names);
System.out.println("Sorted names:");
printArray(names);
}
private static <T> void printArray(T[] arr) {
for (T element : arr) {
System.out.print(element + " ");
}
System.out.println();
}
}
此泛型实现可以对任何实现 Comparable 接口的对象数组进行排序。 它展示了 Java 泛型的灵活性，同时保持了类型安全。
插入排序与快速排序基准测试
虽然插入排序很简单，但对于大型数据集来说，它并不是最有效的。 让我们将其与快速排序进行比较，快速排序具有更好的平均性能（O(n log n) 与 O(n²)）
SortBenchmark.java
package com.zetcode;
import java.util.Random;
public class SortBenchmark {
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 quickSort(int[] arr, int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] smallArray = generateRandomArray(100);
int[] mediumArray = generateRandomArray(1_000);
int[] largeArray = generateRandomArray(10_000);
benchmarkSort("Insertion Sort (100)", smallArray.clone());
benchmarkSort("QuickSort (100)", smallArray.clone());
benchmarkSort("Insertion Sort (1,000)", mediumArray.clone());
benchmarkSort("QuickSort (1,000)", mediumArray.clone());
benchmarkSort("Insertion Sort (10,000)", largeArray.clone());
benchmarkSort("QuickSort (10,000)", largeArray.clone());
}
private static void benchmarkSort(String name, int[] arr) {
long startTime = System.nanoTime();
if (name.startsWith("Insertion")) {
insertionSort(arr);
} else {
quickSort(arr, 0, arr.length - 1);
}
long endTime = System.nanoTime();
long duration = (endTime - startTime) / 1_000_000; // milliseconds
System.out.printf("%s: %d ms%n", name, duration);
}
private static int[] generateRandomArray(int size) {
Random random = new Random();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = random.nextInt(10_000);
}
return arr;
}
}
此基准测试比较了插入排序和快速排序在不同大小的数组上的性能。 结果通常表明
- 对于小型数组（100 个元素），插入排序可能具有可比性或更快
- 对于中型数组（1,000 个元素），快速排序开始显示优势
- 对于大型数组（10,000+ 个元素），快速排序明显更快
何时使用插入排序
尽管插入排序具有 O(n²) 的复杂度，但它有一些优点使其在特定情况下有用
- 当数据几乎排序时（最佳情况 O(n) 性能）
- 对于小型数据集，其简单性超过了性能方面的考虑
- 当内存受到限制时（它是一种原地排序算法）
- 作为更高级算法的一部分（例如，Timsort 使用它进行小范围运行）
来源
在本教程中，我们介绍了 Java 中的插入排序算法，包括针对不同数据类型和排序的实现。 我们还将它的性能与快速排序进行了比较，以了解何时使用哪种算法是合适的。
作者
列出所有Java教程。