losophy

快速排序

发表于 更新于

快速排序,说白了就是给基准数据找其正确索引位置的过程。

快速排序的基本思想是：通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归或者非递归进行，以此达到整个数据变成有序序列。

像合并排序一样，快速排序也是基于分治模式的。

  • 在数据集之中，选择一个元素作为”基准”（pivot）（第一个元素，最后一个元素，中间元素，随机选择）
  • 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边
  • 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止

一个例子

现在有一个数据集{85, 24, 63, 45, 17, 31, 96, 50}
第一步，选择中间的元素45作为”基准”。（基准值可以任意选择，但是选择中间的值比较容易理解。）
bg2011040403
第二步，按照顺序，将每个元素与”基准”进行比较，形成两个子集，一个”小于45”，另一个”大于等于45”。
bg2011040403
第三步，对两个子集不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
bg2011040403
bg2011040403
bg2011040403
bg2011040403

实现

快速排序

1
2
3
4
5
quick_sort(array,left,right)
if left < right then
        partitionIndex = partition(array,left,right)
        quick_sort(array,left,partitionIndex -1)
        quick_sort(array,partitionIndex +1,right)

数组划分

1
2
3
4
5
6
7
8
9
10
11
partition(array,left,right)
    pivot = left; // 设定基准值（pivot）
    index = pivot + 1;

    for i=index to right
        if array[i]<array[pivot] then 
            exchange array[i]<->array[index]
            index++

    exchange array[pivot]<->array[index - 1]
    return index - 1

选取枢纽元问题

糟糕的方法

通常的做法是选择数组中第一个元素作为枢纽元，如果输入是随机的，那么这是可以接受的。但是，如果输入序列是预排序的或者是反序的，那么依据这样的枢纽元进行划分则会出现相当糟糕的情况，因为可能所有的元素不是被划入S1，就是都被划入S2中。

较好的方法

一个比较好的做法是随机选取枢纽元，一般来说，这种策略是比较妥当的。

三数取取中值方法

例如，输入序列为 8, 1, 4, 9, 6, 3, 5, 2, 7, 0 ，它的左边元素为8，右边元素为0，中间位置|_left+right）/2_|上的元素为6，于是枢纽元为6.显然，使用三数中值分割法消除了预排序输入的坏情形，并且减少了快速排序大约5%（此为前人实验所得数据，无法具体证明）的运行时间。

Camarón que se duerme se lo lleva la corriente.

相关文章