插入排序的实现

1. 概述

插入排序（Insertion Sort）是一种简单且直观的排序算法。它的基本思想是将未排序的元素逐个插入到已排序的部分中，最终得到一个完全有序的序列。

2. 基本原理

插入排序的核心思想是从未排序的元素中取出一个元素，将其逐个与已排序的元素进行比较，并插入到正确的位置，以保证已排序的部分始终有序。

具体步骤如下：

1. 假设第一个元素已经是有序的序列，可以将其视为已排序部分。
2. 从第二个元素开始，将其与已排序部分的元素逐个比较，找到合适的位置插入。
3. 将待插入元素插入到正确的位置后，将已排序部分的元素向后移动一位，为下一个元素的插入做准备。
   重复步骤2和步骤3，直到所有元素都插入到正确的位置，得到完全有序的序列。

3. C++实现

#include <iostream>
#include <vector>

using namespace std;

// 插入排序
void insertionSort(vector<int>& nums) {
    for (auto i = 1; i < nums.size(); i++){               // 从1开始 
        int a = nums[i];
	for (auto j = i - 1; j >= 0; j--){            // 在已经有序的[0, i)区间寻找nums[i]的位置  
		if (nums[j] > a){
                    nums[j + 1] = nums[j];
                } else {
                   nums[j + 1] = a;
                }
       }
    }
}

int main() {
        // 测试用例
        vector<vector<int>> test_case = {
        {2, 2},
        {1, 2},
        {2, 1},
        {2, 2, 2, 2, 2},
        {1, 2, 3, 4, 5},
        {5, 4, 3, 2, 1},
    };

        // 加一些随机数组
        srand(time(0));
        for (int i = 0; i < 1000; i++){
                int len = rand() % 100 + 1;
                vector<int> nums(len);
                for (int j = 0; j < len; j++){
                        nums.push_back(rand() % 100);
                }
                test_case.push_back(nums);
        }

        for (auto nums : test_case){
                insertionSort(nums);

                for (int i = 1; i < nums.size(); i++){
                        if (nums[i - 1] > nums[i]){
                                cout << "error" << endl;
                                return 0;
                        }
                }
        }

        cout << "all is ok" << endl;
        return 0;
}

4.希尔插入排序

希尔插入排序（Shell Insertion Sort），也称为缩小增量排序，是插入排序的一种改进版本。希尔排序通过将待排序的元素划分为多个子序列来提高插入排序的效率，然后逐步缩小增量，最终完成整个序列的排序。希尔排序的核心思想是通过插入排序对子序列进行排序，从而减少元素的移动次数，提高排序的速度。

下面是希尔插入排序的基本步骤：

1. 首先，选择一个增量（间隔）序列，通常为原序列长度的一半，并对序列进行分组。每个分组称为一个子序列。
2. 对每个子序列进行插入排序，即将每个子序列中的元素按照插入排序的方式进行排序。
3. 缩小增量，重复步骤2，直到增量为1。
4. 最后，对整个序列进行一次插入排序，以确保序列的完全有序性。

void shellInsertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int key = arr[i];
            int j = i;

            while (j >= gap && arr[j - gap] > key) {
                arr[j] = arr[j - gap];
                j -= gap;
            }

            arr[j] = key;
        }
    }
}

普通的插入排序是逐个将元素插入已排序的序列中，如果待插入的元素较小，就需要将已排序的元素逐个后移，以腾出空位插入新元素。这种逐个移动的操作会导致数据的大量移动，特别是当待排序的数据集合较大时，效率会明显降低。

而希尔插入排序通过引入间隔序列，先进行间隔为较大值的插入排序，使得数据可以跳跃式地移动，从而快速地将较小的元素移到合适的位置。然后逐渐缩小间隔，再进行插入排序，直到间隔为1时，即退化为普通的插入排序。通过这种分组和逐渐缩小间隔的方式，希尔插入排序减少了数据移动的次数，提高了排序的效率。

5.总结

插入排序是一种简单但有效的排序算法，适用于小规模的数据集或者基本有序的数据集。它的实现思路直观明了，通过逐个比较和插入来构建有序序列。
虽然插入排序的时间复杂度为O(n²)，在大规模数据集上的性能可能不如其他高级排序算法，但在某些特定场景下，插入排序的性能表现仍然是可接受的。