快速排序(Quick Sort)
扯淡
今天突然想起来好久没有看排序的东西了，就抽了点时间随便选了个排序算法来唠唠嗑，正好抽到的是快速排序，讲真，这种排序一般的library里面都帮实现好了，但是作为一个合格的程序猿还是有必要随手可以拿笔实现各种排序和数据结构。就整理下快排的实现和优化
快排实现
快排基础
快排也属于一种高级排序了，快排其实对世界排序算法里面影响比较大的一个了，听名字就知道很厉害，可以很快的把一个无顺序的数组进行排列。快排类似归并使用了递归，但是他和归并不同的是其递归的部分。
快排的思路是把指定的一个元素，以这个元素为基点，把这个元素移动到指定的位置。移动完之后就会产生效果就是这个元素的左边都小于这个元素和这个元素的右边都大于这个元素。
假设我们有数组[4 3 5 2 7 9], 我们选定第一个次排序的基点为4:
然后我们第一次排序完的结果就是：
以4为基点，4的左边都是小于4，4的右边都是大于4.因为4 在这个数组中已经 处于了正确的位置。 接下来我们就要递归对4的左边和4的右边分别找到对应的基点对其进行排列。
Partition
Partition 机理
我们把基点回归到对应的位置这个步骤做partition，所以我们整个代码的结构应该是这样的(golang)
//对外的接口
func QuickSort(arr []int,n int){
quickSortHelper(arr,0,n-1)
}
//这个方法不对外
func quickSortHelper(arr []int, left,right int){
//找到对应的基点
base:=partition(arr,left,right)
//递归左边
quickSortHelper(arr,left,base-1)
//递归右边
quickSortHelper(arr,base+1,right)
}
//parition
func partition(arr[]int,left,right int)int{
}
如何实现partition就是重点了：
我们取 3个下角标：l: 当前基点的下标（取数组的第一位）, j 为 大于小于的分界点，小于下标j的所有数都小于基点，大于下标j的数所有数大于基点，最后i为当前遍历的数子，也就是最后推出: arr[l+1,j] < V; arr[j+1,i-1]> v
在遍历的时候的分2部分： 第一部分：如果当前的E 大于V， 则i 往后拓展 第二部分：如果当前的E 小于V， 则E(arr[i]) 和arr[j+1]进行交换，最后j++ 这样就确保了，所有大于V的数字在j的右边 和小于V的数组在 j的左边
当一次遍历完成以后：我们需要讲arr[j]和arr[l] 进行交换，根据上图可以发现，j最后的落点其实就是基点应该在的位置：
Partition 实现
func partition(arr[]int,left,right int)int{
base:=arr[left]
j:=left
for i:=j+1;i<=right;i++{
if arr[i]<base{
arr[j+1],arr[i] = arr[i],arr[j+1]
j++
}
}
arr[j],arr[left] = arr[left],arr[j]
return j
}
快排压力测试:
我们可以用golang的测试单元，新建一个quicksort的test文件:
func TestQuickSort(t *testing.T) {
testdata:=make([]int,100000)
random:=rand.New(rand.NewSource(time.Now().UnixNano()))
for i:=0;i<len(testdata);i++{
testdata[i]= random.Int()
}
startTime:= time.Now()
QuickSort(testdata,len(testdata))
elapsed := time.Since(startTime)
fmt.Println("elapsed: ",elapsed)
}
//output
outPut: elapsed: 9.8664ms
其实快速排序的平均Big O在 nlogn 在排序中算很快的了
快排优化
来思考这么一个问题，如果给定的数组是基本排好序的数组，那么用我们目前写的快排的运行速度在多少呢：
进行压力测试一下：
testdata:=make([]int,100000)
random:=rand.New(rand.NewSource(time.Now().UnixNano()))
for i:=0;i<len(testdata);i++{
testdata[i]= random.Int()
}
startTime:= time.Now()
QuickSort(testdata,len(testdata))
elapsed := time.Since(startTime)
fmt.Println("time: ",elapsed)
startTime2:= time.Now()
QuickSort(testdata,len(testdata))
elapsed2 := time.Since(startTime2)
fmt.Println("elapsed2: ",elapsed2)
//output:
elapsed: 8.026583ms
elapsed2: 5.11944269s
可以发现。。。如果对一个排好序的数组在进行快排，速度慢的一笔 = =，跟之前差距太大(看了测试结果突然发现，golang的速度挺快的我以为会超过10s)。 这个是为什么呢
快排优化1
那个是因为我们每次都取数组作为第一个为基点，而对于排好序的数组第一个数就是已经最小的数了，那就造成了。在partition出来的归并数组 并非对称 结果就导致了每次在递归的时候，都是针对一个很长的数组进行递归的。那么效率就降低到 n^2(超级慢。。)
快排方法
其实这个优化很简单，我们在取基点的时候随机取就行了，随机去完之后跟第一个数进行交换就好了。。
func QuickSort(arr []int,n int){
//先初始化一个random器出来
randSelector=rand.New(rand.NewSource(time.Now().UnixNano()))
quickSortHelper(arr,0,n-1)
}
//然后在partition里面随机基点，最后跟第一个数进行调换就可以了。
//虽然基点还是第一个数，但是其实是被掉了包的啦
func partition(arr[]int,left,right int)int{
randNumber:=randSelector.Int()%(right-left+1)+left
arr[randNumber],arr[left]=arr[left],arr[randNumber]
}
最后压力测试下：
elapsed: 10.793327ms
elapsed2: 7.65218ms
回到了 nlog(n)的复杂度，有兴趣的小伙伴可以自己算下数学期望
快排优化2-二路快排
思考下这种情况，如果一个数组里面有超级多的重复会怎么样？
//在压力测试里面规定一下随机的取值范围
for i:=0;i<len(testdata);i++{
testdata[i]= random.Int()%10
}
//output:
elapsed: 668.770599ms
啧啧，也发现这个速度也好慢，那是因为，我们在写代码的时候
for i:=j+1;i<=right;i++{
if arr[i]<base{
arr[j+1],arr[i] = arr[i],arr[j+1]
j++
}
}
这个里面，我们只处理了小于基点的情况，那也就是说，当 等于基点的时候，会被归到 大于基点的那一边，最后造成了，递归的时候，数组很大的情况
进行优化的话，我们可以采用双路快排
我们可以把partition拆分成二块，第一块就是小于V 第二块就是大于V这样的好处就是 出现等于V的时候会分到不同的区域中就没有必要只用一个啦， 当然最后的话就要对小于v 大于v进行递归咯
func partition2(arr[]int,left,right int)int{
randNumber:=randSelector.Int()%(right-left+1)+left
arr[randNumber],arr[left]=arr[left],arr[randNumber]
base:=arr[left]
i:=left+1
j:=right
for true{
for i<=right&&arr[i]<base{
i++
}
for j>=left&&arr[j]>base{
j--
}
if i >j{
break
}
arr[i],arr[j]=arr[j],arr[i]
i++
j--
}
arr[left],arr[j] =arr[j],arr[left]
return j
}
简单的来说就是，i的小下标一直去寻找小于V的数如果找到大于V的数，他就被定在那边，j下角标也是的找到比V小的数那么就定在那里然后进行 交换， biubiubiu的
最后压力测试的结果：elapsed: 4.594925ms
快排优化3-三路快排
在二路上也可以进行三路快排，到了三就没有啦，就没有4路啦，因为三路的思想是增加了 等于V的情况。biubiubiu
也就是说arr[l+1,lt]<V, arr[lt+1,i-1]==v,arr[gt,r]>v
//部分代码
for i<gt{
if arr[i]<v{
arr[i],arr[lt+1]=arr[lt+1],arr[i]
lt++
}else if arr[i]>v{
arr[i],arr[gt]=arr[gt],arr[i]
gt--
}else{
i++
}
}
arr[l],arr[lt]=arr[lt],arr[l]
这里注意的是三路需要返回2个值哦 分别是lt和gt，对于golang的小伙伴表示无所谓，因为golang允许返回多个值，但是对于java的小伙伴，可以考虑把partition直接写在helper里面
结束！！
撒花，快排也就这些内容啦。。撒花撒花，希望可以帮助到大家
