随机数快速排序c++

可以使用C++的STL库中的sort函数对随机数进行排序，其时间复杂度为O(nlogn)。具体实现方法如下：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 3, 1, 6, 9, 4, 7};
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i] << " ";
    }
    return 0;
}

以上代码使用了vector容器存储随机数，并使用sort函数对其进行排序。可以根据实际需要修改容器类型和排序方式。

相关问题

10万个随机数快速排序c++

好的，这里是使用C++实现对10万个随机数进行快速排序的代码：

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

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    const int n = 100000;
    int arr[n];

    srand(time(NULL)); // 设置随机数种子

    // 生成10万个随机数
    for (int i = 0; i < n; i++) {
        arr[i] = rand() % 1000000; // 生成0~999999之间的随机数
    }

    clock_t begin = clock(); // 记录开始时间
    quickSort(arr, 0, n - 1); // 进行快速排序
    clock_t end = clock(); // 记录结束时间

    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;
    cout << "Time elapsed: " << elapsed_secs << " seconds" << endl;

    return 0;
}

这个程序会生成10万个0~999999之间的随机数，然后使用快速排序进行排序，并输出排序后的结果和排序所用的时间。由于数据较大，排序所用的时间可能会比较长。

c++利用桶排序对5000个随机数进行排序

桶排序（Bucket Sort）是一种非比较型整数排序算法，它将元素分布到有限数量的“桶”中，然后对每个桶内的元素分别独立进行排序，最后按顺序合并所有桶的内容。在C++中使用桶排序对大量随机数进行排序的基本步骤如下：

1. **创建桶数组**：首先确定所需的桶的数量，通常选择足够大的值，如5000（这里的5000是个假设数字，实际取决于数据范围）。然后创建一个大小等于这个数量的空数组作为桶。

2. **分配元素到桶**：遍历待排序的5000个随机数，对于每个数，计算它落在哪个桶内。可以使用取模运算找到其在桶中的索引位置。

3. **排序桶中的元素**：对于每一个桶，如果内部元素数量小于或等于某个阈值，可以直接认为是有序的；否则可以使用其他排序算法（如插入排序、快速排序等），对每个桶内的元素进行内部排序。

4. **合并桶**：将所有桶中的元素依次取出并按照它们在原数组中的顺序连接起来，就得到了排序好的序列。

#include <iostream>
#include <vector>
#include <cstdlib> // 需要用到rand()函数

void bucketSort(std::vector<int>& arr, int bucketSize) {
    if (arr.empty()) return; // 如果数组为空，直接返回
    std::vector<std::vector<int>> buckets(bucketSize);
    for (int num : arr) {
        int index = num % bucketSize; // 计算元素落入的桶
        buckets[index].push_back(num); // 将元素放入对应的桶
    }

    for (auto& bucket : buckets) {
        if (!bucket.empty()) {
            sort(bucket.begin(), bucket.end()); // 对每个非空桶进行排序
        }
    }

    int currentIndex = 0;
    for (const auto& bucket : buckets) {
        for (int num : bucket) {
            arr[currentIndex++] = num; // 将已排序的元素合并回原数组
        }
    }
}

// 示例使用
int main() {
    const int n = 5000;
    std::vector<int> randomNumbers(n, 0); // 生成5000个随机数
    // ... (填充随机数)
    bucketSort(randomNumbers, 10); // 假设我们用10个桶
    // 现在randomNumbers数组应该是排序后的
    // ...
    return 0;
}