插入排序

想象一下你正在手里整理一副扑克牌：

1. 你手里拿着的牌（左手）是已经排好序的。
2. 你从桌上的牌堆（右手）里依次拿出一张牌。
3. 将这张新牌与你手中已排好序的牌从右到左进行比较。
4. 找到它应该插入的正确位置，然后将它插入，保持你手中的牌依然有序。
5. 重复这个过程，直到桌上的牌全部拿完。

插入排序就是模拟了这个过程。

插入排序的步骤

我们以一个具体的例子来演示，假设待排序的数组是：[8, 5, 2, 6, 9, 3]

步骤分解

1. 初始状态：
   • 我们将数组分为两部分：已排序区间和未排序区间。
   • 初始时，已排序区间只包含第一个元素 [8]。
   • 未排序区间是剩下的所有元素 [5, 2, 6, 9, 3]。
   • 数组状态：[ **8**, | 5, 2, 6, 9, 3 ]
2. 取出未排序区间的第一个元素：
   • 取出 5。
   • 将 5 与已排序区间的 8 进行比较。
   • 因为 5 < 8，所以将 8 向右移动一位。
   • 此时已排序区间的开头出现空位，将 5 插入。
   • 数组状态变为：[ **5, 8**, | 2, 6, 9, 3 ]
3. 继续取出下一个元素：
   • 取出 2。
   • 将 2 与已排序区间的 8 比较 (2 < 8)，8 右移。
   • 将 2 与已排序区间的 5 比较 (2 < 5)，5 右移。
   • 已排序区间开头出现空位，将 2 插入。
   • 数组状态变为：[ **2, 5, 8**, | 6, 9, 3 ]
4. 继续取出下一个元素：
   • 取出 6。
   • 将 6 与已排序区间的 8 比较 (6 < 8)，8 右移。
   • 将 6 与已排序区间的 5 比较 (6 > 5)，找到了插入位置。
   • 将 6 插入到 5 和 8 之间。
   • 数组状态变为：[ **2, 5, 6, 8**, | 9, 3 ]
5. 继续取出下一个元素：
   • 取出 9。
   • 将 9 与已排序区间的 8 比较 (9 > 8)，找到了插入位置。
   • 9 直接放在 8 的后面，无需移动任何元素。
   • 数组状态变为：[ **2, 5, 6, 8, 9**, | 3 ]
6. 最后一次插入：
   • 取出 3。
   • 将 3 与已排序区间的 9 比较 (3 < 9)，9 右移。
   • 将 3 与已排序区间的 8 比较 (3 < 8)，8 右移。
   • 将 3 与已排序区间的 6 比较 (3 < 6)，6 右移。
   • 将 3 与已排序区间的 5 比较 (3 < 5)，5 右移。
   • 将 3 与已排序区间的 2 比较 (3 > 2)，找到了插入位置。
   • 将 3 插入到 2 和 5 之间。
   • 数组状态变为：[ **2, 3, 5, 6, 8, 9** | ]

排序完成

此时，未排序区间已经为空，整个数组都变成了已排序区间。排序结束。

核心特点总结

1. 时间复杂度：
   • 最坏情况和平均情况：O(n²)。当数组完全逆序时，每次插入都需要移动前面所有的元素。
   • 最好情况：O(n)。当数组已经是有序的，每次插入只需要比较一次，无需移动任何元素。
2. 空间复杂度：O(1)。插入排序是原地排序，不需要额外的存储空间，只需要一个临时变量来存放待插入的元素。
3. 稳定性：稳定。在比较和移动元素时，如果遇到相等的元素，插入排序不会改变它们的相对顺序。
4. 适用场景：
   • 适用于数据量较小的情况。
   • 适用于基本有序的数组，此时效率非常高。
   • 是许多高级排序算法（如希尔排序）的基础。

希尔排序

希尔排序是插入排序的改进版

