为什么百万级的没有运行结果

Question

#include <iostream>
#include <time.h>
#include <assert.h>
#include <cstdlib>

using namespace std;

clock_t start, stop; // clock_t是clock()函数返回的变量类型
double duration;

// 冒泡排序
void sort1(int a[], int n) {
    int i, j, temp;
    int flag;
    for (i = 0; i < n - 1; i++) {
        flag = 0;
        for (j = n - 1; j > i; j--) {
            if (a[j - 1] > a[j]) {
                temp = a[j - 1];
                a[j - 1] = a[j];
                a[j] = temp;
                flag = 1;
            }
        }
        if (flag == 0) break;
    }
}

// 快速排序
int partition(int arr[], int left, int right) { // 找基准数 划分
    int i = left + 1;
    int j = right;
    int temp = arr[left];

    while (i <= j) {
        while (arr[i] < temp) {
            i++;
        }
        while (arr[j] > temp) {
            j--;
        }
        if (i < j)
            swap(arr[i++], arr[j--]);
        else i++;
    }
    swap(arr[j], arr[left]);
    return j;
}

void quick_sort(int arr[], int left, int right) {
    if (left >= right)
        return;
    int j = partition(arr, left, right);
    quick_sort(arr, left, j - 1);
    quick_sort(arr, j + 1, right);
}

// 堆排序
void AdjustDown(int a[], size_t n, int root) {
    size_t parent = root;
    size_t child = parent * 2 + 1;
    while (child < n) {
        if (child + 1 < n && a[child + 1] > a[child]) {
            ++child;
        }
        if (a[child] > a[parent]) {
            swap(a[child], a[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

void HeapSort(int a[], size_t n) {
    assert(a);
    int parent = (n - 2) >> 1;
    // 建堆
    for (; parent >= 0; --parent) {
        AdjustDown(a, n, parent);
    }
    for (int i = n - 1; i >= 0; --i) {
        swap(a[0], a[i]);
        AdjustDown(a, i, 0);
    }
}

// 选择排序
void selectSort(int a[], int len) {
    int minindex, temp;
    for (int i = 0; i < len - 1; i++) {
        minindex = i;
        for (int j = i + 1; j < len; j++) {
            if (a[j] < a[minindex])
                minindex = j;
        }
        temp = a[i];
        a[i] = a[minindex];
        a[minindex] = temp;
    }
}

void test_sorting_algorithms(int size) {
    int* a = new int[size];
    
    cout << "生成" << size << "个随机数" << endl << endl;
    for (int i = 0; i < size; i++) {
        a[i] = rand() % size;
    }

    int* temp = new int[size];
    memcpy(temp, a, size * sizeof(int));
    start = clock();
    sort1(temp, size);
    stop = clock();
    duration = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << "冒泡排序运行时间是：" << duration << "秒" << endl << endl;

    memcpy(temp, a, size * sizeof(int));
    start = clock();
    quick_sort(temp, 0, size - 1);
    stop = clock();
    duration = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << "快速排序运行时间是：" << duration << "秒" << endl << endl;

    memcpy(temp, a, size * sizeof(int));
    start = clock();
    HeapSort(temp, size);
    stop = clock();
    duration = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << "堆排序运行时间是：" << duration << "秒" << endl << endl;

    memcpy(temp, a, size * sizeof(int));
    start = clock();
    selectSort(temp, size);
    stop = clock();
    duration = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << "选择排序运行时间是：" << duration << "秒" << endl << endl;

    delete[] a;
    delete[] temp;
}

int main() {
    srand(time(0));

    test_sorting_algorithms(10);
    test_sorting_algorithms(100);
    test_sorting_algorithms(10000);
    test_sorting_algorithms(1000000);

    return 0;
}

为什么百万级的没有运行结果

Answer 1

引自免费微信小程序：皆我百晓生

对于你提供的C++排序算法测试程序，当尝试对百万级别的数据进行排序时，程序可能没有输出结果的原因有几点，这通常与性能瓶颈、资源限制、死锁或是算法效率低下有关。在当前的情境下，主要关注的是算法效率和资源消耗。

算法效率分析

1. 冒泡排序：O(n^2)的时间复杂度，在百万级别数据量面前，其计算时间将非常长，可能会导致程序看起来像是没有响应。
2. 快速排序：平均情况下为O(n log n)，但在最坏情况下（即数组已经是有序的情况下）退化为O(n^2)，虽然这种情况不太常见，但仍然可能导致长时间运行。
3. 堆排序：O(n log n)的时间复杂度，理论上比快速排序更稳定，但由于堆的调整操作，实际运行时间也可能较长。
4. 选择排序：O(n^2)的时间复杂度，与冒泡排序类似，效率极低。

资源限制

• 内存分配：创建和操作一个包含一百万个整数的数组需要大量的内存。如果系统可用内存不足，这可能导致程序崩溃或操作系统为了腾出空间而进行频繁的磁盘交换操作，显著降低性能。
• CPU使用率：在处理大量数据时，算法的高CPU使用率可能导致操作系统对进程进行调度，将其挂起以便让给其他任务，这也可能导致程序看起来卡住。

解决方案建议

1. 优化算法：对于大规模数据集，可以考虑使用更高效的排序算法，如归并排序或Timsort（Python的内置排序算法），它们通常具有更好的最坏情况时间复杂度O(n log n)。

2. 分治策略：将大问题分解成小问题解决，例如使用并行处理技术，将数据分割成多个部分并同时在不同的处理器核心上执行排序，最后合并结果。

3. 外部排序：如果内存不足以容纳所有数据，可以考虑使用外部排序算法，它将数据存储在磁盘上，并在需要时读取和写入数据块。

4. 使用高效的数据结构：例如，使用std::vector代替new和delete操作，std::vector在内部管理内存，能更有效地处理动态大小的数组。

5. 利用现代C++特性：使用C++标准库中的std::sort，它可以提供比手写算法更优的性能，因为它是高度优化过的。

6. 性能监控：使用性能分析工具（如gprof、valgrind等）来检查程序的性能瓶颈，了解CPU使用率、内存使用情况以及可能的优化点。

为了应用上述建议，这里给出一个修改后的示例，使用std::sort来替换原有的排序算法：

#include <iostream>
#include <vector>
#include <algorithm> // For std::sort
#include <ctime>
#include <cassert>

using namespace std;

void test_sorting_algorithms(int size) {
    vector<int> a(size);
    
    cout << "生成" << size << "个随机数" << endl << endl;
    for (int i = 0; i < size; i++) {
        a[i] = rand() % size;
    }

    auto start = clock();
    sort(a.begin(), a.end()); // 使用std::sort
    auto stop = clock();
    double duration = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << "标准库排序运行时间是：" << duration << "秒" << endl << endl;
}

int main() {
    srand(time(0));

    test_sorting_algorithms(10);
    test_sorting_algorithms(100);
    test_sorting_algorithms(10000);
    test_sorting_algorithms(1000000);

    return 0;
}

通过使用std::sort，我们可以期望在处理大规模数据时获得更好的性能表现。