精华内容
下载资源
问答
  • 多线程快速排序

    2013-09-05 16:27:48
    多线程快速排序,应付网络编程的小作业是个好东西!
  • 为实现多线程快速排序,提出基于Fork/Join框架的多线程快速排序,同时对排序算法进行优化。该算法主要用于大量数据需要进行排序处理的应用。
  • 基于Java的多线程快速排序设计与优化.pdf
  • 这是在WINDOWS下实现的多进程多线程快速排序程序,其中为了加快排序速度使用了文件映射技术。
  • 这是一个使用了多线程快速排序算法的源代码,如果CPU和内存足够,在32位平台下,最大可以对5亿个int数据进行排序(考虑系统本身所需的内存,程序本身运行所需的内存)。 不支持文件。 待排序的数据由程序自动生成...
  • QT多线程快速排序

    千次阅读 2016-09-06 09:17:55
    //测试多线程版本快排 MyThread *myThread = new MyThread(0, N); QObject::connect(myThread, &MyThread::ok, [=]() { ofstream fout("out.txt"); for (int i = 0; i ; i++) fout [i] ; fout ; fout.close();...

    //MyThread.h

    #ifndef MYTHREAD_H
    #define MYTHREAD_H
    
    #include <QThread>
    #include <QMutex>
    #include <QSemaphore>
    
    class MyThread : public QThread
    {
        Q_OBJECT
    public:
        MyThread(int lo, int hi, QObject *parent = 0);
        ~MyThread();
    
    signals:
        void ok();
    
    protected:
        void run();
    
    private:
        static QMutex numMutex;
        static int num;
    
        int lo, hi;
    
        QMutex mutex;
        int nFinished;
    
        MyThread *threadL, *threadR;
    };
    
    #endif // MYTHREAD_H
    


    //MyThread.cpp

    #include "mythread.h"
    #include <cstdlib>
    #include <algorithm>
    #include <QMutexLocker>
    #include <QDebug>
    #define N 10000000
    using namespace std;
    
    QMutex     MyThread::numMutex;
    int        MyThread::num = 0;
    
    extern int arr[N];
    
    MyThread::MyThread(int lo, int hi, QObject *parent)
        : lo(lo), hi(hi), QThread(parent), nFinished(0)
    {
        connect(this, SIGNAL(ok()), this, SLOT(deleteLater()));
    }
    
    MyThread::~MyThread()
    {
        threadL->wait();
        threadR->wait();
        QMutexLocker locker(&numMutex);
        num--;
    }
    
    void MyThread::run()
    {
    //如果线程数目超过30个就不再创建新线程,正常快排,为了省事直接调用了std::sort
        {
            QMutexLocker locker(&numMutex);
            num++;
            if (num >= 30)
            {
                sort(arr + lo, arr + hi);
                emit ok();
                return;
            }
        }
    
    //递归基
        if (hi - lo < 2)
        {
            emit ok();
            return;
        }
    
    //分段
        int mid = lo;
        for (int i = lo + 1; i < hi; i++)
            if (arr[i] < arr[lo]) swap(arr[++mid], arr[i]);
        swap(arr[lo], arr[mid]);
    
    //创建新线程,注意这里不能采用“给MyThread定义槽函数”的做法,因为线程类的槽函数会在主线程里执行。为此我用了lambda表达式
        threadL = new MyThread(lo, mid);
        connect(threadL, &MyThread::ok, [&]() {
            QMutexLocker locker(&mutex);
            nFinished++;
            if (nFinished == 2)
                emit ok();
        });
    
        threadR = new MyThread(mid + 1, hi);
        connect(threadR, &MyThread::ok, [&]() {
            QMutexLocker locker(&mutex);
            nFinished++;
            if (nFinished == 2)
                emit ok();
        });
    
        threadL->start();
        threadR->start();
    }
    

    //main.cpp

    #include <QObject>
    #include <fstream>
    #include <ctime>
    #include <qDebug>
    #include <iostream>
    #include <algorithm>
    #define N 10000000
    
    #include <QCoreApplication>
    #include "mythread.h"
    using namespace std;
    
    int arr[N];
    
    int main(int argc, char *argv[])
    {
        QCoreApplication a(argc, argv);
    
        srand(time(NULL));
        for (int i = 0; i < N; i++) arr[i] = rand() % N;
    
    //测试多线程版本快排
        MyThread *myThread = new MyThread(0, N);
        QObject::connect(myThread, &MyThread::ok, [=]() {
            ofstream fout("out.txt");
            for (int i = 0; i < N; i++)
                fout << arr[i] << ' '; fout << endl;
            fout.close();
    
            qDebug() << "ok threads";
        });
        myThread->start();
    
    //测试标准库版本快排
        qsort(arr, N, sizeof(int), [=](const void *a, const void *b) {
            return *(int *)a - *(int *)b;
        });
        qDebug() << "ok std";   // 似乎还是这个比较快
    
        return a.exec();
    }
    


    展开全文
  • 归 并 方 式 的 线 程 快 速 排 序算法
  • 描述 ...如果申请的线程数大于对应的CPU核数的时候,就是没有意义的,反而有可能导致效率会降低。 代码 #include &lt;iostream&gt; using namespace std; #include &lt;Windows...

    描述

    这里对于对于每个快排递归过程都进行考量,如果对应的区域规模达到一定数值(也就是下面的代码中的MINLEN),设置这个,主要是考虑到对应的电脑的cpu的核数。如果申请的线程数大于对应的CPU核数的时候,就是没有意义的,反而有可能导致效率会降低。

    代码

    #include <iostream>
    using namespace std;
    #include <Windows.h>
    #include <ctime>
    #include <random>
    #include <thread>
    #include <vector>
    
    int *a;
    int N;
    const int MINLEN = 120000;
    
    void random_test(int begin, int end) {
        srand((unsigned)time(NULL) + begin);
        for (int i = begin; i < end; ++i) {
            a[i] = rand() % N;
        }
    }
    
    void sort(int s, int e) {
        if (s >= e)
            return;
        int i = s, j = e, k = a[s];
        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;
        vector<thread> vt;
        if (i - s >= MINLEN)vt.push_back(thread(sort, s, i - 1));
        else sort(s, i - 1);
    
        if (e - i >= MINLEN)vt.push_back(thread(sort, i + 1, e));
        else sort(i + 1, e);
    
        for (int i = 0; i < vt.size(); ++i) vt[i].join();
    }
    
    int main() {
        vector<thread> vt;
        N = 1000000;
        a = new int[N];
        int T = 5;
    
        int st, et;
        st = clock();
        for (int i = 0; i < T; ++i)
            vt.push_back(thread(random_test, i * N / T, (i + 1) * N / T));
        for (int i = 0; i < T; ++i)
            vt[i].join();
        et = clock();
        double ct = (et - st) / 1000.0;
        st = clock();
        sort(0, N-1);
        et = clock();
        /*for (int i = 0; i < N; ++i) cout << a[i] << " ";
        cout << endl;*/
        cout << "Sorting uses " << (et - st) / 1000.0 << " second(s)" << endl;
    
        cout << "Creating the random array uses " << ct << " second(s)" << endl;
        system("pause");
    }
    展开全文
  • c++11 版多线程 快速排序

    千次阅读 2014-08-18 16:36:23
    // First.cpp : 定义控制台应用程序的入口点。 #include "stdafx.h" #include #include #include #include #include #include #include #include using namespace std; /** @ return the ...in
    // First.cpp : 定义控制台应用程序的入口点。
    #include "stdafx.h"
    #include <iostream>
    #include <algorithm>
    #include <iterator>
    #include <ctime>
    #include <random>
    #include <thread>
    #include <mutex>
    #include <memory>
    using namespace std;
    /** @ return the position of x  */
    int partition(int arr[], int beg, int end){   /**  0,1,2,3,...,end*/
    	int ramdom_index = rand() % (end - beg + 1) + beg;
    	swap(arr[beg], arr[end]);
    	int x = arr[beg];
    	size_t i = beg + 1;
    	for (size_t j = beg + 1; j <= end; j++){
    		if (arr[j] < x)
    			swap(arr[i++], arr[j]);
    	}
    	swap(arr[beg], arr[--i]);
    	return i;
    }
    
    //void quickSort(int arr[], int beg, int end){
    //	if (beg < end){
    //		int mid = partition(arr, beg, end);
    //		quickSort(arr, beg, mid - 1);
    //		quickSort(arr, mid + 1, end);
    //
    //	}
    //	/** return if(beg >= end) */
    //}
    size_t size = 10000000;
    const int minSizeOfPerThread = 100000;
    static int threadNum = 0;
    mutex mu;
    void quickSort(int arr[], int beg, int end){
    	if (beg < end){
    		int mid = partition(arr, beg, end);
    		if (mid - beg > minSizeOfPerThread){
    			thread thr1(quickSort, ref(arr), beg, mid - 1);
    			thread thr2(quickSort, ref(arr), mid + 1, end);
    			thr1.join();
    			thr2.join();
    			lock_guard<mutex>muguard(mu);
    			threadNum += 2;
    		}
    		else
    		{
    			quickSort(ref(arr), beg, mid - 1);
    			quickSort(ref(arr), mid + 1, end);
    
    		}
    	}
    
    	/** return if(beg >= end) */
    
    }
    
    
    void test(){
    	unique_ptr<int[]>testArr0(new int[size]);
    	for (size_t i = 0; i < size; ++i)
    		testArr0[i] = rand();
    
    	time_t timeStart = clock();
    	quickSort(testArr0.get(), 0, size - 1);
    	time_t timeEnd = clock();
    
    	cout << "sort time is " << (timeEnd - timeStart) << endl;
    
    	/*for (size_t i = 0; i < size; ++i)
    		cout << testArr0[i] << " ";
    	*/cout << "test over\n" << endl;
    	cout << "threadNum Is " << threadNum << endl;
    
    
    }
    
    void test2(){
    	unique_ptr<int[]>testArr0(new int[size]);
    	for (size_t i = 0; i < size; ++i)
    		testArr0[i] = rand();
    	time_t timeStart = clock();
    	sort(testArr0.get(), testArr0.get() + size - 1);
    	time_t timeEnd = clock();
    	cout << "sort time is " << (timeEnd - timeStart) << endl;
    
    
    	
    	/*for (size_t i = 0; i < size; ++i)
    	cout << testArr0[i] << " ";
    	*/cout << "test over\n" << endl;
    
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	test();
    	test2();
    	system("pause");
    	return 0;
    }
    


    展开全文
  • 使用多线程 实现冒泡排序,选择排序,快速排序
  • 多线程排序+快速排序

    万次阅读 2017-05-24 20:07:48
    多线程排序,主要是将整个排序的序列分成若干份,每一个线程排序一份,所以线程排序完成之后,就进行归并,相当于多个有序序列合并成一个有序序列。 这里就需要用到线程屏障,也就是 pthread_barrier 系列函数...

    多线程排序,主要是将整个排序的序列分成若干份,每一个线程排序一份,所以线程排序完成之后,就进行归并,相当于多个有序序列合并成一个有序序列。


    这里就需要用到线程屏障,也就是 pthread_barrier 系列函数。

    屏障,通俗的说就是一个比赛跑步的过程,所以队员就绪了,才能进行比赛。

    多线程排序也是,需要每个线程都是排序完成后,才能进行合并的过程。


    代码:

    #include <cstdio>
    #include <cstring>
    #include <iostream>
    #include <cstdlib>
    #include <sys/time.h>
    #include <pthread.h>
    #include <algorithm>
    using namespace std;
    
    const long MAX = 10000000L;  //数组中最大数
    const long long MAX_NUM = 100000000L;  //排序数
    const int thread = 4;       //线程数
    const int thread_num = MAX_NUM / thread;  //每个线程排序的个数
    
    int num[MAX_NUM];
    int tmp_num[MAX_NUM];
    
    pthread_barrier_t barrier;
    
    /**
     * Initialized Data
     */
    void init()
    {
    	srandom((int)time(NULL));
    	for(int i = 0; i < MAX_NUM; ++i)
    		num[i] = random() % MAX;
    }
    
    /**
     *quick sort function
     */
    void qsorts(int *start, int *end)
    {	
    	int nums = end - start;
    	if(nums > 0)
    	{
    		int index = 0;
    		int flag = start[0];
    		int i = 0, j = nums;
    		while(i != j)
    		{
    			while(j > i && start[j] >= flag)
    				--j;
    			start[index] = start[j];
    			index = j;
    			while(i < j && start[i] <= flag)
    				++i;
    			start[index] = start[i];
    			index = i;
    		}
    		start[index] = flag;
    		qsorts(start, start + (i - 1));
    		qsorts(start + j + 1, end);
    	}
    }
    
    void* work(void *arg)  //线程排序函数
    {
    	long index = (long)arg;
    	qsorts(num + index, num + index + thread_num - 1);
    	pthread_barrier_wait(&barrier);
    	pthread_exit(NULL);
    }
    
    void meger()        //最终合并函数
    {
    	long index[thread];
    	for (int i = 0; i < thread; ++i)
    	{
    		index[i] = i * thread_num;
    	}
    
    	for(long i = 0; i < MAX_NUM; ++i)
    	{
    		long min_index;
    		long min_num = MAX;
    		for(int j = 0; j < thread; ++j)
    		{
    			if((index[j] < (j + 1) * thread_num) 
    				&& (num[index[j]] < min_num))
    			{
    				min_index = j;
    				min_num = num[index[j]];
    			}
    		}
    		tmp_num[i] = num[index[min_index]];
    		index[min_index]++;
    	}
    }
    
    int main(int argc, char const *argv[])
    {
    	init();
    	
    	struct timeval start, end;
    	pthread_t ptid;
    	//printf("%ld %ld\n", num[1], num[2]);
    	gettimeofday(&start, NULL);
    
    	//init pthread and Thread barrier
    	//add 1, total have (thread + 1) threads.
    	pthread_barrier_init(&barrier, NULL, thread + 1);
    	for(int i = 0; i < thread; ++i)
    		pthread_create(&ptid, NULL, work, (void *)(i * thread_num));
    
    	pthread_barrier_wait(&barrier);
    
    	meger();
    	// use one thread to sort
    	// qsorts(num, num + MAX_NUM - 1);
    
    	gettimeofday(&end, NULL);
    	long long s_usec = start.tv_sec * 1000000 + start.tv_usec;
    	long long e_usec = end.tv_sec * 1000000 + end.tv_usec;
    
    	double useTime = (double)(e_usec - s_usec) / 1000000.0;
    	printf("sort use %.4f seconds\n", useTime);
    
    
    	FILE *fp = fopen("result2.txt", "w+");
    	for(long long i = 0; i < MAX_NUM; ++i)
    		fprintf(fp, "%ld ", num[i]);
    
    	return 0;
    }

    当使用单线程排序时:

    sort use 34.0476 seconds

    当使用2线程排序时:

    sort use 19.7711 seconds

    当使用4线程排序时:

    sort use 16.0659 seconds

    当使用8线程排序时:

    sort use 16.8172 seconds

    如果使用STL中的函数的sort,将会更快。




    展开全文
  • 多线程实现快速排序

    千次阅读 2019-04-28 18:01:04
    多线程排序,主要是将整个排序的序列分成若干份,每一个线程排序一份,所以线程排序完成之后,就进行归并,相当于多个有序序列合并成一个有序序列。 这里就需要用到线程屏障,也就是pthread_barrier 系列函数。 ...
  • 操作系统经典实验:多线程实现排序冒泡排序与快速排序,C++编写,简单易懂
  • 上次传错了,这次绝对不会错了.比较适合新手哦.多线程的东西其实不要想得太复杂,自己亲手做了就会明白的
  • 下面就让我们用多线程验证一下,具体操作:先产生一个随机整数n(大于10),再产生n个随机正数存放于数组中,然后创建两个线程并发地对锁生成的随机整数进行排序,其中一个线程采用冒泡排序,另一个线程采用快速排序...
  • runQuickSort() { //使用单个线程排序 System. out .println(System. currentTimeMillis ()); quickSort( data , 0 , data . length - 1 ); for ( int i= 0 ;i data . length ;i++) { //System.out.print...
  • 多线程实现排序算法的比较:希尔排序、快速排序、堆排序。用java语言实现,很经典,需要的可以下载看看!
  • 高分悬赏:Java语言利用多线程实现快速排序,首先生成1000个随机数,用10个线程排序
  • 在VC环境下产生线程,对一个随机数文件进行快速排序。代码完整,绝对可编译通过。
  • 基于多线程的并行快速排序算法实现 1. 快速算法(Quick Sort)介绍 快速排序(Quick Sort)是一种经典的排序算法,基于递归实现,由于其实现方式简单可靠、平均时间复杂度为O(nlogn) (最坏情况O(n^2)), 被广泛采用。...
  • java多线程排序

    热门讨论 2008-07-02 09:37:17
    java多线程排序源程序,三种排序算法。希尔排序,快速排序,堆排序。
  • VC++多线程实现三种排序算法比较----冒泡排序、快速排序、归并排序,很有意思,可以下载看看!
  • 这是一个简单的运用多线程的程序 主要对快速排序等多个算法进行比较
  • 多线程排序-真香

    千次阅读 2019-12-25 21:00:17
    ​来源:公众号【编程珠玑】 作者:守望先生 ID:shouwangxiansheng 在《系统编程-多线程》中... 每个线程对其中的一组数据使用库函数提供的快速排序算法 所有线程排序完成后,将每组排序好的数组合并 ...
  • 多线程进行的序列快速排序

    千次阅读 2017-07-16 19:11:42
    本质上是选择最前面的一个数作为分割线,以此为分割。 在此基础上进行迭代,终点关注下使用lambda表达式 [&](T...下面是原始的快速排序代码 template list sequential_quick_sort(list input) { if (input.empt
  • 操作系统实验,通过多线程实现 冒泡排序和快速排序算法,直观的现实每种排序的过程
  • Linux 下多线程排序的实现

    千次阅读 2016-04-01 15:57:56
    首先,说一下总体的思路:将元素分成n段,使用快速排序多线程并行处理。最后需要等待这些线程都将分段排好序之后,进行类似归并排序的过程。 这样时间复杂度算下来是(假设我是4核的机器) O(n+n/4log(n/4)),比O...
  • 由于最近在学习C++从底层(指针,对象模型,内存管理)再到网络socket编程,多线程编程,数据库编程等方面知识,需要从Java慢慢的迁移过来。这是以前学习Java的学习路线,所以就把原来Java的做的项目全部用C++重新实现...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 108,700
精华内容 43,480
关键字:

多线程快速排序