从本科到现在一直没有搞懂快排的原理,直到今天学习 Haskell 看到一张图,很直观地解释了快速排序的原理,这里我将以自己的理解向各位解释快排的工作原理。 快速排序的理念非常简单: 从列表中取出一个元素,在剩下的元素中,选出所有比它小的元素放在它的左边,其余的放在右边。 此时我们会遇到一个显而易见的问题:分别在被“选中”的元素左边和右边的两个列表,各自内部依然是乱序(未经过排序)的,因为这一步可以理解为对原列表的遍历,因此元素的顺序并没有变。 在这里,才是快速排序算法的真正体现—— 对各个列表,重复第一步的操作,直到选定元素两边的列表只剩至多一个元素。 可以看出,这是一个递归操作。以数组 [5, 1, 9, 4, 6, 7, 3] 和排序函数 quicksort 为例: quicksort 开始 为了简化算法,我们直接在开始处理数组的时候,直接选择第一个元素作为被选定元素。经过筛选后,我们的结果此时变成了这样: quicksort([1, 4, 3]) ++ [5] ++ quicksort([9, 6, 7]) 中间的[5]是我们选定的元素,左边是比它小的元素数组[1, 4, 3],右边是比它大的[9, 6, 7]。可以看出,元素两侧的数组依然是乱序状态,仍然需要对其进行排序,因此上面的伪代码中写作 quicksort(Array),即对两个数组继续应用排序操作。 这里以左边的数组为例,看看递归是如何工作的: quicksort 第一层递归 对新的数组 [1, 4, 3] 重复上面的操作,选定第一个元素 1 作为被选定元素,并筛选其两边的数组,结果变成这样: quicksort([]) ++ [1] ++ quicksort([4, 3]) 左边已经成为空数组,意味着我们选定的 1 就是整个数组最小的元素了,因此没有比它更小的元素存在于它的左边位置了。这样就只剩右侧比它大的 [4, 3] 了,我们依然需要对其应用排序操作 quicksort: quicksort 第二层递归 对新的数组 [4, 3] 重复上面的操作,变成下面这样: