算法导论快速排序

A. 为什么《算法导论》中的数组序号是从1开始的

c语言下标从零开始是个错误，并且 index 也是一个有误导性的名词，它表示的是偏移量，明明应该用 offset。
然后 c 的徒子徒孙都学了它，导致现在很多人都误以为下标应该从 0 开始。
早期蛮荒时代，很多东西都不科学，算法导论作者致力于与落后文明作斗争，然而却遭到了楼主你的不理解，实乃编程届一大憾事。
我再说一遍，C 是结构化的汇编，下标基 0 是受到了 PDP-11 指令集的影响，更老的语言（比如 Fortran）都是基 1 的。
另外用 0/非 0 代表 false/true 也是 PDP-11 中 TST 指令和 Z 位的行为。
可能是这本书强调算法的求学思想，所以从一更加符合数学的数组规定。
但是编程的时候，指针这个东西会经常用到，如果用a(o)作为第一个元素 那么*a+n就等同于a(n) 比较方便
算法导论上的这个问题呢，我觉得我比较同意楼上的看法，这个书上面的很多的程序并不是可以敲上去直接运行的，他只是伪代码，思想而已，给人看的，人类的普遍思维是从1开始，那么书页就是从1开始了
说编程语言是给机器看而伪代码是给人看的简直是逗大家笑吧...编程语言设计出来就是给人看的....
另外从0开始在很多方便都极好....我觉得写多代码都能体会到吧..
帮算导洗地：
算法导论通篇用的是伪代码 是给人类阅读理解的 不是设计给机器去运行的
而绝大多数情况下， index 从 1 开始更符合人类直觉（如果你对这点有异议请参考的答案 ）
但少数情况下， index 从 0 开始更符合人类直觉。例如书中 hashing 还有 FFT 那块内容， index 是从 0 开始的。
其实写几天 Pascal 你就适应啦。。

