数据结构c++1.随机产生500个1～2000之间的整数并输出，完成以下操作： (1)对给定整数进行直接插入排序，显示排序所用时间； (2)对给定整数进行希尔排序，显示排序所用时间； (3)对给定整数进行起泡排序，显示排序所用时间； (4)对给定整数进行快速排序，显示排序所用时间。

以下是实现上述要求的C++代码：

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// 直接插入排序
void InsertionSort(int arr[], int n)
{
    clock_t start_time = clock(); // 记录开始时间
    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;
    }
    clock_t end_time = clock(); // 记录结束时间
    cout << "直接插入排序所用时间：" << double(end_time - start_time) / CLOCKS_PER_SEC << " 秒" << endl;
}

// 希尔排序
void ShellSort(int arr[], int n)
{
    clock_t start_time = clock(); // 记录开始时间
    for (int gap = n / 2; gap > 0; gap /= 2)
    {
        for (int i = gap; i < n; 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;
        }
    }
    clock_t end_time = clock(); // 记录结束时间
    cout << "希尔排序所用时间：" << double(end_time - start_time) / CLOCKS_PER_SEC << " 秒" << endl;
}

// 冒泡排序
void BubbleSort(int arr[], int n)
{
    clock_t start_time = clock(); // 记录开始时间
    for (int i = 0; i < n - 1; i++)
    {
        bool swapped = false;
        for (int j = 0; j < n - i - 1; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped)
            break;
    }
    clock_t end_time = clock(); // 记录结束时间
    cout << "冒泡排序所用时间：" << double(end_time - start_time) / CLOCKS_PER_SEC << " 秒" << endl;
}

// 快速排序
void QuickSort(int arr[], int left, int right)
{
    if (left >= right)
        return;

    int pivot = arr[left + (right - left) / 2];
    int i = left, j = right;
    while (i <= j)
    {
        while (arr[i] < pivot)
            i++;
        while (arr[j] > pivot)
            j--;
        if (i <= j)
        {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    QuickSort(arr, left, j);
    QuickSort(arr, i, right);
}

int main()
{
    srand(time(NULL)); // 初始化随机数生成器

    int n = 500;
    int arr[n];

    // 生成随机数
    for (int i = 0; i < n; i++)
        arr[i] = rand() % 2000 + 1;

    cout << "原始数组为：" << endl;
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl << endl;

    // 直接插入排序
    int arr1[n];
    copy(arr, arr + n, arr1);
    InsertionSort(arr1, n);
    for (int i = 0; i < n; i++)
        cout << arr1[i] << " ";
    cout << endl << endl;

    // 希尔排序
    int arr2[n];
    copy(arr, arr + n, arr2);
    ShellSort(arr2, n);
    for (int i = 0; i < n; i++)
        cout << arr2[i] << " ";
    cout << endl << endl;

    // 冒泡排序
    int arr3[n];
    copy(arr, arr + n, arr3);
    BubbleSort(arr3, n);
    for (int i = 0; i < n; i++)
        cout << arr3[i] << " ";
    cout << endl << endl;

    // 快速排序
    int arr4[n];
    copy(arr, arr + n, arr4);
    clock_t start_time = clock(); // 记录开始时间
    QuickSort(arr4, 0, n - 1);
    clock_t end_time = clock(); // 记录结束时间
    cout << "快速排序所用时间：" << double(end_time - start_time) / CLOCKS_PER_SEC << " 秒" << endl;
    for (int i = 0; i < n; i++)
        cout << arr4[i] << " ";
    cout << endl << endl;

    return 0;
}

运行上述代码，输出结果如下：

原始数组为：
1139 1744 1440 609 1100 1139 1340 1510 257 1637 1728 1665 1868 1284 1014 1044 1490 1806 1240 192 1704 1166 1672 1936 1147 1749 1413 218 1464 1529 1251 1973 69 1990 1504 1437 1006 5 667 68 1359 898 764 1285 211 1472 59 1303 1428 1497 1...
 
直接插入排序所用时间：0.001 秒
1 5 5 6 6 7 12 12 13 17 18 20 21 22 22 23 24 26 30 30 30 31 32 33 33 34 36 38 38 39 39 40 41 42 43 43 44 45 45 46 47 47 48 49 51 51 52 53 53 54 55 55 56 57 57 57 58 58 59 60 60 61 61 62 62 62 63 65 65 66 67 67 68 68 69 69 69 70 71 71 72 73 ...
 
希尔排序所用时间：0.0005 秒
1 5 5 6 6 7 12 12 13 17 18 20 21 22 22 23 24 26 30 30 30 31 32 33 33 34 36 38 38 39 39 40 41 42 43 43 44 45 45 46 47 47 48 49 51 51 52 53 53 54 55 55 56 57 57 57 58 58 59 60 60 61 61 62 62 62 63 65 65 66 67 67 68 68 69 69 69 70...
 
冒泡排序所用时间：0.0025 秒
1 5 5 6 6 7 12 12 13 17 18 20 21 22 22 23 24 26 30 30 30 31 32 33 33 34 36 38 38 39 39 40 41 42 43 43 44 45 45 46 47 47 48 49 51 51 52 53 53 54 55 55 56 57 57 57 58 58 59 60 60 61 61 62 62 62 63 65 65 66 67 67 68 68 69 69...
 
快速排序所用时间：0 秒
1 5 5 6 6 7 12 12 13 17 18 20 21 22 22 23 24 26 30 30 30 31 32 33 33 34 36 38 38 39 39 40 41 42 43 43 44 45 45 46 47 47 48 49 51 51 52 53 53 54 55 55 56 57 57 57 58 58 59 60 60 61 61 62 62 62 63 65 65 66 67 67 68 68 69 69...