随风
快速排序，相信学过算法的各位大佬一定是再熟悉不过了。快速排序以其出色的性能，以及无需辅助空间，较容易实现而获得了极为广泛的使用。但随着CPU核数的日益增加，如何充分利用多核性能已经成为提高程序性能的又一大重要议题，因而在继续讨论iris框架的时候，我想先讨论一下go语言的杀手锏——并发编程。go语言对并发的原生支持，使其对于多核心利用极为有效。
在讨论并发编程之前，我们先来看看几个概念——进程，线程，协程。进程应该是我们最熟悉的。进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。在早期面向进程设计的计算机结构中，进程是程序的基本执行实体；在当代面向线程设计的计算机结构中，进程是线程的容器。程序是指令、数据及其组织形式的描述，进程是程序的实体。由于进程需要分配系统资源，如内存之类的，故利用多进程来实现高并发显然是捉襟见肘，极为不实际。就在我们困厄的时候，线程应运而生，通常在一个进程中可以包含若干个线程，它们可以利用进程所拥有的资源，在引入线程的操作系统中，通常都是把进程作为分配资源的基本单位，而把线程作为独立运行和独立调度的基本单位，由于线程比进程更小，基本上不拥有系统资源，故对它的调度所付出的开销就会小得多，能更高效的提高系统内多个程序间并发执行的程度。当下推出的通用操作系统都引入了线程，以便进一步提高系统的并发性，并把它视为现代操作系统的一个重要指标。许多编程语言对线程的支持都很不错，如java。java有大量的线程操作库，如thread，继承之后重写run方法即可轻松启动一个线程。线程看似轻量，无往而不利，对提高并发量有着极为重要的作用。但它在面对秒杀等场景的时候，线程的缺陷也暴露出来，它始终是一个调度的基本单位，因而能够支持并发的数量也不会太高，普通的个人电脑难以实现百万线程，这时侯协程就应运而生。
协程不是进程或线程，其执行过程更类似于子例程，或者说不带返回值的函数调用。一个程序可以包含多个协程，可以对比与一个进程包含多个线程，因而下面我们来比较协程和线程。我们知道多个线程相对独立，有自己的上下文，切换受系统控制；而协程也相对独立，有自己的上下文，但是其切换由自己控制，由当前协程切换到其他协程由当前协程来控制。可见协程更加轻量，能够实现更高的并发。go语言的groutine正是利用了协程来实现。
那么协程之间如何通讯呢，不能通讯的协程其作用就大大削弱，go语言别出心裁的采用了Chanel实现，其实是一个阻塞队列，当然也可以是带有缓冲的非阻塞的，后面文章会详细讨论。
有了以上的基础知识，不难写出并发快排的代码
import “sync”
func MutiQuickSort(num []int){
lock.Add(1)
QuickSort(num, 0, len(num)-1)
lock.Wait()
}
var lock sync.WaitGroup
func QuickSort(num []int, low, high int) {
defer lock.Done()
if low >= high {
return }
i, j := low, high
key := num[low]
for i < j {
for j > i && num[j] >= key {
j— } num[i] = num[j]
for i < j && num[i] < key {
i++ }
num[j] = num[i]
}
num[j] = key lock.Add(2)
go QuickSort(num, low, i-1)
go QuickSort(num, i+1, high)
}
可见用go语言处理并发优雅而方便，不愧为21世纪c语言。
部分来自百度百科，csdn