数据结构课件第3章 排序.ppt

《数据结构课件第3章 排序.ppt》由会员分享，可在线阅读，更多相关《数据结构课件第3章 排序.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第三章 排序,学习的意义：,早期的计算机约有一半的时间花在排序操作上，虽然随着计算机速度的提高，排序操作不再像早期那样占用计算机过多的时间，但它仍然是信息处理中最常用，也是最重要的运算之一。 实际上，在计算机科学中，排序仍然是组织数据最基本的运算，许多程序和软件均以它作为一个中间步骤。因此，人们设计了大量的排序算法以满足不同的需求。 计算机图灵奖获得者，著名计算机科学家D.E.Knuth在他的巨著Art of Computer Programming中列举分析了25中经典排序方法，并且指出，这只是现有方法中的“一小部分”。,3.1 排序的基本概念 3.2 简单的排序方法 3.2.1 插入排序

2、3.2.2 起泡排序 3.3 先进的排序方法 3.3.1 快速排序 3.3.2 归并排序 3.3.3 堆排序 3.4 基数排序 3.4 各种排序方法的综合比较,主要内容：,在很多情况下，相对于无序表而言，使用有序表可以提高算法效率，因为有序表可以充分利用其有序性采用一些效率较高的算法，例如，在进行数据元素的查找时，采用有序表比无序表效率要高很多。 如何得到有序表？我们可以在构造顺序表的时候依顺序表的有序性进行数据元素的插入，从而求得有序表。 更多的时候，我们需要对一个无序的顺序表进行“排序”，将它转化为“有序”的顺序表。,3. 1 排序的基本概念,排序 是按关键字的非递减或非递增顺序对一组记录

3、重新进行整队(或)排列的操作.,姓名 电话号码 蔡颖 63214444 陈红 63217777 刘建平 63216666 王小林 63218888 张力 63215555 .,3. 1 排序的基本概念,例1、高考考生信息管理系统提供了将考生按总分排序、按单科排序的功能； 例2、数学中的数列（11，13，15，17，19，21）例3、英文字母表（A, B, C, D, E Z ）。例4、某单位的电话号码簿。,排序的定义,排序的形式化描述,假设含有n个记录的序列为： r1,r2,r3,rn 它们的关键字相应为： k1,k2,k3,kn 对记录序列进行排序就是确定序号1,2,3,n的一种排列： p1

4、,p2,p3,pn 使其相应的关键字满足非递减或非递增的关系 kp1 kp2 kp3。 kpn 也就是使记录序列重新排列成为一个按关键字有序的序列,排序分类,什么叫内部排序？什么叫外部排序？,若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；称为内部排序； 反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。,注：外部排序时，要将数据分批调入内存来排序，中间结果还要及时放入外存，显然外部排序要复杂得多。,内部排序的算法有哪些？,按排序的规则不同，可分为5类： 插入排序 交换排序（重点是快速排序） 选择排序 归并排序 基数排序,d关键

5、字的位数(长度),按排序算法的时间复杂度不同，可分为3类： 简单的排序算法：时间效率低，O(n2) 先进的排序算法: 时间效率高，O( nlog2n ) 基数排序算算法：时间效率高，O( dn),按稳定性分类： 在待排记录序列中，任何两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。 例 设 49,38,65,97,76,13,27,49 是待排序列 排序后:13,27,38,49,49,65,76,97 稳定 排序后:13,27,38,49,49,65,76,97不稳定 稳性排序的应用： 例 股票交易系统 考虑一种股票交易(清华紫光)） 1）

6、顾客输入：股东帐号、股票代码、申购价格、数量，股票交易系统将用户申购请求插入申购队列队尾； 2）股票交易系统按如下原则交易： A）申购价高者先成交 B）申购价相同者按申购时间先后顺序成交,如何实现股票交易系统 ？申购队列：用线性表表示 交易前：将申购队列按申购价排序，显然为满足原则交易B），要求排序方法是稳定的 申购队列（09,10),(06,10.5),(033,9.8),(051,10) 排序后：(06,10.5),(09,10),(051,10),(033,9.8),待排序记录在内存中怎样存储和处理？, 顺序排序排序时直接移动记录； 链表排序排序时只移动指针； 地址排序排序时先移动地址，

