多线程生成随机数组+双线程归并排序（C++实现）

╰+哭是因爲堅強的太久メ 2022-05-23 10:43 199阅读 0赞

## 算法概述 ##

*  动态数组生成
 *  多线程随机数组生成
 *  双线程归并排序

## 代码 ##

#include <iostream>
    #include <thread>
    #include <ctime>
    #include <vector>
    #include <mutex>
    using namespace std;
    
    int* arrays;
    int N;
    int T;
    // begin_index: where the thread begins to put number in
    // end_index: where the thread stops putting number in
    void run_test(int begin_index, int end_index)
    {
        srand((unsigned)time(NULL) + begin_index);
        for (int i = begin_index; i<end_index; i++)
            arrays[i] = rand() % N;
    }
    
    void Merge(int begin_index, int mid_index, int end_index);
    
    void M_SORT_f(int begin_index, int end_index) {
        if (begin_index >= end_index - 1) return;
        int mid = (end_index + begin_index) / 2;
        M_SORT_f(begin_index, mid);
        M_SORT_f(mid, end_index);
        Merge(begin_index, mid, end_index);
    }
    
    void M_SORT(int begin_index, int end_index)
    {
        M_SORT_f(begin_index, end_index);
    }
    
    void Merge(int begin_index, int mid_index, int end_index) {
        if (begin_index >= end_index - 1) return;
        int *temp = new int[end_index - begin_index];
        int i = begin_index, j = mid_index, k = 0;
        while (i < mid_index && j < end_index) {
            if (arrays[i] < arrays[j])
                temp[k++] = arrays[i++];
            else
                temp[k++] = arrays[j++];
        }
        while (i < mid_index) temp[k++] = arrays[i++];
        while (j < end_index) temp[k++] = arrays[j++];
    
        for (int t = begin_index; t < end_index; ++t) arrays[t] = temp[t - begin_index];
        delete[] temp;
    }
    
    int main()
    {
        N = 100000;
        T = 10;
        _ASSERT(N >= T);
        cout << "Array Building.\n";
    
        arrays = new int[N];
        cout << "Array Build Finished.\n";
    
        // Ignore thread creation, join action, vector<thread> for now
        vector<thread> vt;
        // create T threads and push them into a vector
        // each thread will be running the function "run_test"
        for (int i = 0; i<T; i++)
            vt.push_back(thread(run_test, i*N / T, (i + 1)*N / T));
    
        for (int i = 0; i<T; i++)
            vt[i].join();
        vt.clear();
    
        T = 2;
        for (int i = 0; i<T; i++)
            vt.push_back(thread(M_SORT, i*N / T, (i + 1)*N / T));
        for (int i = 0; i<T; i++)
            vt[i].join();
        Merge(0, N / T, N);
        for (int i = 0; i < N; ++i) cout << arrays[i] << " ";
        cout << endl;
    
        delete[] arrays;
        system("pause");
        return 0;
    }

**也可以是下面的代码**

#include <iostream>
    #include <thread>
    #include <ctime>
    #include <vector>
    #include <mutex>
    #include <ctime>
    using namespace std;
    
    int* arrays;
    int N;
    int T;
    // begin_index: where the thread begins to put number in
    // end_index: where the thread stops putting number in
    void run_test(int begin_index, int end_index)
    {
        srand((unsigned)time(NULL) + begin_index);
        for (int i = begin_index; i<end_index; i++)
            arrays[i] = rand() % N;
    }
    
    void Merge(int begin_index, int mid_index, int end_index);
    
    void M_SORT(int begin_index, int end_index) {
        if (begin_index >= end_index - 1) return;
        int mid = (end_index + begin_index) / 2;
        M_SORT(begin_index, mid);
        M_SORT(mid, end_index);
        Merge(begin_index, mid, end_index);
    }
    
    void Merge(int begin_index, int mid_index, int end_index) {
        if (begin_index >= end_index - 1) return;
        int *temp = new int[end_index - begin_index];
        int i = begin_index, j = mid_index, k = 0;
        while (i < mid_index && j < end_index) {
            if (arrays[i] < arrays[j])
                temp[k++] = arrays[i++];
            else
                temp[k++] = arrays[j++];
        }
        while (i < mid_index) temp[k++] = arrays[i++];
        while (j < end_index) temp[k++] = arrays[j++];
    
        for (int t = begin_index; t < end_index; ++t) arrays[t] = temp[t - begin_index];
        delete[] temp;
    }
    
    int main()
    {
        N = 1000000;
        T = 10;
        _ASSERT(N >= T);
        cout << "Array Building.\n";
    
        arrays = new int[N];
        cout << "Array Build Finished.\n";
    
        // Ignore thread creation, join action, vector<thread> for now
        vector<thread> vt;
        // create T threads and push them into a vector
        // each thread will be running the function "run_test"
        for (int i = 0; i<T; i++)
            vt.push_back(thread(run_test, i*N / T, (i + 1)*N / T));
    
        for (int i = 0; i<T; i++)
            vt[i].join();
        vt.clear();
    
        T = 2;
        for (int i = 0; i<T; i++)
            vt.push_back(thread(M_SORT, i*N / T, (i + 1)*N / T));
        for (int i = 0; i<T; i++)
            vt[i].join();
        int st, et;
        st = clock();
        Merge(0, N / T, N);
        et = clock();
        /*for (int i = 0; i < N; ++i) cout << arrays[i] << " "; cout << endl; */
        cout << "time: " << (et - st) / 1000.0 << " second(s)\n";
        delete[] arrays;
        system("pause");
        return 0;
    }