10.1 快速排序
10.1.1 算法概述
策略:分而治之。
下面举个例子,假如一组数为13/81/92/43/65/31/57/26/75/0,我们对其进行排序。那么首先选择出一个主元,这里我们选择为65,那么将这组数的其他成员分为了两组,一组是小于主元的13/43/31/57/26/0,一组是大于主元的81/92/75.然后将其递归处理,两边各选一个主元再进行分组……倒数第二步的时候,我们在第一步选择出来的主元左侧已经排好了顺序,右侧也排好了顺序,这样将它们放在同一个数组中,就完成了排序。
以下是上面这段话的伪码描述:
这个方法的关键在于主元的选取(选取不好,快速算法会很慢)和子集划分(这个过程也是耗费时间的一个地方)。
快速排序算法的最好情况就是每次正好中分,T(N)=O(NlogN)。
10.1.2 选主元
选取头、中、尾的中位数,也可以选取5个、7个等数字的中位数。例如8/12/3的中位数就是8。伪码描述如下:
10.1.3 子集划分
为了便于理解,还是举一个例子:
定义两个指针i(指向第一个元素)和j(指向中位数左侧的元素)。(继续强调,这里的i和j不是实际的指针,而是存储所需要元素下标的整数。)先比较i代表的元素和主元的大小,发现8大于6,那么i这个指针不变;然后看j代表的元素和主元比较,发现7大于6,将j减一(即左移一位),然后再比较,发现2小于6,这样就不对了,j停止移动。在i和j都停止移动后,将其所指向的两个元素交换位置,变成了下面这个样子。
然后i加1(右移一位),1小于6,正常,i继续加1(右移一位),4小于6,正常,i继续加1(右移一位),此时9大于6,不正常,i停止;再看j减1(左移一位),5小于6,不正常,j停止,然后交换此时i和j所代表的元素,变成下面这个样子。
然后i加1(右移一位),发现正常,i继续加1,发现正常,i再加1,发现9小于6,不正常,i停止;然后j左移一位,发现3小于6,不正常,停止。
此时发现i-j
快速算法的“快速”在于,划分完成后其主元被一次性放到了正确的位置再也不会移动;例如插入算法等都需要一步一步往后移。
如果有元素正好等于pivot怎么办?停下来处理。
对于小规模数据还不如用插入排序。当递归的数据规模充分小,则停止递归,直接调用简单排序。在程序中定义一个Cutoff的阈值。
10.1.4 算法实现
伪码描述:
为了统一接口,在上段程序后面再加一个:
快速排序算法是不稳定算法!
以下给出另外的C语言编写的代码,它是直接调用函数库:
领取专属 10元无门槛券
私享最新 技术干货