快速排序算法导论

① 计算机科学的“两本圣经”是什么

第一本：《算法导论》原书名——《Introction to Algorithms》，

第二本：高德纳（Donald E.Knuth）的《计算机程序设计艺术》（《The Art Of Computer Programming》）

计算机科学是一门包含各种各样与计算和信息处理相关主题的系统学科，从抽象的算法分析、形式化语法等等，到更具体的主题如编程语言、程序设计、软件和硬件等。计算机科学分为理论计算机科学和实验计算机科学两个部分。

(1)快速排序算法导论扩展阅读：

研究课题

①、计算机程序能做什么和不能做什么（可计算性）；

②、如何使程序更高效的执行特定任务（算法和复杂性理论）；

③、程序如何存取不同类型的数据（数据结构和数据库）；

④、程序如何显得更具有智能（人工智能）；

⑤、人类如何与程序沟通（人机互动和人机界面）。

相关奖项

计算机科学领域的最高荣誉是ACM设立的图灵奖，被誉为是计算机科学的诺贝尔奖。它的获得者都是本领域最为出色的科学家和先驱。华人中首获图灵奖的是姚期智先生.他于2000年以其对计算理论做出的诸多“根本性的、意义重大的”贡献而获得这一崇高荣誉。

专业介绍

培养目标

本专业培养德、智、体全面发展，具有计算机应用技术的基础理论知识，具备计算机及相关设备的维护与维修、行业应用软件、平面图像处理、广告设计制作、动画制作、计算机网络及网站建设与管理、数据库管理与维护等应用能力和操作能力的高等技术应用性人才。

计算机应用基础、计算机组装与维护、计算机局域网络的建设与管理、网络工程、操作系统、服务器、数据库的开发与应用、网站建设与网页设计、C/C++语言、Visual Basic语言、平面设计、3D图形设计、多媒体设计、专业英语。

就业方向

毕业生主要面向交通系统各单位、交通信息化与电子政务建设与应用部门、各类计算机专业化公司、广告设计制作公司、汽车营销技术服务等从事IT行业工作。

参考资料：网络-计算机科学

② 《算法导论》（原书第二版）。这本书里面的程序是用什么写的是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

③ 为什么《算法导论》中的数组序号是从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 你就适应啦。。

④ 算法导论中的快排算法实现出错

我未学过pascal，但看你的代码总觉得posion函数有问题，下面是我的C代码，不知你能否看懂
int Posion(int *ar,int l,int h){
int k=ar[l];
while(l<h){
while(l<h&&k<=ar[h])
h--;
ar[l]=ar[h];
while(l<h&&k>=ar[l])
l++;
ar[h]=ar[l];
}
ar[l]=k;
return l;
}

⑤ 数据结构 如何快速排序

这个过程对于初学者的确有点复杂，建议你看下严蔚敏数据结构书上的例子，多耐心看下，然后再看代码。另外也可以参考下算法导论，关于快排这本书有单独章节讲解。自己去弄懂会很深刻的。

⑥ 快速排序算法问题，看看大家的思路

/*刚看了下算法导论，写了一个，感觉效率还可以，你看看 */
#include <stdio.h>

static int a[8] = {3, 7, 2, 8, 4, 5, 3, 9};

void swap (int *m, int *n)
{
int temp = *m;
*m = *n;
*n = temp;
}

int partition (int p, int r)
{
int j;
int x = a[r];
int i = p - 1;

for (j=p; j<r; j++)
{
if (a[j] <= x)
{
i++;
swap(&a[i], &a[j]);
}
}
swap(&a[i+1], &a[r]);

return i+1;
}

void quicksort (int p, int r)
{
int q;

if (p < r)
{
q = partition (p, r);
quicksort (p, q - 1);
quicksort (q+1, r);
}
}

int main ()
{
int i;
int len = sizeof(a) / 4;

for (i=0; i<len; i++)
printf ("%d ", a[i]);
printf ("\n");

quicksort (0, len - 1);

for (i=0; i<len; i++)
printf ("%d ", a[i]);
printf ("\n");

return 0;
}
/* 我空间里还有一篇文章是关于qsort的，glibc里的源码，我也没怎么看懂，感兴趣可以研究下 */
刚才看了楼上给出的网址，文章写的不错，里面给的网址对qsort的分析也很透彻，感觉人外有人，学习的路还很长阿。

⑦ C语言一个快速排序的问题 我应该是传参的问题 但我不知道该如何改 请大师指教 谢谢

下面是《算法导论》里快速排序的实现，希望对你有用：

#include<stdio.h>
voidswap(int*a,int*b){
intt=*a;
*a=*b;
*b=t;
return;
}
intpartition(inta[],intstart,intend){
intx=a[end];
inti=start-1;
intj;
for(j=start;j<=end-1;j++){
if(a[j]<=x){
i+=1;
swap(a+i,a+j);
}
}
swap(a+i+1,a+end);
returni+1;
}