B. 快速排序方法的时间复杂度为O(n^2）=n(n-1)/2.

1）对于你的问题简单解释如下：
理论计算机研究中，衡量算法一般从两个方面分析：时间复杂度和空间复杂度。空间复杂度跟时间复杂度是类似的，下面简单解释一下时间复杂度：返芦察对于一个数据规模为n的问题，解决该问题的算法所用时间可以用含有n的函数T(n)来表示。对于绝大多数情况，我们只需要了解算法的一般性能而不考虑细节，也就是说，我们只关心函数T(n)的表达式的形式，而不关心表达式的常数系数等与数据规模没有关系的量值。对于函数T(n)，我们又进一步将它简化为O(n)，即只考虑算法平均运行时间的“瓶颈”，也就是T(n)表达式中，关于变量n增长最快的哪一项。比如下面的代码：
for(int i=1; i<=n*2; i++)
for(int j=1; j<=n; j++)
// do something here
那么这个算法的时间复杂度就是O(n^2)，因为它有两层循环，每层循环的数据哗消规模都是n。注意第一层循环（外循环）要迭代n*2次，则实际上T(n)=2*n*n，而对于O(n)来说，我们忽略了常数2，只保留了n^2。这就是大O记法的一个概括，并不精确。
对于时间复杂度的更精确、深入的解释，可以自己查阅《算法导论》第一章。

2）更正你的问题：快速排序算法的时间复杂度应该为O(n lg n)。注意三种时间复杂度符号表示的不同意义！英文字母O代表的是平均运行时间，因此对于快速排序来说应该是O(n lg n)。而使用下界函数Omega或者上界函数Theta则分别表示算法运行的最快和最慢漏茄时间。对于未使用随机化的快速排序，理论上可以证明，存在某一方法构造出一组数据使快速排序“退化”成平方复杂度算法即Theta(n^2)。但是对于其O(n)表示法应该为O(n^2)。

C. 对1000个数排序 只需显示前十个数 用哪种排序算法

#include "stdio.h"
#include<锋渣庆string.h>梁缺
#include<math.h>
#include<algorithm>银握
using namespace std;

int main(void)
{
int n=1000;
int a[1000],i;
for(i=0;i<n;i++)scanf("%d",&a[i]);
sort(a,a+n);
for(i=0;i<10;i++)printf("%d ",a[i]);
puts("");
return 0;
}

D. 各类排序算法，实现对海量数据排序额，怎么做

由于数据范围在1000万，因此我们需要一个O(n)时间效率的算法，然而所有基于比较的算法最快只能达到O(nlgn)的时间效率，因此，所有的基于比较的算法都无法达到要求。而数的范围仅仅是2000000之内的整数，因此能开数组记录。
这里有一个不基于比较的排序，叫计数排序，具体代码实现以及备注：

void CountingSort(int a[], int b[], int n)
{
int c[100001], i, max = -MaxInt; //c[i]记录i出现的次数

memset(c, 0, sizeof(c));

for (i = 1; i <= n; i++)
{
c[a[i]]++;
if (a[i] > max)
max = a[i];
}

for (i = 1; i <= max; i++) //c[i]记录i现在该出现的位置
{
c[i] += c[i - 1];
}

for (i = n; i >= 1; i--)
{
b[c[a[i]]] = a[i]; //排序
c[a[i]]--; //更新
}
}

E. 基于比较的排序算法

    基于比较的排序算法，应该是最符合人们直觉的方法。在各种算法的技术书上，已经证明了基于比较的排序算法的时间最优复杂度为O(nlogn)。

    下面是几种常见的基于比较的排序算法：

    1. 选择排序：这应该是最直观的排序方法。在排序n个元素时，第一次遍历，找到最小的元素，将其与第一个元素互换；第二次遍历，找到次小的元素，将其与第二个元素交换；直至剩下最后一个元素。

    2. 冒泡排序：这应该是我们学到的第一种排序算法。基本思想就是，通过依次比较相邻的两个元素，如后值比前值小，则交换这两个值，小值被交换到前面，大值被交换到后面。这样一次遍历后，最大值被放到最后。而小值被交换到n-1前。然后再次遍历前n-1，n-2，直至最后2个元素。整个儿过程，小值随着不断的遍历过程，逐渐被交换到前面，很像气泡逐渐从水底逐渐冒出。所以被称为冒泡算法。

    3. 插入排序：这个算法的思想很直观。按照《算法导论》中的解释，这个算法可以参照我们平时打扑克的情形。当抓取一张牌的时候，按顺序比较手牌，将其插入到恰当的位置。这样保证了手中所有的牌依然有序。当已排序的值数量较多时，由于已经保证了有序，那么在确定新值插入位置的时候，可以通过二分查找的方法来去确定插入位置。

    4. 希尔排序：在冒泡算法中，所以小值只能以步长为1的速度向前面移动。希尔排序在步长上作了优化，开始以一个较大的m步长进行分组，每组进行插入排序，这样就实现了步长为m的移动。然后逐渐缩小步长m直至1。所以根本思想是尽可能的将元素移动较远的位置代替移动一位。

5.归并排序：该思想利用的是解决问题的一个常用思想，divide-and-conquer，即分而治之的思想。将n个元素每次2分，变为两个n/2个元素组，直至1个元素——1个元素，自然是排好序了。然后，再两两合并元素组，最终合并为一个元素组。归并算法，因为需要归并，所以必然需要一个额外的n空间来实现归并。

    6.快速排序：同样是分而治之的思想，将原始数据分为2组。但是与归并算法直接将原始数据分为两部分不同的是，快排选择一个中值，新的两个子组，一个子组所有的元素都小于中值，另外一个子组所有的元素都大于等于中值，直至元素个数为1。当元素个数为1时，实际上快排已经完成了排序。这点与归并排序也不同，快排在子组完成以后，无需额外的操作。很明显，快排的效率依赖于中值的选择。如果中值可以将数据分为两个数量相等的子组，那么效率则为最高的。快排无需额外的存储空间，可以in-place进行排序。

    7.堆排序：该思想是将原始元素视为一个平衡二叉树。然后要求父节点必须大于子节点的规则，调整该平衡二叉树。由于是平衡二叉树，所以数据被完美的等分。这样根节点即为最大值。这时，堆排序完成了最大值的选择。为排序，则将根节点与最后一个子节点交换。此时，树的规则被破坏，需要从根节点逐级verify规则。

F. 快速排序方法的时间复杂度为O(n^2)=n(n-1)/2中O()是什么意思

O(1): 表示算法的运行时间为常量

O(n): 表示该算法是线性算法

O(㏒2n): 二分查找算法

O(n2): 对数组进行排序的各种简单算法，例如直接插入排序的算法。

O(n3): 做两个n阶矩阵的乘法运算

O(2n): 求具有n个元素集合的所有子集的算法

O(n!): 求具有N个元素的全排列的算法
O(n²)表示当n很大的时候，复杂度约等于Cn²，C是某个常数，简单说就是当n足够大的时候，n的线性增长，复杂度将沿平方增长。
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))
为算法的渐进时间复杂度，简称时间复杂度。

