直接插入排序

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int a[N];
int n;

void InsertSort()
{
    // 要插入的数为end+1
    for (int i = 0; i < n - 1; i++)
    {
        int end = i;
        int key = a[end + 1];
        while (end >= 0 && a[end] > key) // a[]覆盖后移并end前移过程
        {
            a[end + 1] = a[end];
            end--;
        }
        a[end + 1] = key; // 当前end比key小，直接在end+1处插入key
    }
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    InsertSort();
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << ' ';
    }
    return 0;
}

希尔排序

#include <bits/stdc++.h>
using namespace std;
const int N = 1000;

int a[N];
int n;

void ShellSort()
{
    int gap = n;
    for (int g = gap / 2; g >= 1; g /= 2)
    {
        for (int k = 0; k < g; k++)
        {
            for (int j = k + g; j < n; j += g)
            {
                int end = j - g;
                int key = a[end + g];
                while (end >= 0 && a[end] < key)
                {
                    a[end + g] = a[end];
                    end -= g;
                }
                a[end + g] = key;
            }
        }
        for (int x = 0; x < n; x++)
        {
            cout << a[x];
            if (x != n - 1)
                cout << ' ';
        }
        cout << endl;
    }
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
        }
        ShellSort();
        if (t != 0)
            cout << endl;
    }
    return 0;
}