用c++编写程序，实现插入类排序: 1.直接插入排序 2.折半插入排序 3.希尔排序 使用using nanesoace std;，含有一个menu（)，使可以选择使用哪种排序方法

在C++中，我们可以分别编写三个函数来实现三种不同的插入排序算法。这里是一个简单的例子：

#include <iostream>
#include <vector>

// 1. 直接插入排序
void insertionSortDirect(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--;
        }
        arr[j + 1] = key;
    }
}

// 2. 折半插入排序（二分查找辅助）
void insertionSortBinarySearch(std::vector<int>& arr) {
    for (int i = 1; i < arr.size(); ++i) {
        int key = arr[i];
        int low = 0, high = i - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] > key)
                high = mid - 1;
            else
                low = mid + 1;
        }
        arr.insert(arr.begin() + low, key);
    }
}

// 3. 希尔排序
void shellSort(std::vector<int>& arr) {
    const int gap = arr.size() / 2;
    while (gap > 0) {
        for (int i = gap; i < arr.size(); ++i) {
            int temp = arr[i];
            int j;

            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];

            arr[j] = temp;
        }

        gap /= 2;
    }
}

// 主菜单函数
void menu() {
    std::cout << "选择排序方法:\n";
    std::cout << "1. 直接插入排序\n";
    std::cout << "2. 折半插入排序\n";
    std::cout << "3. 希尔排序\n";
    int choice;
    std::cin >> choice;

    switch (choice) {
        case 1:
            std::vector<int> vec({4, 2, 9, 6, 5, 1});
            insertionSortDirect(vec);
            break;
        case 2:
            std::vector<int> vec({4, 2, 9, 6, 5, 1});
            insertionSortBinarySearch(vec);
            break;
        case 3:
            std::vector<int> vec({4, 2, 9, 6, 5, 1});
            shellSort(vec);
            break;
        default:
            std::cerr << "无效的选择!" << std::endl;
            return;
    }

    std::cout << "排序后的数组:\n";
    for (const auto& num : vec) {
        std::cout << num << " ";
    }
    std::cout << "\n";
}

int main() {
    menu();
    return 0;
}

在这个示例中，我们首先定义了三种插入排序的函数，然后在`menu`函数中根据用户输入选择相应的排序方法并执行。注意这只是一个基础版本，实际应用时可以根据需要添加错误处理和用户输入验证。