惠州网站建设公司哪家好,wordpress法律主题,建设网站 买了域名还要什么,龙岩今天刚刚最新新闻事件数据结构和算法 基于《算法图解》—Aditya Bhargava 和《数据结构》—严蔚敏
第4章 快速排序
4.1 分而治之 divide and conquer , 简称DC#xff1a;一种著名的递归式问题解决方法。
例子1#xff1a; 假设你是农场主#xff0c;有一小块土地。要求将这块地均匀地分…数据结构和算法 基于《算法图解》—Aditya Bhargava 和《数据结构》—严蔚敏
第4章 快速排序
4.1 分而治之 divide and conquer , 简称DC一种著名的递归式问题解决方法。
例子1 假设你是农场主有一小块土地。要求将这块地均匀地分成方块且分出的方块要尽可能大。 使用DC解决问题的过程包括两个步骤 1找出基线条件这种条件必须尽可能简单。 2不断将问题分解或者说缩小规模直到复合基线条件。 在分土地问题中我们设定基线条件为一条边的长度是另一条边的整数倍。
根据DC的定义每次递归调用都必须缩小问题的规模。因此我们首先找出这块可容纳的最大方块。
可以将这块地划出连个640m×640m的方块。
余下一块640m×400m的土地
按照上述方法继续划分 最终得出对于最初的那块土地适用的最大方块为80m×80m。 也就是说适用于小块地的最大方块也是适用于整块地的最大方块。
例子2 重申DC工作原理 1找出简单的基线条件。 2确定如何缩小问题的规模使其符合基线条件。 注意DC并非可用于解决问题的算法而是一种解决问题的思路。 练习 4.1 请编写前述sum函数的代码。 4.2 编写一个递归函数来计算列表包含的元素数。 4.3 找出列表最大的数字。 4.4 找出二分查找算法的基线条件和递归条件。 4.2 快速排序 使用DC的排序算法需要将数组分解直到满足基线条件。 工作原理从数组中选择一个元素作为基准值(pivot)。 基线条件数组为空或只包含一个元素。(因为这种情况下只需要返回数组——不需要排序)。
假设一个包含三个元素的数组
首先确定元素15用作基准值。
对包含三个元素的数组进行排序的步骤
选择合适的基准值。将数组分成两个子数组小于基准值的元素组成的子数组和大于基准值的元素组成的子数组。对这两个子数组进行排序。最后合并为一个有序数组小于基准值子数组基准值大于基准值子数组。
那么对于包含四个、五个…的数组呢 同样选择一个合适的基准进行分区每个区对其递归地调用快速排序。
#快速排序代码
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 quick(greater)
print quicksort([10,5,2,3]) 4.3 再谈大O表示法 快速排序的独特之处在于其速度取决于选择的基准值。
几种常见的大O运行时间(横坐标为次数纵坐标为时间)
4.3.1 常量的影响
对于大O运行时间相同的两种算法影响大比如合并排序和快速排序运行时间都为O(n log n)快速排序更快。对于大O运行时间不同的两种算法影响则忽略不计这种常量将无关紧要。
4.3.2 平均情况和最糟情况 快速排序的性能高度依赖于你选择的基准值。
假设总是以第一个元素用作基准值
实际上数组并没有被分成两半其中一个子数组始终为空实在是一种浪费导致调用栈达到最大长度栈高也就是层数为O(n)。
假设总是将中间元素用作基准值
调用栈直接减半栈高也就是层数为O(n log n)因为每次都将数组分成两半不需要那么多递归调用很快就达到了基线条件。
在调用栈的每一层都涉及O(n)个元素因此完成每层所需的时间都为O(n) 最佳情况调用栈高度为O(log n)每层需要的时间为O(n)因此整个算法需要的时间为O(n)*O(log n)O(n log n)。 最糟情况调用栈高度为O(n)每层所需时间为O(n)整个时间为On²。 最佳情况也是平均情况快速排序时最快的排序算法之一也是DC典范。
练习 4.5 打印数组中每个元素的值。 4.6 将数组中每个元素的值都乘以2。 4.7 只将数组中第一个元素的值乘以2。 4.8 根据数组包含的元素创建一个乘法表即如果数组为[2,3,7,8,10]首先将每个元素都乘以2再将每个元素都乘以3然后每个元素都乘以7以此类推。 4.4 小结
DC将问题逐步分解。编写涉及数组的递归函数时基线条件通常是数组为空或只包含一个元素。实现快速排序时请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。比较二分查找和简单查找时常量几乎无关紧要因为列表很长时O(log n)的速度比O(n)快很多。
——持续修改完善中…