G. 《算法导论》（第三版）目录

1.1 算法

1.2 作为一种技术的算法

2.1 插入排序

2.2 分析算法

2.3 设计算法

2.3.1 分治法

2.3.2 分析分治算法

3.1 渐近记号

3.2 标准记号与常用函数

4.1 最大子数组问题

4.2 矩阵乘法的 Strassen 算法

4.3 用代入法求解递归式

4.4 用递归树方法求解递归式

4.5 用主方法求解递归式

*4.6 证明主定理

4.6.1 对 b 的幂证明主定理

4.6.2 向下取整和向上取整

5.1 雇佣问题

5.2 指示器随机变量

5.3 随机算法

*5.4 概率分析和指示器随机变量的进一步使用

5.4.1 生日悖论

5.4.2 球与箱子

5.4.3 特征序列

5.4.4 在线雇佣问题

6.1 堆

6.2 维护堆的性质

6.3 建堆

6.4 堆排序算法

6.5 优先队列

7.1 快速排序的描述

7.2 快速排序的性能

7.3 快速排序的随机化版本

7.4 快速排序分析

7.4.1 最坏情况分析

7.4.2 期望运行时间

8.1 排序算法的下界

8.2 计数排序

8.3 基数排序

8.4 桶排序

9.1 最小值和最大值

9.2 期望为线性时间的选择算法

9.3 最坏情况为线性时间的选择算法

10.1 栈和队列

10.2 链表

10.3 指针和对象的实现

10.4 有根树的表示

11.1 直接寻址表

11.2 散列表

11.3 散列函数

11.3.1 除法散列法

11.3.2 乘法散列法

*11.3.3 全域散列法

11.4 开放寻址法

11.5 完全散列

12.1 什么是二叉树

12.2 查询二叉搜索树

12.3 插入和删除

12.4 随机构建二叉搜索树

13.1 红黑树的性质

13.2 旋转

13.3 插入

13.4 删除

14.1 动态顺序统计

14.2 如何扩张数据结构

14.3 区间树

15.1 钢条切割

15.2 矩阵链乘法

15.3 动态规划原理

15.4 最长公共子序列

15.5 最优二叉搜索树

16.1 活动选择问题

16.2 贪心算法原理

16.3 赫夫曼编码

*16.4 拟阵和贪心算法

*16.5 用拟阵求解任务调度问题

17.1 聚合分析

17.2 核算法

17.3 势能法

17.4 动态表

17.4.1 表扩张

17.4.2 表扩张和收缩

18.1 B 树的定义

18.2 B 树上的基本操作

18.3 从 B 树上删除关键字

19.1 斐波那契结构

19.2 可合并堆操作

19.3 关键字减值和删除一个结点

19.4 最大度数的界

20.1 基本方法

20.2 递归结构

20.2.1 原型 van Emde Boas 结构

20.2.2 原型 van Emde Boas 结构上的操作

20.3 van Emde Boas 树及其操作

20.3.1 van Emde Boas 树

20.3.2 van Emde Boas 树的操作

21.1 不相交集合的操作

21.2 不相交集合的链表表示

21.3 不相交集合森林

*21.4 带路径压缩的按秩合并的分析

22.1 图的表示

22.2 广度优先搜索

22.3 深度优先搜索

22.4 拓扑排序

22.5 强连通分量

23.1 最小生成树的形成

23.2 Kruskal 算法和 Prim 算法

24.1 Bellman-Ford 算法

24.2 有向无环图中的单源最短路径问题

24.3 Dijkstra 算法

24.4 差分约束和最短路径

24.5 最短路径性质的证明

25.1 最短路径和矩阵乘法

25.2 Floyd-Warshall 算法

25.3 用于稀疏图的 Johnson 算法

26.1 流网络

