经典算法巡礼(六) -- 排序之快速排序
原创经典算法巡礼(六) -- 排序之快速排序
原创
快速排序正如她的名字，她是一种排序效率相当高的算法，而且可能是应用最广泛的排序算法了。快速排序流行的原因是她实现简单，适用于各种不同的输入数据且在一般应用中比其他排序算法都要快。不仅如此，她与归并排序不同，她只需要很小的辅助空间就可以进行排序。
快速排序也是分治思想的典型应用。她与归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序而是当两个子数组都有序时，整个数组也就自己有序了。前者的递归调用发生在处理整个数组之前，而后者的递归调用发生在处理整个之后。
快速排序最主要的操作就是patition，即切分操作。选择数组中一元素，以该元素做为基准切分元素，姑且将其称为P，切分后使P之前的所有元素都小于P(排序成递增序列)，P之后的所有元素都大于P。然后对P切分成的两个子数组分别再一次进行切分操作。重复此过程直到不能切分为止，即整个数组排序完成。
那么如何选择这个切分基准元素P呢？通常是随机取数组中任意值，所以快速排序的效率是和概率相关的，但实际使用过程中排序效率还是非常可观的。具体golang实现如下：
// partition方法即为快速排序中重要的切分操作，以首元素做为基准，将剩余元素从两端寻找，分别找到大于（小于）基准的元素并交换，重复此过程直到剩余元素全部遍历为止
func (this *QuickSort) partition(a []Comparable, compare Compare, lo int, hi int) int {
i := lo + 1
j := hi
v := a[lo]
for true {
for this.less(a[i], v, compare) == true {
if i == hi {
break
}
i++
}
for this.less(a[j], v, compare) == false {
if j == lo {
break
}
j--
}
if i >= j {
break
}
this.exch(a, i, j)
i++
j--
}
this.exch(a, lo, j)
return j
}
// Sort中参数类型Comparable为统一的可比较接口，若为整数数组排序，则Comparable为int即可
// Sort中参数类型Compare为配合Comparable接口的比较方法，若为整数数组排序，则Compare即满足a int < a int即可
func (this *QuickSort) Sort(a []Comparable, compare Compare, lo int, hi int) {
if hi <= lo {
return
}
p := this.partition(a, compare, lo, hi)
this.Sort(a, compare, lo, p-1)
this.Sort(a, compare, p+1, hi)
}上述实现过程在切分操作时，只是简单取数组第一个元素做为切分基准元素。如此做法，排序效率则与输入序列相关了，因此可以在排序之前shuffee数组，如此一来就与概率相关了。
分析快速排序的过程，可以得到每次patition时，需要N-1次比较操作（数组元素为N的情况下），同时又可得到此patition过程需要进行logN次。因此，整个快速排序需要(N-1)logN ~ NlogN次比较操作，也就是说其时间复杂度为O(NlogN)。因此，她也是可以应用于大规模数组的排序，而且也不需要归并排序大量的额外空间，同时也没有希尔排序的不确定性。
当然，其实快速排序有一种方便的改进，即可在对有大量相同元素的数组排序时，效率大大提高。她是由Dijkstra提出的“三向切分的快速排序“。具体实现如下：
// Sort方法采用”三向切分的快速排序“法进行排序
func (this *QuickSort) Sort(a []Comparable, compare Compare, lo int, hi int) {
if hi <= lo {
return
}
lt := lo
i := lo + 1
gt := hi
v := a[lo]
for i <= gt {
cmp := compare(v, a[i])
if cmp < 0 {
this.exch(a, i, gt)
gt--
} else if cmp > 0 {
this.exch(a, i, lt)
i++
lt++
} else {
i++
}
}
this.Sort(a, compare, lo, lt-1)
this.Sort(a, compare, gt+1, hi)
}"三向切分的快速排序"中的切分方法过程如下：
她遍历数组一次，维护一个指针lt使得alo..lt-1中的元素都小于v(即切分基准元素)，一个指针gt使得agt+1..hi中的元素都大于v，一个指针i使得alt..i-1全部等于v，而ai..gt中的元素都还未确定。正如上述代码中所示，等遍历完数组后，数组就分为三部分，alo..lt-1为小于v的部分，agt+1..hi为大于v的部分，而alt..gt则为等于v的部分。然后，对不等于v的部分数组再次切分递归，直到不能切分为止。
而如果数组中有大量相同元素时，采用”三向切分“方法就不会对相同部分再次进行重复比较，大大提高排序性能。而当没有重复元素时，”三向切分“方法又等同时原始快速排序。因此，”三向切分的快速排序“通常被用于实际场合中进行快速排序。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。