十大排序算法（三） - 插入排序算法

排序算法是计算机科学中的基础概念，它们用于对数据集合进行有序排列。插入排序（Insertion Sort）是其中一种简单而有效的排序算法。本文将详细介绍插入排序的工作原理，并提供Python、Go、Java和C语言的示例代码。

插入排序的基本思想

插入排序的基本思想是将数据分成已排序和未排序两部分，初始时已排序部分只包含第一个元素，而未排序部分包含其他元素。然后，它从未排序部分依次选择元素，将其插入到已排序部分的合适位置，直到所有元素都在已排序部分。

让我们通过一个简单的示例来理解插入排序的工作原理。假设我们有一个整数数组 [5, 2, 9, 3, 4]，我们希望按升序排序它。

初始状态：首先，已排序部分只包含第一个元素 5，未排序部分包含其他元素 [2, 9, 3, 4]。
第一次插入：从未排序部分选择第一个元素 2，将它与已排序部分的 5 比较。因为 2 < 5，所以 2 插入到 5 的前面，得到 [2, 5] 和 [9, 3, 4]。
第二次插入：继续选择未排序部分的第一个元素 9，将它与已排序部分的 5 和 2 比较。由于 9 > 5，不需要交换。已排序部分保持不变 [2, 5]，未排序部分为 [3, 4]。
继续插入：依此类推，依次选择未排序部分的元素并插入到已排序部分的正确位置。最终，数组被完全排序成 [2, 3, 4, 5, 9]。

插入排序的关键在于将元素逐个插入到已排序部分，并确保已排序部分始终保持升序。

插入排序的时间复杂度

插入排序的时间复杂度取决于输入数据的顺序。在最好的情况下，即数据已经按升序排列，插入排序的时间复杂度为O(n)，其中n是数组的长度。这是因为在最好情况下，不需要执行元素交换，只需遍历一次数组。

在最坏的情况下，即数据逆序排列，插入排序的时间复杂度为O(n^2)，因为每个元素都需要与已排序部分的所有元素进行比较和移动。

插入排序在小型数据集上通常表现良好，但对于大型数据集，更高效的排序算法可能更合适。

插入排序的应用场景

尽管插入排序不如一些高级排序算法那样高效，但它仍然有一些应用场景：

小型数据集：插入排序在处理小型数据集时性能良好，因为其常数因子较低。
部分有序数据：如果数据集已经部分有序，插入排序的性能会较好，因为不需要多次交换元素。
稳定性要求：插入排序是一种稳定的排序算法，可以保持相同元素的相对位置。
在线排序：插入排序可以应用于在线排序场景，即数据不一次性全部可用，而是逐个元素到达。

示例代码

以下是插入排序的示例代码，分别使用Python、Go、Java和C语言编写。

Python 插入排序

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

arr = [5, 2, 9, 3, 4]
insertion_sort(arr)
print("排序后的数组:", arr)

Go 插入排序

package main

import "fmt"

func insertionSort(arr []int) {
    n := len(arr)
    for i := 1; i < n; i++ {
        key := arr[i]
        j := i - 1
        for j >= 0 && key < arr[j] {
            arr[j+1] = arr[j]
            j--
        }
        arr[j+1] = key
    }
}

func main() {
    arr := []int{5, 2, 9, 3, 4}
    insertionSort(arr)
    fmt.Println("排序后的数组:", arr)
}

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 && key < arr[j]) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 3, 4};
        insertionSort(arr);
        System.out.print("排序后的数组: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

C 语言插入排序

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && key < arr[j]) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {5, 2, 9, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("排序后的数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

这些示例代码演示了插入排序的工作原理，并提供了Python、Go、Java和C语言的不同语言版本的实现。插入排序虽然简单，但在一些特定情况下是一种有效的排序算法，特别适合处理小型数据集或部分有序的数据。