#include <iostream>
#include <vector>
#include <algorithm>

// 直接插入排序
void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    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 = j - 1;
        }
        arr[j + 1] = key;
    }
}

// 一趟希尔排序（增量为d）
void shellSortOnePass(std::vector<int>& arr, int d) {
    int n = arr.size();
    for (int i = d; i < n; ++i) {
        int temp = arr[i];
        int j;
        for (j = i; j >= d && arr[j - d] > temp; j -= d) {
            arr[j] = arr[j - d];
        }
        arr[j] = temp;
    }
}

// 直接选择排序
void selectionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int min_index = i;
        for (int j = i + 1; j < n; ++j) {
            if (ar...