软件设计师 http://www.educity.cn/jiaocheng/zg7.html
部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O（nlog2n）。快速排序在系统内部需要一个栈来实现递归。若每次划分较为均匀，则其递归树的高度为O（log2n），故递归后需栈空间为O（log2n）。在最坏的情况下，递归树的高度为O（n），所需的栈空间为O（n）。快速排序是不稳定的。
1.4.4 归并排序
归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时，把含有n个结点的待排序序列看做由n个长度都为1的有序子表所组成，将它们依次两两归并得到长度为2的若干有序子表，再对它们两两合并。直到得到长度为n的有序表，排序结束。 例如，我们需要对关键码{72,28,51,17,96,62,87,33}进行排序，其归并过程如图1-26所示。
归并排序是一种稳定的排序，可用顺序存储结构，也易于在链表上实现。对长度为n的文件，需进行log2n趟二路归并，每趟归并的时间为O（n），故其时间复杂度无论是在最好情况下还是在最坏情况下均是O（nlog2n）。归并排序需要一个辅助向量来暂存两个有序子文件归并的结果，故其辅助空间复杂度为O（n），显然它不是就地排序。
1.4.5 基数排序
设单关键字的每个分量的取值范围均是C0≤kj≤Crd–1（0≤j 软件设计师 http://www.educity.cn/jiaocheng/zg7.html 称为基数。基数的选择和关键字的分解因关键字的类型而异。 （1）若关键字是十进制整数，则按个、十等位进行分解，基数rd=10,C0=0,C9=9,d为最长整数的位数。 （2）若关键字是小写的英文字符串，则rd=26,C0='a',C25='z',d为字符串的最大长度。 基数排序的基本思想是：从低位到高位依次对待排序的关键码进行分配和收集，经过d趟分配和收集，就可以得到一个有序序列。 基数排序的具体实现过程如下：设有r个队列，队列的编号分别为0,1,2,…，r–1.首先按最低有效位的值把n个关键字分配到这r个队列中；然后从小到大将各队列中的关键字再依次收集起来；接着再按次低有效位的值把刚刚收集起来的关键字分配到r个队列中。重复上述收集过程，直至最高有效位，这样便得到一个从小到大的有序序列。为减少记录移动的次数，队列可以采用链式存储分配，称为链式基数排序。每个队列设有两个指针，分别指向队头和队尾。 例如，需要对{288,371,260,531,287,235,56,299,18,23}进行排序，因为这些数据最高位为百位，所以需要3趟分配和收集。第1趟分配和收集（按个位数）的过程如图1-16所示；第2趟分配与收集（按十位数）的过程如图1-17所示；第3趟分配与收集（按百位数）的过程如图1-18所示。 图1-27 第1趟分配与收集 软件设计师 http://www.educity.cn/jiaocheng/zg7.html 图1-28 第2趟分配与收集 图1-29 第3趟分配与收集 基数排序的时间复杂度为O（d（r+n）），所需的辅助存储空间为O（n+rd），基数排序是稳定的。 1.4.6 算法复杂性比较 在此，我们把常用的排序算法的复杂度进行列表，如表1-3所示。 表1-3 排序算法时间复杂度表 软件设计师 http://www.educity.cn/jiaocheng/zg7.html 注：rd称为基数，基数的选择和关键字的分解因关键字的类型而异。 1.5 查找 查找是指给定一个值k,在含有n个结点的表中找出关键字等于给定值k的结点。若找到，则查找成功，返回该结点的信息或该结点在表中的位置；否则查找失败，返回相关的指示信息。若在查找的同时对表做修改操作（如插入和删除），则相应的表称之为动态查找表，否则称之为静态查找表。 查找运算的主要操作是关键字的比较，所以通常把查找过程中对关键字需要执行的平均比较次数（也称为平均查找长度）作为衡量一个查找算法效率优劣的标准。平均查找长度ASL定义为： 其中n是结点的个数，pi是查找第i个结点的概率。若不特别声明，认为每个结点的查找概率相等，即p1=p2=…=pn=1/n;ci是找到第i个结点所需进行的比较次数。 1.5.1 顺序查找 软件设计师 http://www.educity.cn/jiaocheng/zg7.html 顺序查找的基本思想是从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和给定值k相比较。若当前扫描到的结点关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的结点，则查找失败。顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构。 成功时的顺序查找的平均查找长度如下： 在等概率情况下，pi=1/n（1≤i≤n），故成功的平均查找长度为（n+…+2+1）/n=（n+1）/2, 即查找成功时的平均比较次数约为表长的一半。若k值不在表中，则需进行（n+1）次比较之后才能确定查找失败。 若事先知道表中各结点的查找概率不相等和它们的分布情况，则应将表中结点按查找概率由小到大地存放，以便提高顺序查找的效率。 顺序查找的优点是算法简单，且对表的结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。缺点是查找效率低，因此，当n较大时不宜采用顺序查找。 1.5.2 二分法查找 二分法查找又称折半查找，它是一种效率较高的查找方法。二分法查找要求线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。 二分法查找的基本思想是：（设R[low,…，high]是当前的查找区间） ①确定该区间的中点位置：mid=[（low+high）/2]; ②将待查的k值与R[mid].key比较，若相等，则查找成功并返回此位置，否则需确定