图解算法基础——快速排序，用Go代码实现

很多面试题都是基于排序来回答的。如果我们写一个算法，很大概率会挂掉。今天写一篇关于快速排序的基础文章。后面会根据情况写合并和堆排序。至于时间复杂度高的选择排序和冒泡排序就不写了。有兴趣的可以自己找本书看。本文算法的实现是用Go写一个比较简单的快速排序，方便大家理解（画外音：其实他好几年没面试了，写不出来即使他太优秀了）。关于更好的代码实现，大家可以发到评论区一起学习。相信在我们的读者当中，肯定有卧虎藏龙，也有很多厉害的算法。快速排序的思想快速排序算法首先在序列中随机选择一个主元值，然后将除主元值以外的数分为“小于主元值的数”和“大于主元值的数”。两大类，然后把它们排列成下面的形式。【小于参考值的个数】参考值【大于参考值的个数】接下来，继续对“【】”两个序列中的数据进行排序后，整体排序完成。将序列排序到枢轴值的左侧和右侧时，也会使用快速排序。快速排序是一种“分而治之法”，将原问题分解为两个子问题——小于参考值的数和大于参考值的数，然后分别求解这两个子问题。求解子问题时又用到了快速排序，只有当子问题只剩下一个数时，排序才算完成。快速排序的过程下面我们用一个示意图来更好的理解快速排序对一个序列进行排序的过程。传说来自—《我的第一本算法书》。假设有一个待排序序列如下：待排序序列首先在序列中随机选择一个参考值，这里选择4。选中参考值支点，将其他数与参考值进行比较，小于参考值则向左移动，大于参考值则向右移动。先比较第一个元素3和参考值4，因为3<4，所以把3放在参考值的左边。先比较3和基值4，因为3<4，所以把3放在基值的左边接下来，比较5和基值，因为5>4，所以把5放在基值的右边。5>4，把5放在参考值的右边，对整个数列做同样的操作，所有小于参考值的数都放在参考值的左边，所有大于参考值的数都放在向右。一轮排序完成后，将基准值放入序列中。现在排序分为两个子问题，分别对基准值左右的数据进行排序。分解成两个子问题两边的排序操作同上。也采用快速排序算法来选择参考值，较小的数字放在左边，较大的数字放在右边。对子序列使用QuickSort子问题可以再次分解为子问题，直到子问题只剩下一个数，不能再分解子问题时，整个序列的排序才算完成。排序完成是因为快速排序算法在对序列进行排序的过程中会再次使用该算法，所以快速排序算法需要使用“递归”来实现。快速排序的Go代码实现了以下快速排序算法的Go版本的简单实现：funcquickSort(sequence[]int,lowint,highint){ifhigh<=low{return}j:=partition(sequence,low,high)quickSort(sequence,low,j-1)quickSort(sequence,j+1,high)}//快速排序进行一轮排序funcpartition(sequence[]int,lowint,highint)int{i,j:=low+1,highfor{//使用头元素作为枢轴值pivotforsequence[i]=high{break}}forsequence[j]>sequence[low]{//j坐标从回到前面，如果position上面的值小于参考值，就停止。//将位置j与大于参考值的i坐标指向的值交换--ifj<=low{break}}ifi>=j{break}sequence[i],sequence[j]=sequence[j],sequence[i]}sequence[low],sequence[j]=sequence[j],sequence[low]returnj}每一轮快速排序都会经过以下步骤：设置两个变量i和j，开始排序当：i=0，j=待排序序列的长度-1。取第一个数组元素作为枢轴值（也可以是最后一个元素，也可以是随机元素）。i坐标从头开始向后访问序列中的元素，即i++，找到第一个大于pivot的位置，与j坐标访问的小于参考值的值交换位置。j坐标从末尾向前查找，即j--，找到第一个比pivot小的位置，交换i和j坐标上的值。重复步骤3和4，直到i=j，然后交换pivot和j坐标上的值，完成一轮排序。小于pivot的值放在左边，大于pivot的值放在右边。重复上述过程，直到排序完成。最后，我们可以生成一个随机数序列来测试上面的快速排序函数：funcmain(){rand.Seed(time.Now().Unix())sequence:=rand.Perm(34)fmt.Printf("sequencebeforesort:%v",sequence)quickSort(sequence,0,len(sequence)-1)fmt.Printf("sequenceaftersort:%v",sequence)}拆分子序列时需要快速排序的时间复杂度选择参考值。如果每次选择的参考值都能使两个子序列的长度为原来的一半，那么快速排序的运行时间和归并排序一样，都是O(nlogn)。将序列分割成log2n次对半后，子序列只剩下一个数据，子序列的排序就完成了。因此，如果像下图这样逐行显示按pivot值拆分系列的过程，则总共有log2n行。quicksort分解序列的个数要求每一行的每个数都需要和参考值进行比较，所以每一行需要的运行时间为O(n)。可以看出整体时间复杂度为O(nlogn)。如果运气不好，每次都选择最小值作为参考值，那么每次都需要把其他数据移到参考值的右边，递归执行n行，运行时间会减少。因此，在实际应用时，参考值的选择更为讲究。例如，中位数作为参考值：将本轮排序序列的第一个、最后一个、中间位置的中位数作为排序的参考值。