Java数据结构与算法：排序算法之插入排序

Java数据结构与算法：排序算法之插入排序

大家好，我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编，寒冬来袭，虽然冷空气刺骨，但我们程序猿依然保持风度。今天，我们将探讨Java中另一种引人注目的排序算法——插入排序。这种简单而高效的排序算法有着独特的魅力，让我们一同揭开它的神秘面纱。

插入排序简介

插入排序是一种基础的比较排序算法，其核心思想是将待排序的序列分为两部分，一部分是已排序的，另一部分是未排序的。在未排序部分选择一个元素，插入到已排序部分的适当位置，以此类推，直到所有元素都被排序完毕。插入排序的实现简单直观，是初学者入门排序算法的绝佳选择。

插入排序的基本步骤

1. 初始状态： 将整个待排序的序列分为已排序部分和未排序部分。初始时，已排序部分只包含第一个元素，未排序部分包含其余所有元素。

2. 插入元素： 从未排序部分选择一个元素，插入到已排序部分的适当位置。插入的方式是从右向左比较，找到合适的位置插入。

3. 扩大已排序部分： 将刚刚插入的元素视为已排序部分的一部分，未排序部分减少一个元素。

4. 重复步骤2和3： 重复以上步骤，直到未排序部分为空，排序完成。

插入排序Java实现

下面是一个简单的Java代码示例，演示了如何使用插入排序对一个整型数组进行升序排序：

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

        // 打印排序前的数组
        System.out.println("排序前的数组：" + Arrays.toString(array));

        // 执行插入排序
        insertionSort(array);

        // 打印排序后的数组
        System.out.println("排序后的数组：" + Arrays.toString(array));
    }

    // 插入排序算法实现
    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;
        }
    }
}

插入排序的时间复杂度

插入排序的平均时间复杂度为O(n^2)，效率相对较高。尤其在数据集近乎有序的情况下，插入排序的表现更为出色。虽然在大规模数据集上可能不如一些高级排序算法，但插入排序在实际应用中仍有广泛的使用。

通过这篇文章，相信你对插入排序有了更深入的理解。在接下来的系列中，我们将一起学习更多Java中的排序算法，为你呈现更多有趣的内容。敬请期待！