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

插入排序是一种简单的排序算法，基本思想是将一个数组分为两部分，已排序的部分和未排序的部分。将未排序的部分中的每个元素插入到已排序的部分中正确的位置，直到将所有元素都插入到已排序的部分中，这样整个数组就被排序了。具体操作步骤如下：

1. 将第一个元素视为已排序部分，第二个元素开始视为未排序部分；

2. 从未排序部分中取出一个元素，与已排序部分中的元素从后向前逐个进行比较；

3. 如果已排序部分中的元素大于取出的元素，就将已排序部分中的元素后移一位，直到找到合适的插入位置；

4. 将取出的元素插入到已排序部分中的合适位置；

5. 重复步骤2~4，直到所有元素都被插入到已排序部分中为止。

插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)，在小规模数据排序时性能较好，但对于大规模数据排序来说性能较差。

一、C 实现插入排序及代码详解

插入排序是一种简单直观的排序方法，其基本思想就是将一个待排序的序列分为已排序和未排序两部分，每次从未排序的部分中取出一个元素，遍历已排序的部分，找到插入位置插入。插入排序的时间复杂度为O(n^2)，适用于小规模数据的排序。

以下是C语言实现插入排序的代码及详解：

void insertionSort(int arr[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        // 将arr[j]比key大的元素向后移动一位
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        // 插入key
        arr[j + 1] = key;
    }
}

函数参数说明：

• arr：待排序数组
• n：数组长度

函数实现说明：

1. 初始化变量i为1，表示从第二个元素开始遍历数组
2. 将第i个元素存储在变量key中，并初始化变量j为i-1
3. 比较arr[j]和key的大小，如果arr[j]比key大，则将arr[j]向后移动一位，j–，继续比较，直到找到arr[j]比key小的位置或j<0
4. 插入key到j+1的位置

注释中已经详细解释了代码中每个步骤的含义，结合代码可以更好地理解它的实现过程。

二、C++ 实现插入排序及代码详解

插入排序是一种简单直观的排序算法，其基本思想是每次将一个待排序的元素插入到已经排好序的序列中，直到全部元素都插入到已排序序列中。以下是使用 C++ 实现插入排序的代码及详解：

#include <iostream>
#include <vector>

using namespace std;

void insertion_sort(vector<int>& nums) {
    int n = nums.size();
    for (int i = 1; i < n; i++) {
        int key = nums[i];
        int j = i - 1;
        while (j >= 0 && nums[j] > key) {
            nums[j + 1] = nums[j];
            j = j - 1;
        }
        nums[j + 1] = key;
    }
}

int main() {
    vector<int> nums = {3, 1, 4, 2, 5};
    insertion_sort(nums);
    for (int i : nums) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

首先定义了一个 insertion_sort 函数来实现插入排序，它接受一个整数数组 nums 的引用作为参数。在函数中，我们首先获取数组的长度 n，然后从第二个元素开始遍历数组，即 i = 1。对于当前遍历的元素 nums[i]，我们将其赋值给一个 key 变量。

接下来，我们将 key 插入到已排序序列 nums[0]...nums[i-1] 中，这是通过一个 while 循环实现的。该循环从 i - 1 开始，向前遍历已排序序列，找到第一个小于等于 key 的元素 nums[j] 的位置，然后将 nums[j + 1] 赋值为 nums[j]，这样就为 key 腾出了一个位置。接着，我们将 key 插入到 nums[j + 1] 的位置上。

最后，我们在 main 函数中定义一个整数数组 nums，并将 {3, 1, 4, 2, 5} 赋值给它。然后，我们调用 insertion_sort 函数对 nums 进行排序，并使用一个 for 循环打印排序后的结果。

三、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;
            // 在已排序区间中从后向前查找插入位置
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;  // 插入当前元素
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 4, 7, 6, 1, 3, 8};
        System.out.println("排序前：" + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }
}

代码中的 insertionSort 方法接收一个整型数组作为输入，对该数组进行插入排序。变量 n 表示数组的长度，i 从 1 开始遍历数组，表示当前要插入的元素的位置。变量 key 表示当前要插入的元素的值。

在插入元素之前，我们需要在已排序区间中查找插入位置。变量 j 从 i - 1 开始向前遍历已排序区间，寻找插入位置。

如果当前元素比插入位置的元素小，则将插入位置的元素后移一位，继续往前查找。这个过程可以用一个 while 循环实现。插入位置的元素后移的过程中，我们需要将数组中的元素依次向后移动一位，以便为当前元素腾出位置。

当找到插入位置时，将当前元素插入该位置。

最终，我们得到的就是一个有序的数组。

上述代码的输出结果为：

排序前：[5, 2, 9, 4, 7, 6, 1, 3, 8]
排序后：[1, 2, 3, 4, 5, 6, 7, 8, 9]

可以看到，插入排序对于这个乱序的数组排序得非常快，时间复杂度是 $O(n^2)$，空间复杂度是 $O(1)$。虽然效率比不上快速排序和归并排序等高级排序算法，但插入排序算法代码量小，实现简单，对于小规模的数据排序非常快捷。