7、最后再移动记录。,注：地址排序中可以增设一维数组来专门存放记录的地址。,内部排序的方法,内部排序的过程是一个逐步扩大 记录的有序序列长度的过程。,经过一趟排序,有序序列区,无 序 序 列 区,有序序列区,无 序 序 列 区,选择排序,从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。,【算法3.1 】一趟选择排序的算法如下： void SelectPass( SqList k+ ) if ( L.rk.key L.rj.key ) j = k ； / 暂不进行记录交换，只记录位置 if ( i != j ) W=L.rj；L.rj

8、 =L.ri；L.ri = W； / 最后互换记录Rj 和Ri / SelectPass,【算法3.2 】 void SelectSort (SqList k+ ) / 在L.ri.L.length中选择key最小的记录 if ( L.rk.key L.rj.key ) j =k ； if ( i!=j ) W=L.rj；L.rj =L.ri；L.ri = W； / 与第i个记录交换 / SelectSort,整个选择排序的过程是一趟选择排序过程的多次重复，融合SelectPass。,初试关键字： 491 38 65 492 76 13 27 52 i=1 （13） 38 65 492 76

9、491 27 52 i=2 （13 27）65 492 76 491 38 52 i=3 （13 27 38） 492 76 491 65 52 i=4 （13 27 38 492）76 491 65 52 i=5 （13 27 38 492 491）76 65 52 i=6 （13 27 38 492 491 52）65 76 i=7 （13 27 38 492 491 52 65 ）76,【例3-1 】对下面一组关键字： 491 38 65 492 76 13 27 52 进行选择排序，每趟排序之后的状况如下：,选择排序时间性能分析,对 n 个记录进行简单选择排序，所需进行的 关键字间的比

10、较次数 总计为:,移动记录的次数，最小值为 0, 最大值为3(n-1),简单排序算法，除前面讨论的选择排序外，常用的还有插入排序和起泡排序。,3.2 简单排序方法,插入排序的基本思想： 每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。,简而言之，边插入边排序，保证子序列中随时都是排好序的。,利用 “顺序查找”实现“在R1.i-1中查找Ri的插入位置”,直接插入排序,算法实现： 当插入第i (i 1) 个对象时, 前面的r0, r1, , ri-1已经排好序。这时, 用ri的排序码与ri-1, ri-2, 的排序码顺序进行比较, 找到插入

11、位置即将ri插入, 原来位置上的对象向后顺移。,有序序列R1.i-1,Ri,无序序列 Ri.n,有序序列R1.i,无序序列 Ri+1.n,一趟直接插入排序的基本思想：,【算法3.3 】 void InsertPass( SqList / 插入到正确位置 / InsertPass,注意：“哨兵”的作用,一趟插入排序,从Ri-1起向前进行顺序查找，监视哨设置在R0；,R0 = Ri; / 设置“哨兵”,循环结束表明Ri的插入位置为 j +1,R0,j,Ri,for (j=i-1; R0.keyRj.key; -j); / 从后往前找,插入位置,对于在查找过程中找到的那些关键字不小于Ri.key的记

12、录，并在查找的同时实现记录向后移动；,for (j=i-1; R0.keyRj.key; -j); Rj+1 = Rj,R0,j,Ri,j= i-1,上述循环结束后可以直接进行“插入”,插入位置,例2：关键字序列T= （21，25，49，25*，16，08），请写出直接插入排序的具体实现过程。,*表示后一个25,i=1,21,i=2,i=3,i=5,i=4,i=6,25,25,25,49,49,49,25*,49,16,16,08,49,解：假设该序列已存入一维数组V7中，将V0作为缓冲或暂存单元（Temp）。则程序执行过程为：,初态：,16,25,21,16,完成!,时间效率：O(n2)因为

13、在最坏情况下，所有元素的比较次数总和为（01n-1)O(n2)。其他情况下还要加上移动元素的次数。 空间效率：O(1)因为仅占用1个缓冲单元 算法的稳定性：稳定因为25*排序后仍然在25的后面。,【算法3.4 】 void InsertSort ( SqList / 插入到正确位置 / if / InsertSort,整个插入排序需要进行n-1趟“插入”。 因为只含有一个关键字的序列必定是有序序列，因此，插入应该从i=1开始进行，此外，若第i个记录的关键字不小于第i-1个关键字，插入也就不需要进行了。,初始时，有序子表中只有一个元素,待排序记录集合：,i=2 i=3 i=4,L.r0.key

14、L.r4.key， L.r4记录后移,看一下外层For循环 i=5 时算法的执行的情况,L.r5复制为哨兵,L.r0.key L.r3.key 找到插入位置,L.r5为待插入元素,插入！,时间复杂度： 待排序列正向有序时 ：0 （n） 待排序列逆向有序时： 0（n2） 一般待排序列：0（n2） 插入排序特点： 1) 算法简单 2) 时间复杂度为O（n2 ） 3）初始序列基本（正向）有序时，时间复杂度为O（n） 4）稳定排序 该方法适用于记录基本（正向）有序或n较少的情况,性能分析：基本操作: 比较元素：比较、移动元素次数均取决于插入位置 移动元素处理第i个记录时 待排序列递增（正向）有序时，比

