多线程随机数组生成+双线程快速排序（C++实现）（0.2秒排100W个数字）

末蓝、 2022-05-22 02:36 134阅读 0赞

## 简述 ##

用很多个线程进行随机数的生成  
用两个线程来进行数组的排序

基于的算法是快速排序算法。  
基本可以做到  
**0.2秒左右的时间排完100W个数字**

#include <iostream>
    using namespace std;
    #include <thread>
    #include <ctime>
    #include <random>
    int* a;
    int N;
    
    void random_arr(int begin, int end) {
        srand(time(NULL) + begin);
        for (int i = begin; i < end; ++i) a[i] = rand() % N;
    }
    
    void QSort(int begin, int end) {
        if (begin >= end - 1) return;
        int i = begin, j = end-1, k = a[i];
        while (i < j) {
            while (i < j && a[j] >= k) j--;
            if (i < j) a[i++] = a[j];
            while (i < j && a[i] <= k) i++;
            if (i < j) a[j--] = a[i];
        }
        a[i] = k;
        QSort(begin, i);
        QSort(i + 1, end);
    }
    
    void QSortThread(int begin, int end) {
        if (begin >= end - 1) return;
        int i = begin, j = end - 1, k = a[i];
        while (i < j) {
            while (i < j && a[j] >= k) j--;
            if (i < j) a[i++] = a[j];
            while (i < j && a[i] <= k) i++;
            if (i < j) a[j--] = a[i];
        }
        a[i] = k;
        thread thArr[2];
        thArr[0] = thread(QSort, begin, i);
        thArr[1] = thread(QSort, i + 1, end);
        for (i = 0; i < 2; ++i) thArr[i].join();
    }
    
    int main() {
        N = 1000000;
        a = new int[N];
        const int T = 5;
        thread arr[T];
        int st, et, ct;
        st = clock();
        for (int i = 0; i < T; ++i) arr[i] = thread(random_arr, i * N / T, (i + 1) * N / T);
        for (int i = 0; i < T; ++i) arr[i].join();
        et = clock();
        ct = et - st;
        st = clock();
        QSortThread(0, N);
        et = clock();/* for (int i = 0; i < N; ++i) cout << a[i] << " "; cout << endl;*/
        cout << "Sort " << (et - st) / 1000.0 << " Second(s)" << endl;
        cout << "Create " << ct / 1000.0 << " Second(s)" << endl;
        system("pause");
        delete[] a;
    }