如果每个元素都距离他的最终位置距离不远，那插入排序排序效率还是很高的，远了就不行了

为了解决这个问题，希尔排序先分组（概念上分组，代码中不用分），

每H（如果H=4 那么拿[ [0],[4],[8] ]）拿出来一个元素作为一组，进行插入排序，变成一个H有序的数组，可以让元素先走大步子

然后缩小H，排序，直到最后H=1，就是普通的插入排序

对于大部分数据来说，这时每个元素距离目的地已经不远了

h有说法的，H序列对性能有很大影响

AI人话版

1. 洞察核心问题：
   • 插入排序在处理基本有序的数组时效率很高（接近 O (n)）。
   • 但在处理无序数组时，尤其是当一个很小的元素在数组末尾时，它需要一步一步地移动到数组开头，导致大量的比较和交换操作，效率骤降为 O (n²)。
2. 希尔排序的解决方案：
   • 分组预处理：希尔排序的核心是分组。它不像插入排序那样逐个比较相邻元素，而是按一个增量（gap）h将数组元素划分为若干组。
     • 例如，如果h=4，那么索引为0, 4, 8, ...的元素为一组，索引为1, 5, 9, ...的元素为另一组，以此类推。
   • 组内插入排序：对每一组元素独立地执行插入排序。这一步的目的不是为了完全排序，而是为了让数组变得 **“部分有序”或“h 有序”**。
   • 大步长移动：通过这种方式，那些距离最终位置很远的元素，可以借助较大的h值，以 **“大步长”** 快速地移动到大致正确的位置，而无需一步一步地挪动。
3. 逐步精调过程：
   • 完成一轮h增量的排序后，数组已经比之前有序得多。
   • 此时，缩小增量h（例如，取h = h / 2），然后重复上述分组和组内插入排序的过程。
   • 随着h值的不断减小，分组越来越多，每组包含的元素也越来越少，但数组的有序程度却在不断提高。
4. 最终阶段：
   • 这个过程一直持续，直到增量h减小到1。
   • 当h=1时，整个数组被看作一个分组，此时执行的就是一次标准的插入排序。
   • 由于经过前面几轮的 “预处理”，此时的数组已经基本有序，所以最后这次插入排序会非常高效，几乎可以在线性时间内完成。
5. 关键：增量序列的选择：
   • 你提到的 “h 有说法的” 非常关键。增量序列（h-sort sequence）的选择是决定希尔排序性能的核心因素。
   • 一个好的增量序列可以显著提升排序效率。常用的有：
     • Knuth 序列 ((3^k - 1) / 2)：在实践中表现非常好，是推荐的选择。
     • Hibbard 序列 (2^k - 1)：理论上分析性能较好。
     • 简单序列 (n/2, n/4, ..., 1)：实现简单，但性能相对较差。

from:https://www.cnblogs.com/chengxiao/p/6104371.html

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

　　简单插入排序很循规蹈矩，不管数组分布是怎么样的，依然一步一步的对元素进行比较，移动，插入，比如[5,4,3,2,1,0]这种倒序序列，数组末端的0要回到首位置很是费劲，比较和移动元素均需n-1次。而希尔排序在数组中采用跳跃式分组的策略，通过某个增量将数组元素划分为若干组，然后分组进行插入排序，随后逐步缩小增量，继续按组进行插入排序操作，直至增量为1。希尔排序通过这种策略使得整个数组在初始阶段达到从宏观上看基本有序，小的基本在前，大的基本在后。然后缩小增量，到增量为1时，其实多数情况下只需微调即可，不会涉及过多的数据移动。

　　我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

#include <iostream>
using namespace std;

#include <cstdlib>
#include <ctime>

const int MAX = 10;
int arr[MAX];

