快速排序算法是基于分治策略的另一个排序算法。 该方法的基本思想是: 1.先从数列中取出一个数作为基准数,记为x。 2.分区过程,将不小于x的数全放到它的右边,不大于x的数全放到它的左边。(这样key的位置左边的没有大于key的,右边的没有小于key的,只需对左右区间排序即可) 3.再对左右区间重复第二步,直到各区间只有一个数 快排目前有两类实现算法,第一种是标准算法,第二种是两头交换法。总的思想与上面三步一样,在细节处理上有一些差异。 标准算法思想及实现标准算算法采用的思想是挖坑填坑的思想: 以一个数组作为示例,取区间第一个数为基准数。
初始时,i = 0; j = 9; X = a[i] = 72 由于已经将a[0]中的数保存到X中,可以理解成在数组a[0]上挖了个坑,可以将其它数据填充到这来。 从j开始向前找一个比X小或等于X的数。当j=8,符合条件,将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了,但又形成了一个新坑a[8],这怎么办了?简单,再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数,当i=3,符合条件,将a[3]挖出再填到上一个坑中a[8]=a[3]; j--; 数组变为:
i = 3; j = 7; X=72 再重复上面的步骤,先从后向前找,再从前向后找。 从j开始向前找,当j=5,符合条件,将a[5]挖出填到上一个坑中,a[3] = a[5]; i++; 从i开始向后找,当i=5时,由于i==j退出。 此时,i = j = 5,而a[5]刚好又是上次挖的坑,因此将X填入a[5]。 数组变为:
可以看出a[5]前面的数字都小于它,a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。 对挖坑填数进行总结 1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。 2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。 3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。 4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。 代码实现如下: [cpp]view plain copyprint?
两头交换法思想及实现两头交换法与标准算法思想的差异是,先从左边开始找到大于基准值的那个数,再从右边找到小于基准值的那个数,将两个数交换(这样比基准值小的都在左边,比基准值大的都在右边)。直到数列分成大于基准值和小于基准值的两个区间,以这两个区间进行同样的排序操作。 代码实现如下: [cpp]view plain copyprint?
上面的算法是两头交换法官方的版本,边界情况较少,比较健壮。 两头交换法还有另一个实现方式,这种实现方式,基准值只能选区间第一个值或最后一个值。基准值不参与交换,将除基准值之外的所有值按照与基准值的大小关系分成两部分,然后将区间分界点的值填到基准值的坑里,将基准值放在区间分界点。对于基准值左右的区间进行再次排序。 代码实现: [cpp]view plain copyprint? [cpp]view plain copyprint?
[cpp]view plain copyprint? 注意:两头交换法,最后填坑点的选择与基准值的选择有关系,当基准值在区间前半部分则填坑点选值较小的j,反之则选i. 效率分析快排的时间复杂度理论上是Nlog(N). i,j点的值与基准值比较时取“严格大于/小于”还是”大于等于/小于等于”会影响复法最坏复杂度。一般的想法是用大于等于/小于等于,忽略与枢纽元相同的元素,这样可以减少不必要的交换,因为这些元素无论放在哪一边都是一样的。但是如果遇到所有元素都一样的情况,这种方法每次都会产生最坏的划分,也就是一边1个元素,令一边n-1个元素,使得时间复杂度变成。而如果用严格大于/小于,虽然两边指针每此只挪动1位,但是它们会在正中间相遇,产生一个最好的划分,时间复杂度为。。但是当取严格大于/小于的时候,交换的次数也会相应的增加。实际的交换次数应该是相同的。
|
|
来自: 昵称46399781 > 《数字编码》