《算法导论》读书笔记附练习第七章快速排序

算法导论思考题7_2对区间的模糊排序这个学期在做算法设计课的助教，很多题以前做过就忘记了，重做特地记录下。

《算法导论》chapter7 problem7-6对区间的模糊排序考虑这样⼀种排序问题,即⽆法准确的知道等排序的各个数字到底是多⼤.对于其中的每个数字,我们只知道它落在实轴上的某个区间内.亦即,给定的 n 个形如[ai, bi ]的闭区间,其中ai,≤bi .算法的⽬标是对这些区间进⾏模糊排序(fuzzy-sort),亦即,产⽣各区间的⼀个排序<i1, i2, i3, i4,…in >,使得存在⼀个 cj ∈[ai, bi ],满⾜c1≤c2≤…≤cn .a)为n个区间的模糊排序设计⼀个算法,你的算法应该具有算法的⼀般结构,它可以快速排序左部端点(即各ai ),也要能充分利⽤重叠区间来改善运⾏时间.(随着各区间重叠得越来越多,对各区间的排序的问题会变得越来越容易,你的算法应该能充分利⽤这种重叠.)b)证明: 在⼀般情况下,你的算法的区望运⾏时间为 O(n*lgn),但当所有的区间都重叠时,期望的运⾏时间为O(n) (亦即,当存在⼀个值 x, 使得对所有的 i, 都有x∈[ai, bi ] ).你的算法不应显式的检查这种情况,⽽是应当随着重叠量的增加,性能⾃然地有所改善.解答a. 算法思想基本是仿快速排序对区间进⾏排序。

难点在于如何充分利⽤重叠区间来改善运⾏时间？其关键在于Partion()的设计。

对于如何充分利⽤重叠区间，解决思路是在调⽤Partion()划分时，区间如果重叠的部分，就把它们看做是相等的，并提取公共部分继续划分。

即对于区间[ai,bi]，[aj,bj],它们⼤⼩分为三种情况。

if(bi<aj)那么[ai,bi]<[aj,bj]else if(bj<ai)那么[aj,bj]<[ai,bi]else [ai,bi]=[aj,bj]。

⽹上其它⼈的解答，思路都是类似的，不过看了⼏个版本，不少⼈在代码实现上多少有点bug。

精通八大排序算法系列：一、快速排序算法2011/01/09 583 写此八大排序算法系列之前，先说点题外话。

每写一篇文章，我都会遵循以下几点原则：一、保持版面的尽量清晰，力保排版良好。

二、力争所写的东西，清晰易懂，图文并茂三、尽最大可能确保所写的东西精准，有实用价值。

 因为，我觉得，你既然要把你的文章，公布出来，那么你就一定要为你的读者负责。

不然，就不要发表出来。

一切，为读者服务。

 ok，闲不多说。

接下来，咱们立刻进入本文章的主题，排序算法。

众所周知，快速排序算法是排序算法中的重头戏。

因此，本系列，本文就从快速排序开始。

------------------------------------------------------ 一、快速排序算法的基本特性时间复杂度：O（n*lgn）最坏：O（n ）空间复杂度：O（n*lgn）不稳定。

 快速排序是一种排序算法，对包含n个数的输入数组，平均时间为O（nlgn），最坏情况是O（n ）。

通常是用于排序的最佳选择。

因为，排序最快，也只能达到O （nlgn）。

 二、快速排序算法的描述算法导论，第7章快速排序时基于分治模式处理的，对一个典型子数组A[p...r]排序的分治过程为三个步骤：1.分解：A[p..r]被划分为俩个（可能空）的子数组A[p ..q-1]和A[q+1 ..r]，使得A[p ..q-1] = A[q] = A[q+1 ..r]2.解决：通过递归调用快速排序，对子数组A[p ..q-1]和A[q+1 ..r]排序。

3.合并。

 三、快速排序算法 版本一：QUICKSORT(A, p, r)1 if p r2 then q ←PARTITION(A, p, r) //关键3 QUICKSORT(A, p, q - 1)4 QUICKSORT(A, q + 1, r) 数组划分快速排序算法的关键是PARTITION过程，它对A[p..r]进行就地重排：PARTITION(A, p, r)1 x ← A[r]2 i ← p - 13 for j ← p to r - 14 do if A[j] ≤ x5 then i ← i + 16 exchange A[i] - A[j]7 exchange A[i + 1] - A[r]8 return i + 1。

算法导论第7章看CLRS⼀般把笔记写在书的margin⾥。

Cormen的提纲也是蛮好的，适合复习。

这⾥⽤的Partition⽅法是Lomuto Partition，不是原始的也是第1版中的Hoare Partition。

后者被留作习题。

快排Quicksort的时间复杂度worst-case是\Theta(n^2), 期望时间是\Theta(nlgn), 复杂度前⾯的常数很⼩，sort in place。

Descriptions of quicksort快排是Divide-and-conquer的典范。