void generateRandomArray() {
    std::srand(static_cast<unsigned>(std::time(nullptr)));
    for (int i = 0; i < MAX; ++i) {
        arr[i] = std::rand() % 100; // 0~99的随机数
    }
}
void printArray() {
    for (int i = 0; i < MAX; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main(){
    cout << "Original array:\n" << endl;
    generateRandomArray();
    printArray();
    int N = MAX;
    int h = 1;
    while (h < N / 3){
        h = 3 * h + 1;
    } // 计算最大增量
    
    cout << "\n开始希尔排序，初始增量序列:" << endl;
    while(h >= 1){ //跃进值
        cout << "\n当前增量 h = " << h << endl;
        cout << "开始对间隔为 " << h << " 的子数组进行插入排序:" << endl;
        
        for(int i = h; i < MAX; i++){
            for(int j = i; j >= h && arr[j] < arr[j-h]; j -= h) {
                cout << "比较 arr[" << j << "]=" << arr[j] << " 和 arr[" << j-h << "]=" << arr[j-h];
                cout << " -> 需要交换" << endl;
                
                cout << "交换前: ";
                printArray();
                
                std::swap(arr[j], arr[j-h]);
                
                cout << "交换 arr[" << j << "] 和 arr[" << j-h << "] 后: ";
                printArray();
                cout << endl;
            }
        }
        
        cout << "增量 h=" << h << " 的排序完成" << endl;
        h = h/3;
    }
    cout << "Sorted array:\n" << endl;
    printArray();
    return 0;
}

Original array:

97 89 52 87 65 91 95 64 16 17

开始希尔排序，初始增量序列:

当前增量 h = 4
开始对间隔为 4 的子数组进行插入排序:
比较 arr[4]=65 和 arr[0]=97 -> 需要交换
交换前: 97 89 52 87 65 91 95 64 16 17
交换 arr[4] 和 arr[0] 后: 65 89 52 87 97 91 95 64 16 17

比较 arr[7]=64 和 arr[3]=87 -> 需要交换
交换前: 65 89 52 87 97 91 95 64 16 17
交换 arr[7] 和 arr[3] 后: 65 89 52 64 97 91 95 87 16 17

比较 arr[8]=16 和 arr[4]=97 -> 需要交换
交换前: 65 89 52 64 97 91 95 87 16 17
交换 arr[8] 和 arr[4] 后: 65 89 52 64 16 91 95 87 97 17

比较 arr[4]=16 和 arr[0]=65 -> 需要交换
交换前: 65 89 52 64 16 91 95 87 97 17
交换 arr[4] 和 arr[0] 后: 16 89 52 64 65 91 95 87 97 17

比较 arr[9]=17 和 arr[5]=91 -> 需要交换
交换前: 16 89 52 64 65 91 95 87 97 17
交换 arr[9] 和 arr[5] 后: 16 89 52 64 65 17 95 87 97 91

比较 arr[5]=17 和 arr[1]=89 -> 需要交换
交换前: 16 89 52 64 65 17 95 87 97 91
交换 arr[5] 和 arr[1] 后: 16 17 52 64 65 89 95 87 97 91

增量 h=4 的排序完成

当前增量 h = 1
开始对间隔为 1 的子数组进行插入排序:
比较 arr[7]=87 和 arr[6]=95 -> 需要交换
交换前: 16 17 52 64 65 89 95 87 97 91
交换 arr[7] 和 arr[6] 后: 16 17 52 64 65 89 87 95 97 91

比较 arr[6]=87 和 arr[5]=89 -> 需要交换
交换前: 16 17 52 64 65 89 87 95 97 91
交换 arr[6] 和 arr[5] 后: 16 17 52 64 65 87 89 95 97 91

比较 arr[9]=91 和 arr[8]=97 -> 需要交换
交换前: 16 17 52 64 65 87 89 95 97 91
交换 arr[9] 和 arr[8] 后: 16 17 52 64 65 87 89 95 91 97

比较 arr[8]=91 和 arr[7]=95 -> 需要交换
交换前: 16 17 52 64 65 87 89 95 91 97 
交换 arr[8] 和 arr[7] 后: 16 17 52 64 65 87 89 91 95 97

增量 h=1 的排序完成
Sorted array:

16 17 52 64 65 87 89 91 95 97

归并排序

自顶向下方式

#include <iostream>
using namespace std;

#include <cstdlib>
#include <ctime>
#include <algorithm> // 添加这个头文件用于 sort 函数
const int MAX = 100;
int arr[MAX];
int aux[100] = {};
int backup[MAX]; // 添加备份数组

void generateRandomArray() {
    std::srand(static_cast<unsigned>(std::time(nullptr)));
    for (int i = 0; i < MAX; ++i) {
        arr[i] = std::rand() % 100; // 0~99的随机数
        backup[i] = arr[i]; // 备份原始数组
    }
}

void printArray() {
    for (int i = 0; i < MAX; ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void printAux() {
    cout<<"aux:"<<endl;
    for (int i = 0; i < MAX; ++i) {
        cout << aux[i] << " ";
    }
    cout << endl;
}

// 检查排序是否正确的函数
bool checkSortResult() {
    // 检查1: 验证数组是否有序
    for (int i = 0; i < MAX - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            cout << "排序错误：数组不是升序的！位置 " << i << " 和 " << i + 1 << endl;
            return false;
        }
    }
    
    // 检查2: 验证元素是否与原数组相同
    // 先对备份数组进行排序
    int sortedBackup[MAX];
    for (int i = 0; i < MAX; i++) {
        sortedBackup[i] = backup[i];
    }
    std::sort(sortedBackup, sortedBackup + MAX);
    
    // 比较排序后的数组与标准排序结果
    for (int i = 0; i < MAX; i++) {
        if (arr[i] != sortedBackup[i]) {
            cout << "排序错误：元素不匹配！位置 " << i << " 期望值 " << sortedBackup[i] << " 实际值 " << arr[i] << endl;
            return false;
        }
    }
    
    cout << "排序验证通过：数组已正确排序且包含所有原始元素！" << endl;
    return true;
}

void sort(int left,int right) {
    if(right <= left){
        return;
    }
    int half = left + (right - left)/2;
    sort(left,half);
    sort(half+1,right);
    for(int i =left;i<=right;i++){
        aux[i] = arr[i];
        // cout<<arr[i]<<"["<<i<<"];";
    }
    int left_p = left;
    int right_p = half+1;
    for(int i = left;i<=right;i++){
        if(left_p > half) { arr[i] = aux[right_p++]; }
        else if(right_p > right) {arr[i] = aux[left++];}
        else if(aux[left_p] > aux[right_p]){
            arr[i] = aux[right_p++];
        }else{
            arr[i] = aux[left_p++];
        }
    }
}

int main(){
    cout << "Original array:" << endl;
    generateRandomArray();
    printArray();
    
    cout << "\nSorted array:" << endl;
    sort(0,MAX-1);
    printArray();
    
    cout << "\n验证结果:" << endl;
    checkSortResult();
    
    return 0;
}

优化-短数组直接插入排序

#include <iostream>
using namespace std;

#include <cstdlib>
#include <ctime>
#include <algorithm> // 添加这个头文件用于 sort 函数
const int MAX = 100;
int arr[MAX];
int aux[100] = {};
int backup[MAX]; // 添加备份数组

void generateRandomArray()
{
    std::srand(static_cast<unsigned>(std::time(nullptr)));
    for (int i = 0; i < MAX; ++i)
    {
        arr[i] = std::rand() % 100; // 0~99的随机数
        backup[i] = arr[i];         // 备份原始数组
    }
}

void printArray()
{
    for (int i = 0; i < MAX; ++i)
    {
        cout << arr[i] << " ";
    }
    cout << endl;
}

void printAux()
{
    cout << "aux:" << endl;
    for (int i = 0; i < MAX; ++i)
    {
        cout << aux[i] << " ";
    }
    cout << endl;
}

// 检查排序是否正确的函数
bool checkSortResult()
{
    // 检查1: 验证数组是否有序
    for (int i = 0; i < MAX - 1; i++)
    {
        if (arr[i] > arr[i + 1])
        {
            cout << "排序错误：数组不是升序的！位置 " << i << " 和 " << i + 1 << endl;
            return false;
        }
    }

    // 检查2: 验证元素是否与原数组相同
    // 先对备份数组进行排序
    int sortedBackup[MAX];
    for (int i = 0; i < MAX; i++)
    {
        sortedBackup[i] = backup[i];
    }
    std::sort(sortedBackup, sortedBackup + MAX);

    // 比较排序后的数组与标准排序结果
    for (int i = 0; i < MAX; i++)
    {
        if (arr[i] != sortedBackup[i])
        {
            cout << "排序错误：元素不匹配！位置 " << i << " 期望值 " << sortedBackup[i] << " 实际值 " << arr[i] << endl;
            return false;
        }
    }

    cout << "排序验证通过：数组已正确排序且包含所有原始元素！" << endl;
    return true;
}

void sort(int left, int right)
{
    // if(right <= left){ //差==1 || == 0
    //     return;
    // }
    int len = right - left;
    cout << len << "|";
    if (len < 15)
    {
        for (int i = left; i <= right; i++)
        {
            for (int j = i; j > left && arr[j] < arr[j - 1]; j--)
            {
                swap(arr[j], arr[j - 1]);
            }
        }
        return;
    }
    int half = left + len / 2;
    sort(left, half);
    sort(half + 1, right);
    for (int i = left; i <= right; i++)
    {
        aux[i] = arr[i];
        // cout<<arr[i]<<"["<<i<<"];";
    }
    int left_p = left;
    int right_p = half + 1;
    for (int i = left; i <= right; i++)
    {
        if (left_p > half)
        {
            arr[i] = aux[right_p++];
        }
        else if (right_p > right)
        {
            arr[i] = aux[left_p++];
        }
        else if (aux[left_p] > aux[right_p])
        {
            arr[i] = aux[right_p++];
        }
        else
        {
            arr[i] = aux[left_p++];
        }
    }
}

int main()
{
    cout << "Original array:" << endl;
    generateRandomArray();
    printArray();

    cout << "\nSorted array:" << endl;
    sort(0, MAX - 1);
    printArray();

    cout << "\n验证结果:" << endl;
    checkSortResult();

    return 0;
}

快速排序

void sort(int left,int right) {
    if(right <= left){
        return;
    }
    //基点，排序
    int k = arr[left];
    int lp = left;
    int rp = right+1;
    while(true){
        while(arr[++lp] <= k){
            if(lp > rp){
                break;
            }
        }
        while(arr[--rp] >= k){
            if(rp < lp){
                break;
            }
        }
        if(rp <= lp){
            break;
        }
        swap(arr[lp],arr[rp]);
    }
    swap(arr[left],arr[rp]);
    sort(left,rp-1);
    sort(rp+1,right);
}

int main() {
    cout << "Original array:" << endl;
    generateRandomArray();
    printArray();

    cout << "\nSorted array:" << endl;
    
    // 开始计时
    auto start = std::chrono::high_resolution_clock::now();
    
    sort(0,MAX-1); // 调用排序函数
    
    // 结束计时
    auto end = std::chrono::high_resolution_clock::now();
    
    // 计算耗时
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    printArray();

    cout << "\n排序耗时: " << duration.count() << " 微秒 (" 
         << duration.count() / 1000.0 << " 毫秒)" << endl;

    cout << "\n验证结果:" << endl;
    checkSortResult();

    return 0;
}

其他

1.先打乱数组以应对输入影响

2.想让希尔排序慢还是挺难的

3.

4.算法是可以随时创造的，不是天生的有那么一批类别，让大家看着分类的