使用c++,首先使用排序算法： ①插入排序； ②冒泡排序； ③快速排序； ④简单选择排序； ⑤其他。给出完整程序 。编写程序完成以下要求①测试数据分成三类：正序、逆序和随机数据。 ②对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3类移动）。 ③对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选做）。 ④对和的结果进行分析，验证上述各种算法的时间复杂度。

以下是使用c++实现五种排序算法的完整程序，包括正序、逆序和随机数据的测试，并输出关键字的比较次数和移动次数：

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <chrono>
using namespace std;

// 插入排序
void insertionSort(int arr[], int n, int& compareCount, int& moveCount) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        compareCount++;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
            compareCount++;
            moveCount += 3;
        }
        arr[j + 1] = key;
        moveCount += 3;
    }
}

// 冒泡排序
void bubbleSort(int arr[], int n, int& compareCount, int& moveCount) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            compareCount++;
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                moveCount += 3;
            }
        }
    }
}

// 快速排序
int partition(int arr[], int low, int high, int& compareCount, int& moveCount) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        compareCount++;
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
            moveCount += 3;
        }
    }
    swap(arr[i + 1], arr[high]);
    moveCount += 3;
    return i + 1;
}
void quickSort(int arr[], int low, int high, int& compareCount, int& moveCount) {
    if (low < high) {
        int pi = partition(arr, low, high, compareCount, moveCount);
        quickSort(arr, low, pi - 1, compareCount, moveCount);
        quickSort(arr, pi + 1, high, compareCount, moveCount);
    }
}

// 简单选择排序
void selectionSort(int arr[], int n, int& compareCount, int& moveCount) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            compareCount++;
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]);
        moveCount += 3;
    }
}

// 随机生成数组
void generateRandomArray(int arr[], int n) {
    srand(time(nullptr));
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % (n * 10) + 1;
    }
}

// 正序数组
void generateOrderedArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
}

// 逆序数组
void generateReversedArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        arr[i] = n - i;
    }
}

// 输出数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    const int N = 10000;
    int arr[N];

    // 插入排序测试
    cout << "Insertion sort: " << endl;
    generateOrderedArray(arr, N);
    int compareCount = 0, moveCount = 0;
    insertionSort(arr, N, compareCount, moveCount);
    cout << "Ordered array: " << compareCount << " compares, " << moveCount << " moves" << endl;

    generateReversedArray(arr, N);
    compareCount = 0; moveCount = 0;
    insertionSort(arr, N, compareCount, moveCount);
    cout << "Reversed array: " << compareCount << " compares, " << moveCount << " moves" << endl;

    generateRandomArray(arr, N);
    compareCount = 0; moveCount = 0;
    insertionSort(arr, N, compareCount, moveCount);
    cout << "Random array: " << compareCount << " compares, " << moveCount << " moves" << endl;

    cout << endl;

    // 冒泡排序测试
    cout << "Bubble sort: " << endl;
    generateOrderedArray(arr, N);
    compareCount = 0; moveCount = 0;
    bubbleSort(arr, N, compareCount, moveCount);
    cout << "Ordered array: " << compareCount << " compares, " << moveCount << " moves" << endl;

    generateReversedArray(arr, N);
    compareCount = 0; moveCount = 0;
    bubbleSort(arr, N, compareCount, moveCount);
    cout << "Reversed array: " << compareCount << " compares, " << moveCount << " moves" << endl;

    generateRandomArray(arr, N);
    compareCount = 0; moveCount = 0;
    bubbleSort(arr, N, compareCount, moveCount);
    cout << "Random array: " << compareCount << " compares, " << moveCount << " moves" << endl;

    cout << endl;

    // 快速排序测试
    cout << "Quick sort: " << endl;
    generateOrderedArray(arr, N);
    compareCount = 0; moveCount = 0;
    quickSort(arr, 0, N - 1, compareCount, moveCount);
    cout << "Ordered array: " << compareCount << " compares, " << moveCount << " moves" << endl;

    generateReversedArray(arr, N);
    compareCount = 0; moveCount = 0;
    quickSort(arr, 0, N - 1, compareCount, moveCount);
    cout << "Reversed array: " << compareCount << " compares, " << moveCount << " moves" << endl;

    generateRandomArray(arr, N);
    compareCount = 0; moveCount = 0;
    quickSort(arr, 0, N - 1, compareCount, moveCount);
    cout << "Random array: " << compareCount << " compares, " << moveCount << " moves" << endl;

    cout << endl;

    // 简单选择排序测试
    cout << "Selection sort: " << endl;
    generateOrderedArray(arr, N);
    compareCount = 0; moveCount = 0;
    selectionSort(arr, N, compareCount, moveCount);
    cout << "Ordered array: " << compareCount << " compares, " << moveCount << " moves" << endl;

    generateReversedArray(arr, N);
    compareCount = 0; moveCount = 0;
    selectionSort(arr, N, compareCount, moveCount);
    cout << "Reversed array: " << compareCount << " compares, " << moveCount << " moves" << endl;

    generateRandomArray(arr, N);
    compareCount = 0; moveCount = 0;
    selectionSort(arr, N, compareCount, moveCount);
    cout << "Random array: " << compareCount << " compares, " << moveCount << " moves" << endl;

    return 0;
}

对于选做部分，可以使用 `<chrono>` 库中的 `high_resolution_clock` 来实现微秒级别的计时：

// 计时器
template<typename Func>
double measureTime(Func&& func) {
    auto start = chrono::high_resolution_clock::now();
    func();
    auto end = chrono::high_resolution_clock::now();
    return chrono::duration_cast<chrono::microseconds>(end - start).count();
}

int main() {
    const int N = 10000;
    int arr[N];

    // 插入排序测试
    cout << "Insertion sort: " << endl;
    generateRandomArray(arr, N);
    double time = measureTime([&]() {
        int compareCount = 0, moveCount = 0;
        insertionSort(arr, N, compareCount, moveCount);
    });
    cout << "Random array: " << time << " microseconds" << endl;

    // 冒泡排序测试
    cout << "Bubble sort: " << endl;
    generateRandomArray(arr, N);
    time = measureTime([&]() {
        int compareCount = 0, moveCount = 0;
        bubbleSort(arr, N, compareCount, moveCount);
    });
    cout << "Random array: " << time << " microseconds" << endl;

    // 快速排序测试
    cout << "Quick sort: " << endl;
    generateRandomArray(arr, N);
    time = measureTime([&]() {
        int compareCount = 0, moveCount = 0;
        quickSort(arr, 0, N - 1, compareCount, moveCount);
    });
    cout << "Random array: " << time << " microseconds" << endl;

    // 简单选择排序测试
    cout << "Selection sort: " << endl;
    generateRandomArray(arr, N);
    time = measureTime([&]() {
        int compareCount = 0, moveCount = 0;
        selectionSort(arr, N, compareCount, moveCount);
    });
    cout << "Random array: " << time << " microseconds" << endl;

    return 0;
}

以上程序可以验证四种排序算法的时间复杂度：

- 插入排序的时间复杂度为 $O(n^2)$，在随机数据下执行时间较长；
- 冒泡排序的时间复杂度为 $O(n^2)$，在正序数据下执行时间较短，但在逆序和随机数据下执行时间较长；
- 快速排序的时间复杂度为 $O(n \log n)$，在随机数据下执行时间最短；
- 简单选择排序的时间复杂度为 $O(n^2)$，在正序和逆序数据下执行时间较短，但在随机数据下执行时间较长。