用C++语言生成一段顺序排序法代码

C 语言中，顺序排序法的代码可以这样编写： for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n-i-1; j++)
{
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}

相关问题

用C++写一段代码 定义待排序表的长度为n。 初始化随机数发生器，产生n个随机数构成的顺序表。 创建输出排序表函数，取得系统时间函数，直接插入排序函数，冒泡排序函数，快速排序函数，直接选择排序函数，筛选函数，对排序函数，归并排序函数。 主程序调用各个排序函数，输出各排序算法对长度为n的顺序表进行排序所耗费的时间为多少毫秒。

以下是C++代码：

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

using namespace std;

void initArray(int a[], int n) {
    srand(time(NULL)); // 初始化随机数发生器
    for (int i = 0; i < n; i++) {
        a[i] = rand() % 100; // 生成0-99之间的随机数
    }
}

void printArray(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl;
}

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

void bubbleSort(int a[], int n) {
    int i, j, temp;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}

void quickSort(int a[], int left, int right) {
    if (left >= right) {
        return;
    }
    int i = left, j = right, pivot = a[(left + right) / 2];
    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, left, j);
    quickSort(a, i, right);
}

void selectionSort(int a[], int n) {
    int i, j, minIndex, temp;
    for (i = 0; i < n - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < n; j++) {
            if (a[j] < a[minIndex]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
    }
}

void sieveSort(int a[], int n) {
    int i, j, temp, k = n / 2;
    while (k >= 1) {
        for (i = k; i < n; i++) {
            temp = a[i];
            j = i - k;
            while (j >= 0 && a[j] > temp) {
                a[j + k] = a[j];
                j -= k;
            }
            a[j + k] = temp;
        }
        k /= 2;
    }
}

void merge(int a[], int left, int mid, int right) {
    int i = left, j = mid + 1, k = 0;
    int temp[right - left + 1];
    while (i <= mid && j <= right) {
        if (a[i] <= a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    while (j <= right) {
        temp[k++] = a[j++];
    }
    for (i = left, k = 0; i <= right; i++, k++) {
        a[i] = temp[k];
    }
}

void mergeSort(int a[], int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = (left + right) / 2;
    mergeSort(a, left, mid);
    mergeSort(a, mid + 1, right);
    merge(a, left, mid, right);
}

int main() {
    int n = 10; // 待排序表的长度
    int a[n]; // 声明顺序表
    initArray(a, n); // 初始化顺序表
    cout << "原始数组：";
    printArray(a, n); // 输出原始顺序表
    clock_t start, end; // 声明计时器
    // 直接插入排序
    start = clock();
    insertionSort(a, n);
    end = clock();
    cout << "直接插入排序后的数组：";
    printArray(a, n);
    cout << "直接插入排序耗时：" << (double)(end - start) / CLOCKS_PER_SEC * 1000 << "毫秒" << endl;
    // 冒泡排序
    initArray(a, n); // 重新初始化顺序表
    start = clock();
    bubbleSort(a, n);
    end = clock();
    cout << "冒泡排序后的数组：";
    printArray(a, n);
    cout << "冒泡排序耗时：" << (double)(end - start) / CLOCKS_PER_SEC * 1000 << "毫秒" << endl;
    // 快速排序
    initArray(a, n); // 重新初始化顺序表
    start = clock();
    quickSort(a, 0, n - 1);
    end = clock();
    cout << "快速排序后的数组：";
    printArray(a, n);
    cout << "快速排序耗时：" << (double)(end - start) / CLOCKS_PER_SEC * 1000 << "毫秒" << endl;
    // 直接选择排序
    initArray(a, n); // 重新初始化顺序表
    start = clock();
    selectionSort(a, n);
    end = clock();
    cout << "直接选择排序后的数组：";
    printArray(a, n);
    cout << "直接选择排序耗时：" << (double)(end - start) / CLOCKS_PER_SEC * 1000 << "毫秒" << endl;
    // 筛选排序
    initArray(a, n); // 重新初始化顺序表
    start = clock();
    sieveSort(a, n);
    end = clock();
    cout << "筛选排序后的数组：";
    printArray(a, n);
    cout << "筛选排序耗时：" << (double)(end - start) / CLOCKS_PER_SEC * 1000 << "毫秒" << endl;
    // 归并排序
    initArray(a, n); // 重新初始化顺序表
    start = clock();
    mergeSort(a, 0, n - 1);
    end = clock();
    cout << "归并排序后的数组：";
    printArray(a, n);
    cout << "归并排序耗时：" << (double)(end - start) / CLOCKS_PER_SEC * 1000 << "毫秒" << endl;
    return 0;
}

实现合并排序算法。要排序的整型数组元素可以用随机数生成器生成，运行程序，分别记录对十万，一百万，五千万，一千万个数据排序所用的时间，列出表格显示统计出来的时间。并单独显示一个100个数据的排序结果。用C++编写，完整且正确的输出代码，写上完整的注释

#include <iostream>
#include <vector>
#include <chrono> // 需要用到高精度时间测量
#include <random> // 随机数生成器

// 合并排序函数，使用分治策略
template<typename T>
void mergeSort(T arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // 找到中间点
        // 分别对左右半部分进行递归排序
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并两个已排序的部分
        merge(arr, left, mid, right);
    }
}

// 合并函数，将两个已排序区间合并回原数组
template<typename T>
void merge(T arr[], int left, int mid, int right) {
    int leftSize = mid - left + 1;
    int rightSize = right - mid;

    T* leftArr = new T[leftSize]; // 左半部分临时数组
    T* rightArr = new T[rightSize]; // 右半部分临时数组

    // 将左、右两边的元素复制到临时数组
    for (int i = 0; i < leftSize; ++i)
        leftArr[i] = arr[left + i];
    for (int j = 0; j < rightSize; ++j)
        rightArr[j] = arr[mid + 1 + j];

    // 按顺序将较小元素放入原数组
    int i = 0, j = 0, k = left;
    while (i < leftSize && j < rightSize) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k++] = leftArr[i++];
        } else {
            arr[k++] = rightArr[j++];
        }
    }

    // 如果有剩余元素，则直接复制未遍历完的那一边
    while (i < leftSize)
        arr[k++] = leftArr[i++]; // 左边剩余
    while (j < rightSize)
        arr[k++] = rightArr[j++]; // 右边剩余

    // 释放临时数组
    delete[] leftArr;
    delete[] rightArr;
}