Divide: ⽤pivot把数组划分为两半A[p,…,q-1]和A[q+1,…,r]。

前⾯的数组⽐A[q]⼩，后⾯的数组⽐A[q]⼤。

Conquer: 递归调⽤quicksortCombie: 不需要，sort in place⽤来划分的函数叫做PARTITION，返回下标q。

Quicksort函数def QUICKSORT(A, p, r):if p < r:q = PARTITION(A, p, r)QUICKSORT(A, p, q - 1)QUICKSORT(A, q + 1, r)Python美~PARTITION函数def PARTITION(A, p, r ):x = A[r ]i = p - 1for j = p to r - 1:if A[ j ] <= x:i = i + 1exchange A[i ] - A[ j ]exchange A[i + 1] - A[r ]return i + 1PARTITION总是选取最后⼀个元素作为pivot，习题中可以⽤Median of 3优化，要求我们计算划分good split的概率提供了多少。

没有优化的PARTITION有可能使得划分到的2个数组有1个为空原⽂⽤Loop invariant证明PARTITION正确性，Initialization，Maintenance，Termination，blablabla……。

算法导论小笔记算法导论（CLRS）笔记Note on CLRS(Outline & Draft, 2011)Jian Xiao1第2章Getting started1. Merge sort相关的扩展问题1）链表实现V.S.数组实现。

Divide阶段，如何快速找到链表的中点？另外，如何减少Divide/Combine的时间（相比数组实现）？2）In-place merge的方法。

3）归并树：把Merge sort的中间过程都记录下来，所形成的树。

（其实就是一棵线段树,每个节点存放该节点的区间内有序化后的数）4）逆序数的计算。

2. 两数和问题。

数的集合S，一个数x，判断S中是否存在两个数，二者的和为x。

这个问题扩展以后是一个subset problem，为NPC问题。

第3章Growth of Functions1. 全部5个渐进符号的确切含义第4章Recurrences1. Substitution方法，Recursion tree方法计算复杂度2. Master Theorem及其不能被三种case覆盖的其他情况Master Theorem的证明3. Chip testing problem4. Monge arrays，凸四边形不等式，最优二叉查找树DP算法的优化第5章Probabilistic Analysis and Randomized Algorithms1. 用Biased-Random产生Uniform-Random分布。

2. In-place、O(n)的uniform random permutationIn-place、O(n)的各个position等概的排列1iamxiaojian@/doc/d1*******.html,3. Coupon collector’s problem4. On-line hiring problem第6章Heapsort1. 两种建堆的方法：逐个插入的O(nlogn)，以及自底向上调整的O(n)算法2. Heap sort可能存在效率的地方：每次删除堆顶，都是把某树叶放置于堆顶，然后调整；但是，树叶一般比较大，放于堆顶后，几乎总是要进行多次的比较才能恢复堆的结构。

算法导论读书笔记第1章:算法在计算中的作用1.算法即是一系列的计算步骤,用来将一个有效的输入转换成一个有效的输出。

2.计算机的有限的资源必须被有效的利用,算法就是来解决这些问题的方法。

第2章:算法入门1、循环不变式的三个性质:(循环不变式通常用来证明递归的正确性)（1）初始化:它在循环的第一轮迭代开始之前,应该是正确的。

（2）保持:如果在循环的某一次迭代开始之前它是正确的,那么,在下一次迭代开始之前,它也应该保持正确。

（3）终止:当循环结束时,不变式给了我们一个有用的性质,它有助于表明算法是正确的。

2、分治策略:将原问题划分成n个规模较小而结构与原问题相似的子问题;递归地解决这些小问题,然后再合并其结果，就得到原问题的解。

3、分治模式在每一-层递归上都有三个步骤:（1）分解(Divde):将原问题分解成-系列子问题;（2）解决(Conquer):递归地解答各子问题。

若子问题足够小，则直接求解;（3）合并(Combine):将子问题的结果合并成原问题的解。

第3章:函数的增长1.对几个记号的大意:。

(非渐近紧确上界)≈<;0(渐近上界)≈≤;日(渐近紧界)≈=;2(渐近下界)≈≥;w(非渐近紧确下界)≈>;这里的<，s,=,2,>指的是规模上的比较,即o(n))的规模比g(n)小。

