快速排序python实现

快速排序

快速排序的实现同样使用分治法，它的原理是从序列中选择一个值作为基准值，然后分成比基准值小的序列集合和比基准值小的序列集合和与基准值相等的序列集合。

再将比基准值小的序列集合和比基准值小的序列集合再次进行选择基准值分割，最后再从下到上每层按照顺序合并即可。

如图：

每次分割都是以序列中的第一个值作为基准值，经过拆分后自然就变成了有顺序的

具体算法

def quick_sort(s):
    """快速排序，s为列表"""
    # 结束条件
    if len(s) < 2:
        return
    # 从列表取出一个元素作为基准值
    p = s[0]
    L = [] # 小于
    E = [] # 等于
    R = [] # 大于
    # 把s里的元素放入3个队列
    while len(s) > 0:
        if s[-1] < p:
            L.append(s.pop())
        elif s[-1] == p:
            E.append(s.pop())
        else:
            R.append(s.pop())

    quick_sort(L)
    quick_sort(R)
    s.extend(L)
    s.extend(E)
    s.extend(R)

if __name__ == '__main__':
    s = [1, 7, 3, 5, 4]
    quick_sort(s)
    print(s)

代码中实现的是列表的快速排序，类似的也可以实现其他类型序列的排序

时间复杂度

快速排序的时间复杂度有最优情况与最坏情况

最优情况为每一次的基准值都正好为序列的中位数，时间复杂度为nlog(n)

最坏情况为每一次的基准值都恰好是序列的最大值或最小值，时间复杂度为n^2。有意思的是如果每次选第一个数做基准值，但每次这个数又是最小值，那么序列本身就是有序的，但时间复杂度也是最高的

要想

要想优化时间复杂度，基准值的选择很关键，可以使用类似的从序列中选几个数，再求出他们的中位数做基准值

就地快速排序

上面的快排使用了L，E，R存储临时的序列，这样会占用内存，使用就地快速排序的方式可以在原序列上完成排序，减少了内存的使用

def inplace_quick_sort(s,a,b):
    """列表的就地快速排序，s为列表，a为起始索引，b为终止索引"""
    if a >= b:
        return
    # s[b]作为基准值
    p = s[b]
    # left和right相当于指向
    left = a
    right = b-1
    # 把除了s[b]d 其他元素按照以s[b]为基准分割
    while left <= right:

        while left <= right and s[left] < p:
            left += 1

        while left <= right and p < s[right]:
            right -=1

        if left <= right:
            s[left],s[right] = s[right],s[left]
            left,right = left+1,right-1

    s[left],s[b] = s[b],s[left]
    inplace_quick_sort(s,a,left-1)
    inplace_quick_sort(s,left+1,b)

上述代码是列表的就地快速排序，有部分注释可以参考，基本原理是：

• 选择索引b处的值为基准值

• 通过从左到右扫描与从右到左扫描，left是左扫描位置，right是右扫描位置，找到左边第一个大于基准值的位置与右边第一个小于基准值的位置

• 然后将这两个值交换，并将left向右移动，right向左移动，继续重复进行

• 直到left>right,也就是全部扫描一遍后，将基准值s[b]与最后的left位置交换

• 这样就完成了分割

• 然后再进行递归调用两个序列