26.2 Ford-Fulkerson 方法

26.3 最大二分匹配

*26.4 推送-重贴标签算法

*26.5 前置重贴标签算法

27.1 动态多线程基础

27.2 多线程矩阵乘法

27.3 多线程归并排序

28.1 求解线性方程组

28.2 矩阵求逆

28.3 对称正定矩阵和最小二乘逼近

29.1 标准型和松弛型

29.2 将问题表达为线性规划

29.3 单纯形算法

29.4 对偶性

29.5 初始基本可行解

30.1 多项式的表示

30.2 DFT 和 FFT

30.3 高效 FFT 实现

31.1 基础数论概念

31.2 最大公约数

31.3 模运算

31.4 求解模线性方程

31.5 中国余数定理

31.6 元素的幂

31.7 RSA 公钥加密系统

*31.8 素数的测试

*31.9 整数的因子分解

32.1 朴素字符串匹配算法

32.2 Rabin-Karp 算法

32.3 利用有限自动机进行字符串匹配

32.4 Knuth-Morris-Pratt 算法

33.1 线段的性质

33.2 确定任意一对线段是否相交

33.3 寻找凸包

33.4 寻找最近点对

34.1 多项式时间

34.2 多项式时间的验证

34.3 NP 完全性与可归约性

34.4 NP 完全性的证明

34.5 NP 完全问题

34.5.1 团问题

34.5.2 顶点覆盖问题

34.5.3 哈密顿回路问题

34.5.4 旅行商问题

34.5.5 子集和问题

35.1 顶点覆盖问题

35.2 旅行商问题

35.2.1 满足三角不等式的旅行商问题

35.2.2 一般旅行商问题

35.3 集合覆盖问题

35.4 随机化和线性规划

35.5 子集和问题

A.1 求和公式及其性质

A.2 确定求和时间的界

B.1 集合

B.2 关系

B.3 函数

B.4 图

B.5 树

B.5.1 自由树

B.5.2 有根树和有序树

B.5.3 二叉树和位置树

C.1 计数

C.2 概率

C.3 离散随机变量

C.4 几何分布与二项分布

C.5 二项分布的尾部

D.1 矩阵与矩阵运算

D.2 矩阵的基本性质

H. 如何从最大的N个数中选出最大或者最小的n个数