o(g())={f(n):对任意正常数C,存在常数n.>0,使对所有的n≥n,有0≤f(n)<cg(n)}O(g(n))={f(n):存在正常数c和n。

,使对所有n≥n。

,有0S(n)≤cg(n)}0(g(n)={f(n):存在正常数Cc.c和n。

,使对所有的n≥n,有0≤c,g(n)Sf(n)≤cg(n)}Q(g(n))={f(n):存在正常数c和n。

,使对所有n≥n,有0≤cg(n)Sf(n)}w(g())={f(n):对任意正常数c,存在常数n,>0.使对所有的n,有0≤cg(n)<f(n)}第4章:递归式1.递归式是一组等式或不等式,它所描述的函数是用在更小的输入下该函数的值来定义的。

快速排序（C语⾔）-解析快速排序快速排序是⼀种排序算法，对包含 n 个数的输⼊数组，最坏情况运⾏时间为O（n2）。

虽然这个最坏情况运⾏时间⽐较差，但快速排序通常是⽤于排序的最佳的实⽤选择，这是因为其平均性能相当好：期望的运⾏时间为O（nlgn），且O（nlgn）记号中隐含的常数因⼦很⼩。

另外，它还能够进⾏就地排序，在虚存环境中也能很好的⼯作。

快速排序（Quicksort）是对的⼀种改进。

快速排序由C. A. R. Hoare在1962年提出。

它的基本思想是：通过⼀趟排序将要排序的数据分割成独⽴的两部分，其中⼀部分的所有数据都⽐另外⼀部分的所有数据都要⼩，然后再按此⽅法对这两部分数据分别进⾏快速排序，整个排序过程可以进⾏，以此达到整个数据变成有序。

像合并排序⼀样，快速排序也是采⽤分治模式的。

下⾯是对⼀个典型数组A[p……r]排序的分治过程的三个步骤：分解：数组 A[p……r]被划分为两个（可能空）⼦数组 A[p……q-1] 和 A[q+1……r] ，使得 A[p……q-1] 中的每个元素都⼩于等于 A(q) , ⽽且，⼩于等于 A[q+1……r] 中的元素。

⼩标q也在这个划分过程中进⾏计算。

解决：通过递归调⽤快速排序，对于数组 A[p……q-1] 和 A[q+1……r] 排序。

合并：因为两个⼦数组是就地排序的，将它们的合并不需要操作：整个数组 A[p……r] 已排序。

下⾯的过程实现快速排序(伪代码)：QUICK SORT（A，p，r）1if p<r2 then q<-PARTITION(A,p,r)3 QUICKSORT(A,p,q-1)4 QUICKSORT(A,q+1,r)为排序⼀个完整的数组A，最初的调⽤是QUICKSORT（A，1，length[A]）。

数组划分： 快速排序算法的关键是PARTITION过程，它对⼦数组 A[p……r]进⾏就地重排(伪代码)：PARTITION（A，p，r）1 x <- A[r]2 i <- p-13for j <- p to r-14do if A[j]<=x5 then i <- i+16 exchange A[i] <-> A[j]7 exchange A[i + 1] <-> A[j]8return i+1排序演⽰⽰例假设⽤户输⼊了如下数组：下标012345数据627389创建变量i=0（指向第⼀个数据）, j=5(指向最后⼀个数据), k=6(为第⼀个数据的值)。

算法导论读书笔记算法导论读书笔记篇1《算法导论》是计算机科学中一门重要的课程，它是一本经典的算法教材，被广泛使用于各个领域。

这本书的作者是美国计算机科学家ChristopherD.H.Anderson，他是一位著名的计算机科学家和数学家，曾在斯坦福大学和卡内基梅隆大学任教。

这本书主要介绍了各种基本算法，包括排序、搜索、图论、动态规划、贪心算法、分治算法等。

它通过示例代码和问题解决的方式，向读者展示了如何使用这些算法来解决实际问题。

这本书的特点是简洁明了、易于理解、逻辑清晰、重点突出。

作者在书中使用了通俗易懂的语言和简单的例子，使得读者可以轻松地理解各种算法的原理和应用。

同时，作者还对各种算法进行了深入的分析和比较，使得读者可以更好地理解它们的优缺点和应用场景。

在阅读这本书的过程中，我深刻地感受到了算法的重要性和应用价值。

算法是一种解决问题的工具，它可以帮助我们快速地解决复杂的问题，提高工作效率。

同时，算法也是一种思维方式和解决问题的手段，它可以帮助我们更好地理解问题和现象，提高我们的逻辑思维能力和解决问题的能力。

在阅读这本书的过程中，我遇到了一些困难和挑战。

首先，书中的算法种类繁多，有些算法比较抽象，需要深入思考才能理解它们的原理和应用。

其次，书中的代码示例比较简单，需要自己动手实现才能更好地理解算法的原理和应用。

总的来说，《算法导论》是一本非常优秀的教材，它可以帮助我们更好地理解算法的原理和应用，提高我们的逻辑思维能力和解决问题的能力。

在未来的学习和工作中，我将继续深入学习和研究算法，不断提高自己的专业水平和实践能力。

算法导论读书笔记篇2《算法导论》是计算机科学中广泛使用的一种经典算法教材。

本书的目的是为学生提供一种系统而全面的算法学习体验，旨在帮助学生理解算法的基本原理，掌握常见算法的实现和应用，提高编程能力和解决问题的能力。

本书共有11个章节，涵盖了各种常见算法的介绍和实现，如排序、搜索、图论、动态规划、贪心算法等。