第七章 快速排序

2024-08-21 05:48
文章标签 快速 排序 第七章

本文主要是介绍第七章 快速排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

7.1 快速排序的描述

7.1.-1参照图7-1的方法,说明PARTITION在数组A=<13,19,9,5,12,8,7,4,21,2,6,11>上的操作过程。

这里写图片描述
图解:在一个样例数组上的PARTITION操作过程。数组项A[r]是主元x=11,红褐色阴影部分。浅绿部分的数组元素都在划分的第一部分,其值都不大于x。深绿部分的元素都在划分的第二部分,其值都大于x。无色的元素是还未分入这两部分中的任意一个。

7.1-2 当数组A[p…r]中的元素都相同时,PARTITION返回的q值是什么?修改PARTITION,使得当数组A[p…r]中所有元素的值都相同时,q= (p+q)/2
1)返回的是r
2)思路:让主元等于首位的元素;i等于p+1,j=r。i指向的元素向左替换,j指向的元素向右替换,最后i和主元替换。

PARTITION(A,p,r)
{x=A[p]i=p+1for j=r to i=jwhile(A[i]<x && i!=j)i++exchange A[i] and A[j]i++while(A[j]>x && i!=j)j++exchange A[i] and A[j]j++exchange A[i] and A[p] 
}

7.1-3 请简要的证明:在规模为n的子数组上,PARTITION的时间复杂度为θ(n)。
它的循环次数为r-p-1次,在规模为n的数组上,循环次数为n-2次
所以PARTITION的时间复杂度为θ(n)

7.1-4 如何修改QUICKSORT,使得它能够以非递增序进行排列?
控制递增排序的是PARTITION而不是QUICKSORT部分,所以要对PARTITION函数进行修改,将里面A[j]<=x变成A[j]>=x即可。

7.2 快速排序的性能

7.2-1 利用代入法证明: 正如7.2节开头提到的那样,递归式T(n)=T(n-1)+θ(n)的解为T(n)=θ( n2 )。

T(n)=c(n1)2+n=cn22cn+1+ncn2c>1/2

7.2-2 当数组A的所有元素都具有相同值时,QUICKSORT的时间复杂度是什么
θ(n2)

7.2-3 证明:当数组A包含的元素不同,并且是按降序排列的时候,QUICKSORT的时间复杂度为θ( n2
第一次,划分为0:n
第二次,划分为0:n-1
……
最后进行次数 1+nn2

7.2-4 银行一般会按照交易时间来记录某一账户的交易情况。但是,很多人却喜欢收到的银行对账单是按照支票号码的顺序来排列的。这是因为,人们通常都是按照支票号码的顺序来开出支票的,而商人也通常都是根据支票编号的顺序兑付支票。这一问题是将按交易时间排序的序列转换成按支票号排序的序列,它实质上是一个对几乎有序的输入序列进行排序的问题。请证明:在这个问题上,INSERTION-SORT 的性能往往要优于QUICKSORT?

QUICKSORT(a,p,r)if p<rq=PARTITION(A,p,r)QUICKSORT(A,p,q-1)QUICKSORT(A,q+1,r)INSERTION-SORT(A)for j=2 to A.lengthkey=A[j]//Insert A[j] into the sorted sequence A[1…j-1]i=j-1while i>0 and A[i]>keyA[i+1]=A[i]i=i-1A[i+1]=key

假如支票序列是排好序的
但是INSERTION-SORT时间复杂度为n
而QUICKSORT时间复杂度为 n2
所有INSERTION-SORT的性能往往要优于QUICKSORT

7.2-5 假设快速排序的每一层所做的划分的比例都是1-α:α,其中 0<α1/2 且是一个常数。试证明:在相应的递归树中,叶节点的最小深度大约是-lgn/lgα ,最大深度大约是-lgn/lg(1-α)(无需考虑整数舍入问题)。
这里写图片描述
最小深度:设最大深度为m,每次向α分割方向下降,m次分割后仅剩1个元素 n*α^m = 1, α^m = 1/n ,两边取对数 mlgα = lg1-lgn ,m = -lgn/lgα
最大深度:同理 n*((1-α)^m) = 1, (1-α)^m = 1/n ,取对数 mlg(1-α) = -lgn 即 m = -lgn/lg(1-α)

7.3 快速排序的随机化版本

7.3-1 为什么我们分析随机化算法的期望运行时间,而不是其最坏运行时间呢?
因为想快速排序这样的算法,很少处于最坏运行时间。

7.3-2 在RANDOMIZED-QUICKSORT 的运行过程中,在最坏情况下,随机数生成器RANDOM 被调用了多少次?最好情况下呢?以θ的形式给出你的答案。
最坏情况下n-1次,θ(n)
最好情况下是lgn次,θ(lgn)

7.4 快速排序分析

7.4-1 证明:在递归式

T(n)=max0qn1(T(q)+T(nq1))+θ<

这篇关于第七章 快速排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1092291

相关文章

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

v0.dev快速开发

探索v0.dev:次世代开发者之利器 今之技艺日新月异,开发者之工具亦随之进步不辍。v0.dev者,新兴之开发者利器也,迅速引起众多开发者之瞩目。本文将引汝探究v0.dev之基本功能与优势,助汝速速上手,提升开发之效率。 何谓v0.dev? v0.dev者,现代化之开发者工具也,旨在简化并加速软件开发之过程。其集多种功能于一体,助开发者高效编写、测试及部署代码。无论汝为前端开发者、后端开发者

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

利用Django框架快速构建Web应用:从零到上线

随着互联网的发展,Web应用的需求日益增长,而Django作为一个高级的Python Web框架,以其强大的功能和灵活的架构,成为了众多开发者的选择。本文将指导你如何从零开始使用Django框架构建一个简单的Web应用,并将其部署到线上,让世界看到你的作品。 Django简介 Django是由Adrian Holovaty和Simon Willison于2005年开发的一个开源框架,旨在简