小小林熬夜学编程

这个屌丝很懒，什么也没留下！

热门标签

快速排序基准数字为中间_第4章快速排序

作者：小小林熬夜学编程 | 2024-04-27 22:38:29

踩

单路快速排序以中间值为准

快速排序

分而治之

分而治之 D&C（divide and conquer）--一种著名的递归式问题解决方法；

使用D&C解决问题的过程包括两个步骤：

1. 找出基线条件，这种条件必须尽可能简单；

2. 不断将问题分解（或者说缩小规模），直到符合基线条件。

分治法是将问题逐步分解。使用分治法处理列表时，基线条件很可能是空数组或只包含一个元素的数组。

案例1

首先我们来看一个小例子：

假设你是一个农场主，有一块土地。

案例2

给定一个数组，你需要将里面的数字相加，并返回结果。

例如数组：arr = [1,2,3,4]

1.我们用循环的方式解决:


def sum(arr):
    total = 0
    for x in arr:
        total += x
    return total
 
print(sum([1,2,3,4])

2.我们用递归函数来完成这种任务：


# 4.2
def count(list):
    if list == []:
        return 0
    return 1 + count(list[1:])
 
# 4.3
def max(list):
    if len(list) == 2:
        return list[0] if list[0] > list[1] else list[1]
    sub_max = max(list[1:])
    return list[0] if list[0] > sub_max else sub_max

4.4：二分查找的基线条件是数组只包含一个元素。如果要查找的值与这个元素相同，就找到了！否则说明它不在数组中。递归条件为把数组分成两半，将其中一半丢弃，并对另一半执行二分查找。

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为较小和较大的2个子序列，然后递归地排序两个子序列。步骤为：

1. 挑选基准值：从数列中挑出一个元素，称为"基准"（pivot）;

2. 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成；

3. 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。


#方法一：选取第一个值为基准值的程序如下：
def quicksort(array):
  if len(array) < 2:
    # 基线条件：为空或只包含一个元素的数组是“有序”的
    return array
  else:
    # 递归条件
    pivot = array[0]
    # 由所有小于等于基准值的元素组成的子数组
    less = [i for i in array[1:] if i <= pivot]
    # 由所有大于基准值的元素组成的子数组
    greater = [i for i in array[1:] if i > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)
 
print(quicksort([10, 5, 2, 3])) # 需排序的数组
 
#方法二：选取中间值为基准值的程序如下：
def quicksort(arr):    
    if len(arr) <= 1:        
        return arr    
    pivot = arr[len(arr) // 2]    
    left = [x for x in arr if x < pivot]    
    middle = [x for x in arr if x == pivot]    
    right = [x for x in arr if x > pivot]    
    return quicksort(left) + middle + quicksort(right)
print(quicksort([3, 6, 8, 19, 1, 5]))  # [1，3, 5, 6, 8, 19]

tips

如果上述程序中：

less = [i for i in array[1:] if i <= pivot]

greater = [i for i in array[1:] if i > pivot]

这两条语句看不懂，请看下面“列表生成式”的解读。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/499050?site

快速排序基准数字为中间_第4章 快速排序

快速排序

分而治之

案例1

案例2

快速排序

tips

快速排序基准数字为中间_第4章快速排序