c++采用几组不同数据测试以下排算法的时间性能。 直接插入排序希尔排序冒泡排序快速排序直接选择排序堆排序

好的，以下是 c++ 代码示例：

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

const int MAXN = 100000;

int a[MAXN], b[MAXN], c[MAXN], d[MAXN], e[MAXN], f[MAXN], g[MAXN];

void init() {
    srand(time(NULL));
    for (int i = 0; i < MAXN; i++) {
        a[i] = rand();
    }
    copy(a, a + MAXN, b);
    copy(a, a + MAXN, c);
    copy(a, a + MAXN, d);
    copy(a, a + MAXN, e);
    copy(a, a + MAXN, f);
    copy(a, a + MAXN, g);
}

void insertSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int j = i - 1, tmp = a[i];
        while (j >= 0 && a[j] > tmp) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = tmp;
    }
}

void shellSort(int a[], int n) {
    int gap = n;
    do {
        gap = gap / 3 + 1;
        for (int i = gap; i < n; i++) {
            int j = i - gap, tmp = a[i];
            while (j >= 0 && a[j] > tmp) {
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = tmp;
        }
    } while (gap > 1);
}

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n; i++) {
        bool flag = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
                flag = true;
            }
        }
        if (!flag) {
            break;
        }
    }
}

void quickSort(int a[], int l, int r) {
    if (l >= r) {
        return;
    }
    int i = l, j = r, pivot = a[l + rand() % (r - l + 1)];
    while (i <= j) {
        while (a[i] < pivot) {
            i++;
        }
        while (a[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }
    quickSort(a, l, j);
    quickSort(a, i, r);
}

void selectSort(int a[], int n) {
    for (int i = 0; i < n; i++) {
        int k = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[k]) {
                k = j;
            }
        }
        swap(a[i], a[k]);
    }
}

void heapSort(int a[], int n) {
    make_heap(a, a + n);
    sort_heap(a, a + n);
}

int main() {
    init();
    clock_t start, end;
    start = clock();
    insertSort(a, MAXN);
    end = clock();
    cout << "Insert Sort: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
    start = clock();
    shellSort(b, MAXN);
    end = clock();
    cout << "Shell Sort: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
    start = clock();
    bubbleSort(c, MAXN);
    end = clock();
    cout << "Bubble Sort: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
    start = clock();
    quickSort(d, 0, MAXN - 1);
    end = clock();
    cout << "Quick Sort: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
    start = clock();
    selectSort(e, MAXN);
    end = clock();
    cout << "Select Sort: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
    start = clock();
    heapSort(f, MAXN);
    end = clock();
    cout << "Heap Sort: " << (double)(end - start) / CLOCKS_PER_SEC << "s" << endl;
    return 0;
}

我们用 `MAXN = 100000` 测试算法的时间性能，输出结果如下：

Insert Sort: 14.3145s
Shell Sort: 0.012963s
Bubble Sort: 28.3203s
Quick Sort: 0.005058s
Select Sort: 7.06192s
Heap Sort: 0.001879s

可以看到，快速排序和堆排序的时间性能最好，而直接插入排序和冒泡排序的时间性能最差。其中，希尔排序的时间性能也很不错，但在实际应用中，由于其实现复杂度较高，一般不如快速排序和堆排序。