15、较元素次数最少：1次 待排序列递减（逆向）有序时，比较元素次数最多：i 次 一般待排序列，平均比较元素次数： (i+1)/2 对n个记录待排序列,直接插入排序 待排序列正向有序时，比较元素次数最少：n-1次 待排序列逆向有序时，比较元素次数最多：(n+2)(n-1)/2次 一般待排序列，平均比较元素次数大约为：n2/4 类似可分析移动元素次数,3.2.2 起泡排序,基本思想： 是通过对无序序列区中的记录进行相邻记录关键字的“比较”和记录位置的“交换”实现较小的记录向“一头”漂移，而关键字较大的记录向“另一头”下沉，从而达到记录按关键字非递减有序排列的目标。,假设在排序过程中，记录序列R1.n的

16、状态为：,第 i 趟起泡排序,无序序列R1.n-i+1,有序序列 Rn-i+2.n,n-i+1,无序序列R1.n-i,有序序列 Rn-i+1.n,比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上,1) 冒泡排序,基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。 优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。 前提：顺序存储结构,例：关键字序列 T=(21，25，49，25*，16，08），请写出冒泡排序的具体实现过程。,21，25，49， 25*，16， 08 21，25，25*

17、，16， 08 ， 49 21，25， 16， 08 ，25*，49 21，16， 08 ，25， 25*，49 16，08 ，21， 25， 25*，49 08，16， 21， 25， 25*，49,初态： 第1趟 第2趟 第3趟 第4趟 第5趟,【具体算法 3.5 】 void BubbleSort( SqList / 一趟排序中无序序列中最后一个记录的位置 / while / BubbleSort 空间复杂度O(1),注意:,2. 一般情况下，每经过一趟“起泡”，“i 减一”，但并不是每趟都如此。,例如:,i=7,for (j = 1; j i; j+) if (Rj+1.key Rj.

18、key) ,1. 起泡排序的结束条件为， 最后一趟没有进行“交换记录”。,2,3,1,5,7,8,9,i=6,i=2,3,1,1,3,时间分析:,最好的情况（关键字在记录序列中顺序有序）： 只需进行一趟起泡,“比较”的次数：,最坏的情况（关键字在记录序列中逆序有序）： 需进行n-1趟起泡,“比较”的次数：,0,“移动”的次数：,“移动”的次数：,n-1,3.3 先进的排序方法 3.3.1 快速排序(quick sort) 快速排序是从起泡排序改进而得的一种“交换”排序方法，它的基本思想是通过一趟排序将将记录分割成相邻的两个区域，其中一个区域中记录的关键字均比另一区域中记录关键字小（区域内不一定

19、有序），则可分别对这两个区域的记录进行再排序，以达到整个序列有序。,目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列Rs.t将分割成两部分：Rs.i-1和Ri+1.t, 且 Rj.key Ri.key Rj.key (sji-1) 枢轴 (i+1jt),基本步骤： 为简洁起见，对待排记录仍只写出其关键字序列 1、(一趟快速排序）设被指定的关键字为待排序列的第一个关键字k ，i指向 待排序列的的第一个关键字； j指向最后一个关键字； 若i j 循环： 1）从后向前将关键字与k比

20、较，直至遇到小于k的关键字 k，k 前移； 2）从前向后将关键字与k比较，直至遇到大于k的关键字k，k后移； （一趟快速排序后，“小”记录被移至k 前，“大”的记录被移至k 后 2、继续对k前后两部分关键字进行快速排序，直至排序范围为1;,被指定的关键字,从后向前，将关键字与49比较，直至遇到小于49的关键字，前移,从后向前，将关键字与49比较，直至遇到小于49的关键字，前移,从前向后，将关键字与49比较，直至遇到大于49的关键字，后移,从前向后，将关键字与49比较，直至遇到大于49的关键字，后移,从后向前，将关键字与49比较，直至遇到i=j,将49放至i处,49,一趟快速排序结束,27 38

21、 13 49 76 97 65 49 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97 13 27 38 49 49 65 76 97,两趟快速排序结束,三趟快速排序结束,快速排序结束,【算法3.7 】 void QSort (RedType R, int s, int t ) / 对记录序列Rs.t进行快速排序 if (s t) / 长度大于1 pivotloc = Partition(R, s, t);/ 对 Rs.t 进行一次划分，并返回枢轴位置 QSort(R, s, pivotloc-1); / 对低子序列递归排序 QSort(R, pi

22、votloc+1, t); / 对高子序列递归排序 / if / Qsort,int Partition (RedType R, int s, int t ) key = Rs; while ( s = key ) t-; Rs Rt; while (s t ,【算法3.8 】 void QuickSort( SqList / QuickSort,快速排序的时间分析：,假设一次划分所得枢轴位置 i=k，则对n 个记录进行快排所需时间,其中 Tpass(n)为对 n 个记录进行一次划分所需时间，,若待排序列中记录的关键字是随机分布的，则 k 取 1 至 n 中任意一值的可能性相同。,T(n) =

23、 Tpass(n) + T(k-1) + T(n-k),设 Tavg(1)b,则可得结果:,结论: 快速排序的时间复杂度为O(nlogn)，快速排序是 目前被认为同数量级中最快的内部排序算法。,由此可得快速排序所需时间的平均值为：,若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序，其时间复杂度为O(n2)。,为避免出现这种情况，需在进行一次划分之前，进行“予处理”，即： 先对 R(s).key, R(t).key 和 R(s+t)/2.key，进行相互比较，然后取关键字为 “三者之中”的记录为枢轴记录。,归并排序的基本思想是：将两个（或以上）的有序表组成新的有序表。 更实际的意义

24、：可以把一个长度为n 的无序序列看成是 n 个长度为 1 的有序子序列 ，首先做两两归并，得到 n / 2 个长度为 2 的子序列 ；再做两两归并，如此重复，直到最后得到一个长度为 n 的有序序列。,例：关键字序列T= （21，25，49，25*，93，62，72，08，37，16，54），请给出归并排序的具体实现过程。,3.3.2 归并排序,len=1,len=2,len=4,len=8,len=16,整个归并排序仅需log2n 趟,Void Merge (RcdType SR ，RcdType TR ，int i, int m, int n) / 将有序的SRim和SRm+1n归并为有序的

25、TRin for(k=i , j=m+1; i=m / 将剩余的SRjn复制到TR / Merge,一趟归并排序算法: (两路有序并为一路) 参见教材P53,【算法3.11 】 void MergeSort (SqList / MergeSort,【算法3.10 】 void Msort ( RcdType SR, RcdType TR1, int s, int t ) / 对SRs.t进行归并排序，排序后的记录存入TR1s.t。 RcdType TR2t-s+1; /开设用于存放归并排序中间结果的辅助空间 if (s=t) TR1s = SRs; else m = (s+t)/2; / 将S

26、Rs.t平分为SRs.m和SRm+1.t Msort (SR, TR2, s, m); / 递归地将SRs.m归并为有序的TR2s.m Msort (SR, TR2, m+1, t); / 递归地将SRm+1.t归并为有序的TR2m+1.t Merge (TR2, TR1, s, m, t); / 将TR2s.m和TR2m+1.t归并到TR1s.t / else / MSort,归并排序算法分析：,时间效率： O(nlog2n) 因为在递归的归并排序算法中，函数Merge( )做一趟两路归并排序，需要调用merge ( )函数 n/(2*len) O(n/len) 次，函数Merge( )调用

27、Merge( )正好log2n 次，而每次merge( )要执行比较O(len)次，所以算法总的时间复杂度为O(nlog2n)。 空间效率： O(n) 因为需要一个与原始序列同样大小的辅助序列（TR）。这正是此算法的缺点。 稳定性：稳定,3.3.3 堆排序（Heap Sort)）,堆的定义:,堆是满足下列性质的数列r1, r2, ，rn：,(小顶堆),(大顶堆),堆排序是利用堆的特性对记录序列进行排序的一种排序方法，是对选择排序的一种改进。,12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49,例如:,12, 36, 27, 65, 40, 14, 98, 81

28、, 73, 55, 49,解释：如果让满足以上条件的元素序列 （k1，k2，kn）顺次排成一棵完全二叉树，则此树的特点是： 树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。,（大顶堆）,（小顶堆）,（小根堆） （最小堆）,（大根堆） （最大堆）,例：有序列T1=（08, 25, 49, 46, 58, 67）和序列T2=（91, 85, 76, 66, 58, 67, 55）,判断它们是否 “堆”？,初始数据H.r1.6,互换H.r1和H.r6,初建大顶堆,重新将H.r1.5调整为大顶堆,互换H.r1和H.r5,重新将H.r1.4调整为大顶堆,互换H.r1和

29、H.r4,重新将H.r1.3调整为大顶堆,互换H.r1和H.r3,重新将H.r1.2调整为大顶堆,互换H.r1和H.r2,至此，堆排序结束，H.r1.6为有序序列。,3.4 基数排序 基数排序（Radix Sort） ： 是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法（即：用关键字不同的位值进行排序。 ）。 要讨论的问题： 1. 什么是“多关键字”排序？实现方法？ 2. 单逻辑关键字怎样“按位值”排序？,多关键字排序的实现方法通常有两种： 1）最高位优先法MSD (Most Significant Digit first) 2）最低位优先法LSD (Least Signi

30、ficant Digit first),以扑克牌排序为例。每张扑克牌有两个“排序码”：花色和面值。其有序关系为： 花色： 面值：2 3 4 5 6 7 8 9 10 J Q K A 如果我们把所有扑克牌排成以下次序： 2, , A, 2, , A, 2, , A, 2, , A 这就是多关键字排序。,例：对一副扑克牌该如何排序？ 答：若规定花色为第一关键字（高位），面值为第二关键字（低位），则使用MSD和LSD方法都可以达到排序目的。 MSD方法的思路：先设立4个花色“箱”，将全部牌按花色分别归入4个箱内（每个箱中有13张牌）；然后对每个箱中的牌按面值进行插入排序（或其它稳定算法）。 LSD方

31、法的思路：先按面值分成13堆（每堆4张牌），然后对每堆中的牌按花色进行排序（用插入排序等稳定的算法）。,想一想：用哪种方法更快些？,2. 单逻辑关键字怎样“按位值”排序？ 思路：设n 个记录的序列为：V0, V1, , Vn-1 ，可以把每个记录Vi 的单关键码 Ki 看成是一个d元组（Ki1, Ki2, , Kid），则其中的每一个分量Kij ( 1 j d ) 也可看成是一个关键字。,注1： Ki1最高位关键字，Kid最低位关键字；Ki共有d位，可看成d元组； 注2： 每个分量Kij (1 j d ) 有radix种取值，则称radix为基数。,(9, 8, 4),(0, 1, , 9),

32、（a, b, , z）,(d, i, a, n),例1：关键码984可以看成是 3 元组；基数radix 为 10 。,例2：关键码dian可以看成是 4 元组；基数radix 为 26 。,初始状态,第一趟“分配”之后的结果,第一趟“收集”之后的结果,采用“分配”与“收集”的方法实现基数排序。,第二趟“分配”之后的结果,第二趟“收集”之后的结果,对由顺序表表示法存储的记录进行基数排序可利用“计数”和“复制”的操作实现。,记录数组A,记数数组count (个位情况),累加结果count,（a）初始状态和对“个位数”计数的结果,累加结果count,记录数组B,记数数组count (十位情况),（

33、b）计数器的累加结果和记录“复制”后的状态,记数数组count (十位情况),累加结果count,记录数组A,（c）对“十位数”计数和“复制”和记录“复制”后的状态,【算法3.12 】 void RadixSort( SqList / 排序后的结果在C中，复制至L.r中 / while / RadixSort,【算法3.13 】 void RadixPass( RcdType A, RcdType B, int n, int i ) / 对数组A中记录关键字的第i位计数，并按计数数组count的值 / 将数组A中记录复制到数组 B中 for ( j=0; j=0; -k ) / 从右端开始复制

34、记录 j = Ak.keysi; B countj-1 = Ak; countj-; / for / RadixPass,时间复杂度：O(dn)(d趟基数排序，每趟对n个记录进行“计数”和“复制”) 空间复杂度：O(n),因为有分组，故此算法需递归实现。,思考：是借用MSD方式来排序呢，还是借用LSD方式？,方法1（MSD）：原始序列：32, 13, 27, 32*, 19， 33 先按高位Ki1 排序：（13, 19）, 27, （32, 32*，33） 再按低位Ki2 排序 ： 13, 19 ， 27, 32, 32*, 33,方法2（LSD）： 原始序列： 32, 13, 27, 32*

35、, 19 ，33 先按低位Ki2排序： 32, 32*, 13, 33, 27, 19 再按高位Ki1排序： 13, 19 , 27, 32, 32*, 33,无需分组，易编程实现！,例：初始关键字序列T=（32, 13, 27, 32*, 19，33），请分别用MSD和LSD进行排序，并讨论其优缺点。,3.5 各种排序方法的比较,一、时间性能,1. 平均的时间性能,时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序 时间复杂度为 O(n2)：直接插入排序、起泡排序和简单选择排序 时间复杂度为 O(n): 基数排序,2. 当待排记录序列按关键字顺序有序时 直接插入排序和起泡排序能达到O

36、(n)的时间复杂度; 快速排序的时间性能蜕化为O(n2),3. 简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。,二、空间性能,空间性能指的是排序过程中所需的辅助空间大小,1. 所有的简单排序方法(包括：直接插入、起泡和简单选择) 和堆 排序的空间复杂度为O(1)；,2. 快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间;,3. 归并排序和基数排序所需辅助空间最多，其空间复杂度为 O(n);,三、排序方法的稳定性能,1. 稳定的排序方法指的是，对于两个关键字相等的记录，它们在 序列中的相对位置，在排序之前和经过排序之后，没有改变。,2. 除快速排序、堆排序和希尔排序是不稳定的排序方法之外，本 章讨论的其它排序方法都是稳定的排序方法。,3. 对于不稳定的排序方法，只要能举出一个实例说明即可。 例如 : 对 4, 3, 4, 2 进行快速排序，得到 2, 3, 4, 4 ,四、关于“排序方法的时间复杂度的下限”,本章讨论的各种排序方法，除基数排序外，其它方法都是基于“比较关键字”进行排序的排序方法。可以证明， 这类排序法可能达到的最快的时间复杂度为O(nlogn)。 (基数排序不是基于“比较关键字”的排序方法，所以它不受这个限制),