voidqsort(inta[],intstart,intend){
if(start>=end)return;
intp=partition(a,start,end);
qsort(a,start,p-1);
qsort(a,p+1,end);
}

voidprint(inta[],intstart,intend){
inti;
for(i=start;i<=end;i++)
printf("%d",a[i]);
printf("
");
return;
}

intmain(void){
inta[5]={1,1,2,2,3};
inti;
qsort(a,0,4);
print(a,0,4);
printf("Pleaseinput5numbers:
");
while(1){
for(i=0;i<=4;i++)
scanf("%d",a+i);
qsort(a,0,4);
print(a,0,4);
}
return0;
}

⑧ 快速排序的代码，跟我们学的不一样，大神解释一下。

快排一般我们采用第一个或者最后一个元素作为枢纽元 这里是采用任意一个元素作为枢纽元

具体的解释可参考《算法导论》快速排序那一小节

⑨ 谁能举个例子解释一下，什么是快速排序，冒泡排序，直接插入排序，堆序法thx

快速排序：quicksort: 找数组中一个数，把比他大的放到左边，比他小的放到右边，然后用递归排他左右边的，直到排完，复杂度O（nlgn）。
4,2,1,6，5.开始选4-2，1，4，6，5，再在2，1里选2-1，2，在6，5里选6-5，6 这样就完了1，2，4，5，6.

冒泡排序： bubblesort：简单的方法，从第一个数开始，依次和后面比较，比后面大就往后移动，直到排完，举例： 5，1，2，3，4. 先看5-1，5，2，3，4-1，2，5，3，4-1，2，3，5，4-1，2，3，4，5.这例子特殊，一下排完，事实上复杂度为O（n*n）；
插入排序： insertion sort： 简单的方法，和打牌时排序一样，复杂度O（n*n）
1，3，2，4，7，5-1，2，3，4，7，5-1，2，3，4，5，7.

堆： heapsort： 和树比较像，有根大枝小或根小枝大的特点，很难讲明白，时间复杂度为O（n*lgn）

建议看《算法导论》，或《programming pearls》 很清楚。

⑩ 算法导论的作品目录

目录（Table of Contents）
前言（Preface）
第一部分（Part I） 基础（Foundations）
第一章 计算中算法的角色（The Role of Algorithms in Computing）
第二章 开始（Getting Started）
第三章 函数的增长率（Growth of Functions）
第四章 递归（Recurrences）
第五章 概率分析与随机化算法（Probabilistic Analysis and Randomized Algorithms）
第二部分（Part II） 排序与顺序统计（Sorting and Order Statistics）
第六章 堆排序（Heapsort）
第七章快速排序（Quicksort）
第八章 线性时间中的排序（Sorting in Linear Time）
第九章 中值与顺序统计（Medians and Order Statistics）
第三部分（Part III） 数据结构（Data Structures）
第十章 基本的数据结构（Elementary Data Structures）
第十一章 散列表（Hash Tables）
第十二章 二叉查找树（Binary Search Trees）
第十三章 红-黑树（Red-Black Trees）
第十四章 扩充的数据结构（Augmenting Data Structures）
第四部分（Part IV） 高级的设计与分析技术（Advanced Design and Analysis Techniques）
第十五章 动态规划（Dynamic Programming）
第十六章 贪婪算法（Greedy Algorithms）
第十七章 分摊分析（Amortized Analysis）
第五部分（Part V） 高级的数据结构（Advanced Data Structures）
第十八章 B-树（B-Trees）
第十九章 二项式堆（Binomial Heaps）
第二十章 斐波纳契堆（Fibonacci Heaps）
第二十一章 不相交集的数据结构（Data Structures for Disjoint Sets）
第六部分（Part VI） 图算法（Graph Algorithms）
第二十二章 基本的图算法（Elementary Graph Algorithms）
第二十三章 最小生成树（Minimum Spanning Trees）
第二十四章单源最短路径（Single-Source Shortest Paths）
第二十五章 全对的最短路径（All-Pairs Shortest Paths）
第二十六章 最大流（Maximum Flow）
第七部分（Part VII） 精选的主题（Selected Topics）
第二十七章 排序网络（Sorting Networks）
第二十八章矩阵运算（Matrix Operations）
第二十九章 线性规划（Linear Programming）
第三十章 多项式与快速傅里叶变换（Polynomials and the FFT）
第三十一章 数论算法（Number-Theoretic Algorithms）
第三十二章 字符串匹配（String Matching）
第三十三章 计算几何学（Computational Geometry）
第三十四章 NP-完备性（NP-Completeness）
第三十五章 近似算法（Approximation Algorithms）
第八部分（Part VIII） 附录：数学背景（Mathematical Background）
附录A 求和（Summations）
附录B 集合，等等。（Sets, Etc.）
附录C 计数与概率（Counting and Probability）
参考文献（Bibliography）
索引（Index）