Java中怎么实现插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序的基本思想

插入排序的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。具体步骤如下：

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤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;

            // 将arr[0..i-1]中大于key的元素向后移动
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; ++i) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

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

        insertionSort(arr);

        System.out.println("排序后的数组:");
        printArray(arr);
    }
}

代码解析

1. insertionSort方法：这是插入排序的核心方法。它接受一个整数数组作为参数，并对数组进行排序。

   • int n = arr.length; 获取数组的长度。
   • for (int i = 1; i < n; ++i) 从第二个元素开始遍历数组。
   • int key = arr[i]; 将当前元素存储在key中。
   • int j = i - 1; 初始化j为当前元素的前一个位置。
   • while (j >= 0 && arr[j] > key) 在已排序的部分中从后向前扫描，找到合适的位置插入key。
   • arr[j + 1] = arr[j]; 将大于key的元素向后移动。
   • j = j - 1; 继续向前扫描。
   • arr[j + 1] = key; 将key插入到正确的位置。

2. printArray方法：用于打印数组的内容。

3. main方法：程序的入口，创建一个数组并调用insertionSort方法进行排序，然后打印排序前后的数组。

运行结果

运行上述代码，输出结果如下：

排序前的数组:
12 11 13 5 6 
排序后的数组:
5 6 11 12 13 

插入排序的时间复杂度

• 最坏情况：当输入数组是逆序时，插入排序需要进行O(n^2)次比较和交换。
• 最好情况：当输入数组已经是有序时，插入排序只需要进行O(n)次比较。
• 平均情况：插入排序的时间复杂度为O(n^2)。

总结

插入排序是一种简单且易于实现的排序算法，适用于小规模数据的排序。尽管它的时间复杂度较高，但在某些特定情况下（如数据基本有序时），插入排序的性能可能会优于其他更复杂的排序算法。通过理解插入排序的基本思想和实现方式，可以更好地掌握排序算法的核心概念。