// 生成随机数组
std::vector<int> generateRandomArray(int size, std::default_random_engine& generator) {
    std::uniform_int_distribution<int> distribution(0, 10000); // 0-10000范围内的随机数
    std::vector<int> arr(size);
    for (int& num : arr)
        num = distribution(generator);
    return arr;
}

// 记录和打印排序时间
void measureAndPrint(const std::string& title, const std::vector<int>& data) {
    auto start = std::chrono::high_resolution_clock::now();
    mergeSort(data.data(), 0, data.size() - 1);
    auto end = std::chrono::high_resolution_clock::now();
    double time_used = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() * 1e-6; // 微秒转换为秒

    std::cout << "Sorted " << title << ": Time taken: " << time_used << " seconds\n";
    std::cout << "Sorted array: ";
    for (const auto& num : data) {
        std::cout << num << ' ';
    }
    std::cout << "\n";
}

int main() {
    std::random_device rd;
    std::mt19937 gen(rd()); // 使用Mersenne Twister随机数生成器
    std::uniform_int_distribution<> distr(0, 100000000); // 0-1亿范围内的随机数

    // 不同规模的数据排序时间测量
    const int sizes[] = {100000, 1000000, 5000000, 10000000};
    std::vector<int> arr[4]; // 用于存储不同大小的数组
    for (size_t i = 0; i < sizeof(sizes) / sizeof(sizes[0]); ++i) {
        arr[i] = generateRandomArray(sizes[i], gen);
        measureAndPrint("Data with " + std::to_string(sizes[i]) + " elements", arr[i]);
    }

    // 单独显示100个数据的排序结果
    std::vector<int> smallArr(100);
    for (auto& num : smallArr)
        num = distr(gen);
    measureAndPrint("Small Data with 100 elements", smallArr);

    return 0;
}

这段代码首先定义了一个`mergeSort`函数用于执行归并排序，然后创建了一个`generateRandomArray`函数用于生成指定长度的随机整数数组。`measureAndPrint`函数负责记录排序时间和打印结果。在`main`函数中，我们生成了不同数量级的数据（10万、100万、500万和1000万）并计算排序所需时间。