某同学写了一个多线程快排，出现了莫名其妙的问题！
今晚自己也花点时间写一个类似的多线程排序代码。对于QuickSort！一直认为，出自不同人的手，在写法上至少那么一点儿的差别。
下面是我最常用的单线程版本的写法，

int quick(int A[], int a, int b)
{
	int l = a, r = b, m = A[(a+b)>>1];
	do{
		while(A[l]<m) ++l;
		while(A[r]>m) --r;
		if(l<=r) swap(A[l++], A[r--]);
	}while(l<r);
	if(a<r) quick(A, a, r);
	if(l<b) quick(A, l, b);
}

我在Linux下使用pthread线程函数库实现多线程的排序。下面是用到的一些多线程相关的结构和函数。

pthread_t：用于存储线程信息的结构。
pthread_mutex_t：线程互斥锁，用于限制只有一个线程访问某些资源。
pthread_create：用于创建一个线程。
pthread_join：等待一个线程的结束。
pthread_mutex_init、pthread_mutex_destroy：对线程互斥锁的初始化与销毁。
pthread_mutex_lock、pthread_mutex_unlock：获取锁和释放锁，用于在临界区域进行操作。

先上代码：

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <pthread.h>
using namespace std;

const int MaxData = 20000000;
const int ThreadCount = 3;
int data[MaxData];
pthread_t threads[ThreadCount];
int threadIndex = 0;
int region[ThreadCount][2];
pthread_mutex_t threadMutex;

int GetThreadNumber()
{
	/* 快速判断是否还有线程需要创建 */
	if(threadIndex >= ThreadCount)
		return -1;
	int threadNumber;
	pthread_mutex_lock(&threadMutex);
	/* 有可能在获得锁之后，threadIndex已经被其他线程修改过，所以务必检查一次 */
	if(threadIndex < ThreadCount)
		threadNumber = threadIndex ++;
	else
		threadNumber = -1;
	pthread_mutex_unlock(&threadMutex);
	return threadNumber;
}

void QuickSort(int begin, int end);
void* QuickSort_Procedure(void *data)
{
	cout << ((int*)data)[0] << ", " << ((int*)data)[1] << endl;
	QuickSort(((int*)data)[0], ((int*)data)[1]);
	return 0;
}

void QuickSort(int begin, int end)
{
	int middle, i = begin, j = end;
	/* Pivot */
	if(threadIndex<ThreadCount)
		middle = (float)((begin + end) >> 1) / MaxData * 65535;
	else
		middle = data[(begin + end) >> 1];
	/* Iterating */
	do{
		while(data[i] < middle) i++;
		while(data[j] > middle) j--;
		if(i <= j) 
			swap(data[i++], data[j--]);
	}while(i < j);
	/* Divide and conquer */
	if(begin < j){
		int idx = GetThreadNumber();
		if(idx != -1){
			/* Create a thread to conquer the left part */
			region[idx][0] = begin, region[idx][1] = j;
			pthread_create(&threads[idx], 0, QuickSort_Procedure, region[idx]);
		}else{
			QuickSort(begin, j);
		}
	}
	if(i < end)
		QuickSort(i, end);
}

int main(int argc, char **argv)
{
	pthread_mutex_init(&threadMutex, NULL);
	for(int i=0; i<MaxData; i++)
		data[i] = rand()&0xffff;
	QuickSort(0, MaxData-1);
	/* Wait for 2 threads to end */
	for(int i=0; i<ThreadCount; i++)
		pthread_join(threads[i], 0);
	/*
	for(int i=0; i<MaxData; i++)
		cout << data[i] << " ";
	cout << endl;
	*/
	pthread_mutex_destroy(&threadMutex);
	return 0;
}

代码里定义的ThreadCount，并不是使用的线程数目，而是除了主线程外，额外创建的线程数目。因此，要是用4个线程工作，ThreadCount需要设置为3即可。

下面是我对使用不同的线程数目进行QuickSort的测试结果（统计排序时间包含生成20,000,000个随机数的时间，大约为500ms）：
系统：Ubuntu10.10
CPU：Intel(R) Core(TM) i3 CPU M 330 @ 2.13GHz
内存：2GB

数据大小：20,000,000 ThreadCount = 0 总线程数 = 1

root@xiaoxia-pc:~/code/lab/qsort_mt/Debug# time ./qsort_mt

real 0m6.239s
user 0m6.172s
sys 0m0.052s

数据大小：20,000,000 ThreadCount = 1 总线程数 = 2

root@xiaoxia-pc:~/code/lab/qsort_mt/Debug# time ./qsort_mt
0, 9999594

real 0m3.522s
user 0m6.260s
sys 0m0.024s

数据大小：20,000,000 ThreadCount = 2 总线程数 = 3

root@xiaoxia-pc:~/code/lab/qsort_mt/Debug# time ./qsort_mt
0, 9999283
9999284, 14998392

real 0m3.513s
user 0m7.132s
sys 0m0.056s

数据大小：20,000,000 ThreadCount = 3 总线程数 = 4

root@xiaoxia-pc:~/code/lab/qsort_mt/Debug# time ./qsort_mt
0, 9999283
0, 4998277
9999284, 14998392

real 0m2.707s
user 0m8.049s
sys 0m0.052s

数据大小：20,000,000 ThreadCount = 4 总线程数 = 5

root@xiaoxia-pc:~/code/lab/qsort_mt/Debug# time ./qsort_mt
0, 9999283
0, 4998277
9999284, 14998392
4998277, 7499163

real 0m2.917s
user 0m7.828s
sys 0m0.064s

结果如图所示：

当工作线程数目=CPU线程数目的时候，有最小排序时间，也使CPU的功耗达到最大。