首先，我们假设n和N都是内存可容纳的，也就是说N个数可以一次load到内存里存放在数组里（如果非要存在链表估计又是另一个challenging的问题了）。从最简单的情况开始，如果n=1，那么没有任何疑惑，必须要进行N-1次的比较才能得到最大的那个数，直接遍历N个数就可以了。如果n=2呢？当然，可以直接遍历2遍N数组，第一遍得到最大数max1，但是在遍历第二遍求第二大数max2的时候，每次都要判断从N所取的元素的下标不等于max1的下标，这样会大大增加比较次数。对此有一个解决办法，可以以max1为分割点将N数组分成前后两部分，然后分别遍历这两部分得到两个最大数，然后二者取一得到max2。 也可以遍历一遍就解决此问题，首先维护两个元素max1，max2（max1=max2），取到N中的一个数以后，先和max1比，如果比max1大（则肯定比max2大），直接替换max1，否则再和max2比较确定是否替换max2。采用类似的方法，对于n=2，3，4一样可以处理。这样的算法时间复杂度为O（nN）。当n越来越大的时候（不可能超过N/2，否则可以变成是找N-n个最小的数的对偶问题），这个算法的效率会越来越差。但是在n比较小的时候（具体多小不好说），这个算法由于简单，不存在递归调用等系统损耗，实际效率应该很不错. 堆：当n较大的时候采用什么算法呢？首先我们分析上面的算法，当从N中取出一个新的数m的时候，它需要依次和max1，max2，max3max n比较，一直找到一个比m小的max x，就用m来替换max x，平均比较次数是n/2。可不可以用更少的比较次数来实现替换呢？最直观的方法是，也就是网上文章比较推崇的堆。堆有这么一些好处：1.它是一个完全二叉树，树的深度是相同节点的二叉树中最少的，维护效率较高；2.它可以通过数组来实现，而且父节点p与左右子节l，r点的数组下标的关系是s[l] = 2*s[p]+1和s[r] = 2*s[p]+2。在计算机中2*s[p]这样的运算可以用一个左移1位操作来实现，十分高效。再加上数组可以随机存取，效率也很高。3.堆的Extract操作，也就是将堆顶拿走并重新维护堆的时间复杂度是O（logn），这里n是堆的大小。 具体到我们的问题，如何具体实现呢？首先开辟一个大小为n的数组区A，从N中读入n个数填入到A中，然后将A维护成一个小顶堆（即堆顶A[0]中存放的是A中最小的数）。然后从N中取出下一个数，即第n+1个数m，将m与堆顶A[0]比较，如果m<=A[0]，直接丢弃m。否则应该用m替换A[0]。但此时A的堆特性可能已被破坏，应该重新维护堆：从A[0]开始，将A[0]与左右子节点分别比较（特别注意，这里需要比较两次才能确定最大数，在后面我会根据这个来和败者树比较），如果A[0]比左右子节点都小，则堆特性能够保证，勿需继续，否则如左（右）节点最大，则将A[0]与左（右）节点交换，并继续维护左（右）子树。依次执行，直到遍历完N，堆中保留的n个数就是N中最大的n个数。 这都是堆排序的基本知识，唯一的trick就是维护一个小顶堆，而不是大顶堆。不明白的稍微想一下。维护一次堆的时间复杂度为O（logn），总体的复杂度是O（Nlogn）这样一来，比起上面的O（nN），当n足够大时，堆的效率肯定是要高一些的。当然，直接对N数组建堆，然后提取n次堆顶就能得到结果，而且其复杂度是O（nlogN）,当n不是特别小的时候这样会快很多。但是对于online数据就没办法了，比如N不能一次load进内存，甚至是一个流，根本不知道N是多少。 败者树：有没有别的算法呢？我先来说一说败者树（loser tree）。也许有些人对loser tree不是很了解，其实它是一个比较经典的外部排序方法，也就是有x个已经排序好的文件，将其归并为一个有序序列。败者树的思想咋一看有些绕，其实是为了减小比较次数。首先简单介绍一下败者树：败者树的叶子节点是数据节点，然后两两分组（如果节点总数不是2的幂，可以用类似完全树的结构构成树），内部节点用来记录左右子树的优胜者中的败者（注意记录的是输的那一方），而优胜者则往上传递继续比较，一直到根节点。如果我们的优胜者是两个数中较小的数，则根节点记录的是最后一次比较中的败者，也就是所有叶子节点中第二小的那个数，而最小的那个数记录在一个独立的变量中。这里要注意，内部节点不但要记录败者的数值，还要记录对应的叶子节点。如果是用链表构成的树，则内部节点需要有指针指向叶子节点。这里可以有一个trick，就是内部节点只记录败者对应的叶子节点，具体的数值可以在需要的时候间接访问（这一方法在用数组来实现败者树时十分有用，后面我会讲到）。关键的来了，当把最小值输出后，最小值所对应的叶子节点需要变成一个新的数（或者改为无穷大，在文件归并的时候表示文件已读完）。接下来维护败者树，从更新的叶子节点网上，依次与内部节点比较，将败者更新，胜者往上继续比较。由于更新节点占用的是之前的最小值的叶子节点，它往上一直到根节点的路径与之前的最小值的路径是完全相同的。内部节点记录的败者虽然称为败者，但却是其所在子树中最小的数。也就是说，只要与败者比较得到的胜者，就是该子树中最小的那个数（这里讲得有点绕了，看不明白的还是找本书看吧，对照着图比较容易理解）。 注：也可以直接对N构建败者树，但是败者树用数组实现时不能像堆一样进行增量维护，当叶子节点的个数变动时需要完全重新构建整棵树。为了方便比较堆和败者树的性能，后面的分析都是对n个数构建的堆和败者树来分析的。 总而言之，败者树在进行维护的时候，比较次数是logn+1。与堆不同的是，败者树是从下往上维护，每上一层，只需要和败者节点比较一次即可。而堆在维护的时候是从上往下，每下一层，需要和左右子节点都比较，需要比较两次。从这个角度，败者树比堆更优一些。但是，请注意但是，败者树每一次维护必定需要从叶子节点一直走到根节点，不可能中间停止；而堆维护时，有可能会在中间的某个层停止，不需要继续往下。这样一来，虽然每一层败者树需要的比较次数比堆少一倍，但是走的层数堆会比败者树少。具体少多少，从平均意义上到底哪一个的效率会更好一些？那我就不知道了，这个分析起来有点麻烦。感兴趣的人可以尝试一下，讨论讨论。但是至少说明了，也许堆并非是最优的。 具体到我们的问题。类似的方法，先构建一棵有n个叶子节点的败者树，胜出者w是n个中最小的那一个。从N中读入一个新的数m后，和w比较，如果比w小，直接丢弃，否则用m替换w所在的叶子节点的值，然后维护该败者树。依次执行，直到遍历完N，败者树中保留的n个数就是N中最大的n个数。时间复杂度也是O（Nlogn） 类快速排序方法： 快速排序大家大家都不陌生了。主要思想是找一个轴节点，将数列交换变成两部分，一部分全都小于等于轴，另一部分全都大于等于轴，然后对两部分递归处理。其平均时间复杂度是O（NlogN）。从中可以受到启发，如果我们选择的轴使得交换完的较大那一部分的数的个数j正好是n，不也就完成了在N个数中寻找n个最大的数的任务吗？当然，轴也许不能选得这么恰好。可以这么分析，如果jn，则最大的n个数肯定在这j个数中，则问题变成在这j个数中找出n个最大的数；否则如果j<n，则这j个数肯定是n个最大的数的一部分，而剩下的j-n个数在小于等于轴的那一部分中，同样可递归处理。 需要注意的是，这里的时间复杂度是平均意义上的，在最坏情况下，每次分割都分割成1：N-2，这种情况下的时间复杂度为O（n）。但是我们还有杀手锏，可以有一个在最坏情况下时间复杂度为O（N）的算法，这个算法是在分割数列的时候保证会按照比较均匀的比例分割，at least 3n/10-6。具体细节我就不再说了，感兴趣的人参考算法导论（Introction to Algorithms 第二版第九章 Medians and Orders Statistics）。 还是那个结论，堆不见得会是最优的。 本文快要结束了，但是还有一个问题：如果N非常大，存放在磁盘上，不能一次装载进内存呢？怎么办？对于介绍的Naive方法，堆，败者树等等，依然适用，需要注意的就是每次从磁盘上尽量多读一些数到内存区，然后处理完之后再读入一批。减少IO次数，自然能够提高效率。而对于类快速排序方法，稍微要麻烦一些：分批读入，假设是M个数，然后从这M个数中选出n个最大的数缓存起来，直到所有的N个数都分批处理完之后，再将各批次缓存的n个数合并起来再进行一次类快速排序得到最终的n个最大的数就可以了。在运行过程中，如果缓存数太多，可以不断地将多个缓存合并，保留这些缓存中最大的n个数即可。由于类快速排序的时间复杂度是O（N），这样分批处理再合并的办法，依然有极大的可能会比堆和败者树更优。当然，在空间上会占用较多的内存。 总结：对于这个问题，我想了很多，但是觉得还有一些地方可以继续深挖：1. 堆和败者树到底哪一个更优？可以通过理论分析，也可以通过实验来比较。也许会有人觉得这个很无聊；2. 有没有近似的算法或者概率算法来解决这个问题？我对这方面实在不熟悉，如果有人有想法的话可以一块交流。如果有分析错误或遗漏的地方，请告知，我不怕丢人，呵呵！最后请时刻谨记，时间复杂度不等于实际的运行时间，一个常数因子很大的O（logN）算法也许会比常数因子小的O（N）算法慢很多。所以说，n和N的具体值，以及编程实现的质量，都会影响到实际效率。

I. 快速排序法 平均情况时间复杂度

快速森世排序时间复杂度穗洞可以此族肢写成
T(n)=2T(n/2)+n,这个求解就是T(n)=nlogn

J. 《算法导论》（原书第二版）。这本书里面的程序是用什么写的是java吗

这本书的程序是用伪代码加英文注释写的，学过C/C++/JAVA的都能看懂。

原书摘录如下（快速排序）：
QUICKSORT'(A,p,r)
while p<r
do △ Partition and sort left subarray.
q <- PARTITION(A,p,r)
QUICKSORT'(A,p,q-1)
p <- q+1