快速排序

快排的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。通常可选第一个记录为基准来重新排列其余记录，另外它需要一个栈空间来实现递归。

通常用第一个记录作为基准的时候

最好情况：每次基准归位，刚好落在序列的中间，将序列均匀的划分为长度相等或相近的两个子序列。栈空间最大深度为log(n+1)，1表示最外层参数进栈

时间复杂度：n·log(n)

空间复杂度：log(n)

最坏情况：初始序列已经有序或基本有序时，每趟排序之后基准落在子序列的一端，则为最坏情况。栈空间最大深度为n

时间复杂度：n^2

空间复杂度：n

数据量大且有序时，使用第一个记录为基准排序会很慢，在leetcode 215题中就体现出来了，因此需要用下面方法对最坏情况进行改进

改善基准的选取

1，随机选基准

随机选择基准可以提升最坏情况下的性能，但是在随机选择时也有最坏情况，即每次都选择了有序序列的一端，最坏时间复杂度也是O（N^2），但整体还是比上述以第一个为基准要好。

2，三者取中（a[0]，a[-1]，a[len(a)//2]）

《严 · 数据结构》上推荐使用三者取中，可大大改善快速排序在最坏情况下的性能。

（3，BFPRT是不是也能优化快排的基准选择，如果用了BFPRT，基准每次都划分在序列中间位置，这样总的快排时间复杂度就是优化前的复杂度n·log(n)，就不存在最坏O(N^2)的情况。）

改善快排的递归过程

以基准划分序列时，用两个boolean变量标记两指针向中间移动过程中是否进行过交换，若有哪一部分没有进行交换，则无需对这部分进行递归，进而提升了性能。

代码实现

import random

def partition(nums, left, right, base):

    '''基准归位'''

    if left == right:

        return

    temp = nums[base]

    nums[base], nums[right] = nums[right], nums[base]  # 和尾部节点交换

    max_index = left

    for i in range(left, right):

        if nums[i] < temp:

            nums[i], nums[max_index] = nums[max_index], nums[i]

            max_index += 1

    nums[max_index], nums[right] = nums[right], nums[max_index]

    return max_index

def quick_sort(nums, left, right):

    '''快速排序'''

    if left >= right:

        return

    base = random.randint(left, right)     # 随机选取基准

    base_index = partition(nums, left, right, base)

    quick_sort(nums, left, base_index-1)   # 递归左边

    quick_sort(nums, base_index+1, right)  # 递归右边

if __name__ == '__main__':

    nums = [6, 1, 8, 8, 8, 2, 7, 9, 3, 8, 8, 4, 5, 10]

    left, right = 0, len(nums) - 1

    quick_sort(nums, left, right)

    print(nums)

快速选择

和快排partition过程一致，分治过程只操作有用的一半，另一半不管。

import random

def partition(nums, left, right, base):

    '''基准归位'''

    if left == right:

        return

    temp = nums[base]

    nums[base], nums[right] = nums[right], nums[base]  # 和尾部节点交换

    max_index = left

    for i in range(left, right):

        if nums[i] < temp:

            nums[i], nums[max_index] = nums[max_index], nums[i]

            max_index += 1

    nums[max_index], nums[right] = nums[right], nums[max_index]

    return max_index

def quick_select(nums, left, right, K):

    '''快速选择'''

    if left == right:  # 分治的序列仅剩一个元素，那么就是它了

        return nums[left]

    base = random.randint(left, right)     # 随机选取基准

    base_index = partition(nums, left, right, base)

    if base_index == K:

        return nums[base_index]

    elif base_index > K:

        return quick_select(nums, left, base_index-1, K)   # 递归左边

    else:

        return quick_select(nums, base_index+1, right, K)  # 递归右边

if __name__ == '__main__':

    nums = [6, 1, 8, 8, 8, 2, 7, 9, 3, 8, 8, 4, 5, 10]

    nums = list(set(nums))

    print(nums)

    left, right = 0, len(nums) - 1

    K = 2  # 第K大

    ans = quick_select(nums, left, right, right-K+1)  # 等于N-K+1小，10-2+1=9

    print(ans)

巴特西

对快速排序的分析 Quick Sort

快速排序

改善基准的选取

改善快排的递归过程

代码实现

快速选择

最新文章

热门文章