零基础学数据结构内排序.pptx

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

1、12.1 基本概念 排序：把一个无序的元素序列按照元素的关键字递增或递减排列为有序的序列。假设包含n个元素（记录）的序列 (E1,E2,En)其对应的关键字为 (k1,k2,kn)需确定1,2,n的一种排列p1,p2,pn，使关键字满足以下非递减（或非递增）关系：kp1kp2kpn 从而使元素构成一个非递减（或非递增）的序列：(Ep1,Ep2,Epn)这样的一种操作被称为排序。第1页/共63页12.1 基本概念 稳定排序和不稳定排序：在待排序的记录序列中，若存在两个或两个以上关键字想到呢个的记录。假设ki=kj(1in,1jn,ij)，且排序前的对应的记录Ei领先于Ej（即ij）。若在排序之后

2、，如果元素Ei仍领先于Ej，则称这种排序采用的方法是稳定的。如果经过排序之后，元素Ej领先于Ei（即i6，所以需要先将22向后移动一个位置，然后将6插入到第一个位置，如图12.2所示。其中，阴影部分表示无序集，白色部分表示有序集。第2趟排序：将无序集的元素17从右到左依次与有序集中的元素比较，即先与22比较，因为176，所以将17放在第2个元素的位置，如图12.3所示。第7页/共63页12.2 插入排序第3趟排序：将待排序集合中的元素8与已经有序的元素集合从右到左依次比较，先与22比较。因为822，所以需要将22向后移动一个位置并与前一个元素17比较。由于86，所以将8放在第2个位置，如图12

3、.4所示。第8页/共63页12.2 插入排序 假设待排序元素有8个，分别是17、46、32、87、58、9、50、38。使用直接插入排序对该元素序列的排序过程如图12.5所示。第9页/共63页12.2 插入排序直接插入排序算法描述如下。void InsertSort(SqList*L)/*直接插入排序*/int i,j;DataType t;for(i=1;ilength;i+)/*前i个元素已经有序，从第i+1个元素开始与前i个有序的关键字比较*/t=L-datai+1;/*取出第i+1个元素，即待排序的元素*/j=i;while(j0&t.keydata j.key)/*寻找当前元素的合适

4、位置*/L-data j+1=L-data j;j-;L-data j+1=t;/*将当前元素插入合适的位置*/第10页/共63页12.2 插入排序折半插入排序 折半插入排序算法是直接插入排序的改进。它的主要改进在于，在已经有序的集合中使用折半查找法确定待排序元素的插入位置。在找到要插入的位置后，将待排序元素插入到相应的位置。假设待排序元素有7个：67、53、73、21、34、98、12。使用折半插入排序对该元素序列第一趟排序过程如图12.6所示。第11页/共63页12.2 插入排序第2趟折半插入排序过程如图12.7所示。第12页/共63页12.2 插入排序 void BinInsertSor

5、t(SqList*L)/*折半插入排序*/int i,j,mid,low,high;DataType t;for(i=1;ilength;i+)t=L-datai+1;/*取出第i+1个元素，即待排序的元素*/low=1,high=i;while(lowdatamid.keyt.key)high=mid-1;elselow=mid+1;for(j=i;j=low;j-)/*移动元素，空出要插入的位置*/L-data j+1=L-data j;L-datalow=t;/*将当前元素插入合适的位置*第13页/共63页12.2 插入排序希尔排序 希尔排序（shells sort）也称为缩小增量排序（

6、diminishing increment sort），它也属于插入排序类的算法，但时间效率比前几种排序有较大改进。设待排序元素为：48、26、66、57、32、85、55、19，使用希尔排序算法对该元素序列的排序过程如图12.8所示。第14页/共63页12.2 插入排序相应地，希尔排序的算法可描述如下。void ShellInsert(SqList*L,int c)/*对顺序表L进行一次希尔排序，c是增量*/int i,j;DataType t;for(i=c+1;ilength;i+)/*将距离为c的元素作为一个子序列进行排序*/if(L-datai.keydatai-c.key)/*如果

7、后者小于前者，则需要移动元素*/t=L-datai;for(j=i-c;j0&t.keydata j.key;j=j-c)L-data j+c=L-data j;L-data j+c=t;/*依次将元素插入到正确的位置*/第15页/共63页12.2 插入排序void ShellInsertSort(SqList*L,int delta,int m)/*希尔排序，每次调用算法ShellInsert,delta是存放增量的数组*/int i;for(i=0;inext=NULL。指针p指向待排序的链表，若有序序列为空，将p指向的第一个结点插入到空链表L中。然后将有序链表即L指向的链表的每一个结点与

8、p指向的结点比较，并将结点*p插入到L指向的链表的恰当位置。重复执行上述操作，直到待排序链表为空。此时，L就是一个有序链表。第18页/共63页12.3 交换排序 冒泡排序 冒泡排序(bubble sort)是一种简单的交换类排序算法，它是通过交换相邻的两个数据元素，逐步将待排序序列变成有序序列。它的基本算法思想描述如下：假设待排序元素有n个，从第1个元素开始，依次交换相邻的两个逆序元素，直到最后一个元素为止。当第1趟排序结束，就会将最大的元素移动到序列的末尾。然后按照以上方法进行第2趟排序，次大的元素将会被移动到序列的倒数第2个位置。依次类推，经过n-1趟排序后，整个元素序列就成了一个有序的序

9、列。每趟排序过程中，值小的元素向前移动，值大的元素向后移动，就像气泡一样向上升，因此将这种排序方法称为冒泡排序。第19页/共63页12.3 交换排序例如，有5个待排序元素55、26、48、63和37。第1趟排序：第20页/共63页12.3 交换排序 第2趟排序：从第1个元素开始，依次比较第1个元素与第2个元素、第2个元素与第3个元素、第3个元素与第4个元素，如果前者大于后者，则交换之；否则不进行交换。第2趟排序过程如图12.12所示。第21页/共63页12.3 交换排序 第3趟排序：按照以上方法，依次比较两个相邻元素，交换逆序的元素。第3趟排序过程如图12.13所示。第4趟排序：此时，待排序元

10、素只剩下26和37，只需要进行一次比较即可。因为2637，所以不需要交换。第4趟排序过程如图12.14所示。第22页/共63页12.3 交换排序 设待排序元素为56、72、44、31、99、21、69、80，使用冒泡排序对该元素序列的排序过程如图12.15所示。第23页/共63页12.3 交换排序冒泡排序的算法描述如下。void BubbleSort(SqList*L,int n)/*冒泡排序*/int i,j,flag;DataType t;for(i=1;i=n-1&flag;i+)/*需要进行n-1趟排序*/flag=0;for(j=1;jdata j.keyL-data j+1.key

11、)t=L-data j;L-data j=L-data j+1;L-data j+1=t;flag=1;第24页/共63页12.3 交换排序 快速排序的算法思想是：从待排序记录序列中选取一个记录（通常是第一个记录）作为枢轴，其关键字设为key，然后将其余关键字小于key的记录移至前面，而将关键字大于key的记录移至后面，结果将待排序记录序列分为两个子表，最后将关键字key的记录插入到其分界线的位置。我们将这个过程称为一趟快速排序。通过这一趟划分后，就以关键字为key的记录为界，将待排序序列分为两个子表，前面的子表所有记录的关键字均不大于key，而后面子表的所有记录的关键字均不小于key。继续对

12、分割后的子表进行上述划分，直至所有子表的表长不超过1为止，此时的待排序记录就成了一个有序序列。第25页/共63页12.3 交换排序 【算法步骤】设待排序序列存放在数组a1n中，n为元素个数，设置两个指针i和j，初值分别为1和n，令a1作为枢轴元素赋给pivot，a1相当于空单元，然后执行以下操作：（1）j从右往左扫描，若a j.keypivot.key，将ai移至a j中，并执行一次j-操作；（3）重复执行（1）和（2），直到出现ij，则将元素pivot移动到ai中。此时整个元素序列在位置i被划分成两个部分，前一部分的元素关键字都小于ai.key，后一部分元素的关键字都大于等于ai.key。即

13、完成了一趟快速排序。第26页/共63页12.3 交换排序 例如，一组待排序元素序列为55,22,44,67,35,77,18,69，依据快速排序的算法思想，得到第1趟排序的过程如图12.16所示。第27页/共63页12.3 交换排序 设待排序元素为55、22、44、67、35、77、18、69，用快速排序算法对该元素序列的排序过程如图12.17所示。第28页/共63页12.3 交换排序进行一趟快速排序，即将元素序列进行一次划分的算法描述如下所示。int Partition(SqList*L,int low,int high)/*对顺序表L.rlow.high的元素进行一趟排序，使枢轴前面的元素

14、关键字小于枢轴元素的关键字，枢轴后面的元素关键字大于等于枢轴元素的关键字，并返回枢轴位置*/DataType t;KeyType pivotkey;pivotkey=(*L).datalow.key;/*将表的第一个元素作为枢轴元素*/t=(*L).datalow;while(lowhigh)/*从表的两端交替地向中间扫描*/while(low=pivotkey)/*从表的末端向前扫描*/high-;if(lowhigh)/*将当前high指向的元素保存在low位置*/(*L).datalow=(*L).datahigh;low+;第29页/共63页while(lowhigh&(*L).dat

15、alow.key=pivotkey)/*从表的始端向后扫描*/low+;if(lowhigh)/*将当前low指向的元素保存在high位置*/(*L).datahigh=(*L).datalow;high-;(*L).datalow=t;/*将枢轴元素保存在low=high的位置*/return low;/*返回枢轴所在位置*/12.3 交换排序第30页/共63页12.3 交换排序 通过多次递归调用一次划分算法即一趟排序算法，可实现快速排序，其算法描述如下所示。void QuickSort(SqList*L,int low,int high)/*对顺序表L进行快速排序*/int pivot;i

16、f(lowhigh)/*如果元素序列的长度大于1*/pivot=Partition(L,low,high);/*将待排序序列L.rlow.high划分为两部分*/QuickSort(L,low,pivot-1);/*对左边的子表进行递归排序，pivot是枢轴位置*/QuickSort(L,pivot+1,high);/*对右边的子表进行递归排序*/第31页/共63页12.3 交换排序 快速排序在最好的情况下是每趟排序将序列一分两半，从表中间开始，将表分成两个大小相同的子表，类似折半查找，这样快速排序的划分的过程就将元素序列构成一个完全二叉树的结构，分解的次数等于树的深度即log2n，因此快速排

17、序总的比较次数为 T(n)n+2T(n/2)n+2*(n/2+2*T(n/4)=2n+4T(n/4)3n+8T(n/8)nlog2n+nT(1)。因此，在最好的情况下，时间复杂度为O(nlog2n)。第32页/共63页交换排序应用举例【例12_3】编写算法，使用冒泡排序和快速排序算法对给定的一组关键字序列(37,22,43,32,19,12,89,26,48,92)进行排序，并输出每趟排序结果。【分析】主要考察两种交换排序即冒泡排序和快速排序的算法思想。这两种算法都是对存在逆序的元素进行交换，从而实现排序。主要区别在于：冒泡排序通过比较相邻的两个元素，并对两个相邻的逆序元素进行交换；而快速排序

18、则是选定一个枢轴元素作为参考元素，设置两个指针，分别从表头和表尾开始，将当前扫描的元素与枢轴元素进行比较，存在逆序的元素不一定是相邻的元素，如果存在逆序，则交换之。12.3 交换排序第33页/共63页简单选择排序 简单选择排序是一种简单的选择类排序算法，它是通过依次找到待排序元素序列中最小的数据元素，并将其放在序列的最前面，从而使待排序元素序列变为有序序列。它的基本算法思想描述如下：假设待排序的元素序列有n个，在第一趟排序过程中，从n个元素序列中选择最小的元素，并将其放在元素序列的最前面即第一个位置。在第二趟排序过程中，从剩余的n-1个元素中，选择最小的元素，将其放在第二个位置。依次类推，直到

19、没有待比较的元素，简单选择排序算法结束。12.4 选择排序 第34页/共63页简单选择排序的算法描述如下。void SelectSort(SqList*L,int n)/*简单选择排序*/int i,j,k;DataType t;/*将第i个元素的关键字与后面i+1.n个元素的关键字比较，将关键字最小的的元素放在第i个位置*/for(i=1;i=n-1;i+)j=i;for(k=i+1;kdatak.keydata j.key)j=k;if(j!=i)/*如果序号i不等于j，则需要将序号i和序号j的元素交换*/t=L-datai;L-datai=L-data j;L-data j=t;12.4

20、 选择排序第35页/共63页12.4 选择排序一组元素的关键字序列为(76,31,19,20,6,83,60,52)，简单选择排序的过程如图12.19所示。第36页/共63页堆排序 1什么是堆和堆排序 堆排序(heap sort)主要是利用了二叉树的树形结构，按照完全二叉树的编号次序，将元素序列的关键字依次存放在相应的结点。然后从叶子结点开始，从互为兄弟的两个结点中（没有兄弟结点除外），选择一个较大（或较小）者与其双亲结点比较，如果该结点大于（或小于）双亲结点，则将两者进行交换，使较大（或较小）者成为双亲结点。将所有的结点都做类似操作，直到根结点为止。这时，根结点的元素值的关键字最大（或最小）

21、。12.4 选择排序第37页/共63页 这样就构成了堆，堆中的每一个结点都大于（或小于）其孩子结点。堆 的 数 学 形 式 定 义 为：假 设 存 在 n个 元 素，其 关 键 字 序 列 为(k1,k2,ki,kn)，如果有：则称此元素序列构成了一个堆。如果将这些元素的关键字存放在一维数组中，将此一维数组中的元素与完全二叉树一一对应起来，则完全二叉树中的每个非叶子结点的值都不小于（或不大于）孩子结点的值。12.4 选择排序第38页/共63页 在堆中，堆的根结点元素值一定是所有结点元素值的最大值或最 小 值。例 如，序 列（89,77,65,62,32,55,60,48）和（18,37,29,

22、48,50,43,33,69,77,60）都是堆，相应的完全二叉树表示如图12.20所示。12.4 选择排序第39页/共63页 如果将堆中的根结点（堆顶）输出之后，然后将剩余的n-1个结点的元素值重新建立一个堆，则新堆的堆顶元素值是次大（或次小）值，将该堆顶元素输出。然后将剩余的n-2个结点的元素值重新建立一个堆，反复执行以上操作，直到堆中没有结点，就构成了一个有序序列，这样的重复建堆并输出堆顶元素的过程称为堆排序。12.4 选择排序第40页/共63页 2建堆 堆排序的过程就是建立堆和不断调整使剩余结点构成新堆的过程。假设将待排序的元素的关键字存放在数组a中，第1个元素的关键字a1表示二叉树的

23、根结点，剩下的元素的关键字a a2n分别与二叉树中的结点按照层次从左到右一一对应。例如，a1的左孩子结点存放在a2中，右孩子结点存放在a3中，ai的左孩子结点存放在a2*i中，右孩子结点存放在a2*i+1中。12.4 选择排序第41页/共63页 例如，给定一组元素序列(27,58,42,53,42,69,50,62)，建立大顶堆的过程如图12.21所示。12.4 选择排序第42页/共63页相应地，建立大顶堆的算法描述如下所示。void CreateHeap(SqList*H,int n)/*建立大顶堆*/int i;for(i=n/2;i=1;i-)/*从序号n/2开始建立大顶堆*/Adjus

24、tHeap(H,i,n);12.4 选择排序第43页/共63页void AdjustHeap(SqList*H,int s,int m)/*调整H.datas.m的关键字，使其成为一个大顶堆*/DataType t;int j;t=(*H).datas;/*将根结点暂时保存在t中*/for(j=2*s;j=m;j*=2)if(jm&(*H).data j.key(*H).data j.key)/*如果孩子结点的值小于根结点的值，则不进行交换*/break;(*H).datas=(*H).data j;s=j;(*H).datas=t;/*将根结点插入到正确位置*/12.4 选择排序第44页/共

25、63页 3调整堆 具体实现：当堆顶元素输出后，可以将堆顶元素放在堆的最后，即将第1个 元 素 与 最 后 一 个 元 素 交 换 a1an，则 需 要 调 整 的 元 素 序 列 就 是a1n-1。从根结点开始，如果其左、右子树结点元素值大于根结点元素值，选择较大的一个进行交换。即如果a2a3，则将a1与a2比较，如果a1a2，则将a1与a2交换，否则不交换。如果a2a3，则将a1与a3交换，否则不交换。重复执行此操作，直到叶子结点不存在，就完成了堆的调整，构成了一个新堆。12.4 选择排序第45页/共63页12.4 选择排序 例如，一个大顶堆的关键字序列为(69,62,50,58,42,42

26、,27,53)，当输出69后，调整剩余的元素序列为大顶堆的过程如图12.22所示。第46页/共63页12.4 选择排序调整堆的算法实现如下。void HeapSort(SqList*H)/*对顺序表H进行堆排序*/DataType t;int i;CreateHeap(H,H-length);/*创建堆*/for(i=(*H).length;i1;i-)/*将堆顶元素与最后一个元素交换，重新调整堆*/t=(*H).data1;(*H).data1=(*H).datai;(*H).datai=t;AdjustHeap(H,1,i-1);/*将(*H).data1.i-1调整为大顶堆*/第47页/

27、共63页12.4 选择排序 例如，一个大顶堆的元素的关键字序列为(69,62,50,58,42,42,27,53)，其相应的完整的堆排序过程如图12.23所示。第48页/共63页12.4 选择排序选择排序应用举例【例12_4】编写算法，利用简单选择排序和堆排序算法对一组关键字序列(69,62,50,58,42,42,27,53)进行排序，要求输出每趟排序的结果。【分析】简单选择排序和堆排序都是一种不稳定的排序方法。它们的主要思想：每次从待排序元素中选择关键字最小（或最大）的元素，经过不断交换，重复执行以上操作，最后形成一个有序的序列。第49页/共63页12.4 选择排序【例12_5】编写算法，

28、对关键字序列(76,20,99,32,60,53,11,8,42)进行选择排序，要求使用链表实现。【分析】主要考察选择排序的算法思想和链表的操作。具体实现时，设置两个指针p和q，分别指向已排序链表和未排序链表。初始时，先创建一个链表，q指向该链表，p指向的链表为空。然后从q指向的链表中找到一个元素值最小的结点，将其取出并插入到p指向的链表中。重复执行以上操作直到q指向的链表为空，此时p指向的链表就是一个有序链表。第50页/共63页12.5 归并排序 路归并排序算法 主要思想是：假设元素的个数是n，将每个元素作为一个有序的子序列，然后将相邻的两个子序列两两归并，得到个长度为2的有序子序列。然后将

29、相邻的两个有序子序列两两归并，得到个长度为4的有序子序列。如此重复，直至得到一个长度为n的有序序列为止。关键字序列(50,22,61,35,87,12,19,75)的2路归并排序的过程如图12.26所示。第51页/共63页12.5 归并排序void Merge(DataType s,DataType t,int low,int mid,int high)/*将有序的slow.mid和smid+1.high归并为有序的tlow.high*/int i,j,k;i=low,j=mid+1,k=low;while(i=mid&j=high)/*将s中元素由小到大地合并到t*/if(si.key=s

30、j.key)tk=si+;elsetk=s j+;k+;while(i=mid)/*将剩余的si.mid复制到t*/tk+=si+;while(j=high)/*将剩余的s j.high复制到t*/tk+=s j+;第52页/共63页12.5 归并排序void MergeSort(DataType s,DataType t,int low,int high)/*2路归并排序，将slow.high归并排序并存储到tlow.high中*/int mid;DataType t2MaxSize;if(low=high)tlow=slow;elsemid=(low+high)/2;/*将slow.hig

31、h分为slow.mid和smid+1.high*/MergeSort(s,t2,low,mid);/*将slow.mid归并为有序的t2low.mid*/MergeSort(s,t2,mid+1,high);/*将smid+1.high归并为有序的t2mid+1.high*/Merge(t2,t,low,mid,high);/*将t2low.mid和t2mid+1.high归并到tlow.high*/第53页/共63页12.5 归并排序归并排序应用举例【例12_6】编写算法，请使用2路归并排序对一组关键字(50,22,61,35,87,12,19,75)进行排序。第54页/共63页12.6 基

32、数排序 基数排序算法 基数排序正是借助这种思想，对不同类的元素进行分类，然后对同一类中的元素进行排序，通过这样的一种过程，完成对元素序列的排序。在基数排序中，通常将对不同元素的分类称为分配，排序的过程称为收集。具体算法思想：假设第i个元素ai的关键字keyi，keyi是由d位十进制组成，即keyi=kidkid-1ki1，其中ki1为最低位，kid为最高位。关键字的每一位数字都可作为一个子关键字。首先将元素序列按照最低的关键字进行排序，然后从低位到高位直到最高位依次进行排序，这样就完成了排序过程。第55页/共63页12.6 基数排序 例如，一组元素的关键字序列为(236,128,34,567,

33、321,793,317,106)。对最低位进行分配和收集的过程如图12.28所示。其中，数组fi保存第i个链表的头指针，数组ri保存第i个链表的尾指针。第56页/共63页12.6 基数排序对十位数字分配和收集的过程如图12.29所示。对百位数字分配和收集的过程如图12.30所示。第57页/共63页12.6 基数排序基数排序的算法主要包括分配和收集。静态链表类型定义描述如下：#define MaxNumKey 6/*关键字项数的最大值*/#define Radix 10/*关键字基数，此时是十进制整数的基数*/#define MaxSize 1000typedef int KeyType;typ

34、edef structKeyType keyMaxNumKey;/*关键字*/int next;SListCell;/*静态链表的结点类型*/typedef structSListCell dataMaxSize;/*存储元素，data0为头结点*/int keynum;/*每个元素的当前关键字个数*/int length;/*静态链表的当前长度*/SList;/*静态链表类型*/typedef int addrRadix;/*指针数组类型*/第58页/共63页12.6 基数排序基数排序的分配算法实现如下所示。void Distribute(SListCell data,int i,addr

35、f,addr r)/*为data中的第i个关键字keyi建立Radix个子表，使同一子表中元素的keyi相同*/*f0.Radix-1和r0.Radix-1分别指向各个子表中第一个和最后一个元素*/int j,p;for(j=0;jRadix;j+)/*将各个子表初始化为空表*/f j=0;for(p=data0.next;p;p=datap.next)j=trans(datap.keyi);/*将关键字字符转化为整数类型*/if(!f j)/*f j是空表，则f j指示第一个元素*/f j=p;elsedatar j.next=p;r j=p;/*将p所指的结点插入第j个子表中*/第59页/

36、共63页12.6 基数排序 其中，数组f j和数组r j分别存放第j个子表的第一个元素的位置和最后一个元素的位置。基数排序的收集算法实现如下所示。void Collect(SListCell data,addr f,addr r)/*按keyi将f0.Radix-1所指各子表依次链接成一个静态链表*/int j,t;for(j=0;!f j;j+);/*找第一个非空子表，succ为求后继函数*/data0.next=f j;t=r j;/*r0.next指向第一个非空子表中第一个结点*/while(jRadix-1)for(j=j+1;jRadix-1&!f j;j+);/*找下一个非空子表*

37、/if(f j)/*将非空链表连接在一起*/datat.next=f j;t=r j;datat.next=0;/*t指向最后一个非空子表中的最后一个结点*/第60页/共63页12.6 基数排序 基数排序通过多次调用分配算法和收集算法，从而实现排序，其算法实现如下所示。void RadixSort(SList*L)/*对L进行基数排序，使得L成为按关键字非递减的静态链表，L.r0为头结点*/int i;addr f,r;for(i=0;i(*L).keynum;i+)/*由低位到高位依次对各关键字进行分配和收集*/Distribute(*L).data,i,f,r);/*第i趟分配*/Coll

38、ect(*L).data,f,r);/*第i趟收集*/第61页/共63页12.7 小结 排序可分为插入排序、选择排序、交换排序、归并排序和基数排序。直接插入排序算法实现最为简单，时间复杂度在最好、最坏和平均情况下都为(n2)。简单选择排序算法的时间复杂度在最好、最坏和平均情况下都是O(n2)，而堆排序的时间复杂度在最好、最坏和平均情况下都是O(nlog2n)。冒泡排序的平均时间复杂度为O(n2)，快速排序在最好和平均情况下时间复杂度为O(nlog2n)，最坏情况下时间复杂度为O(n2)。归并排序时间复杂度在最好、最坏和平均情况下都为O(nlog2n)。基数排序是一种不需要对关键字进行比较的一种排序算法。在任何情况下，基数排序的时间复杂度均为O(d(n+rd)。从稳定性来看，直接插入排序、冒泡排序、归并排序和基数排序属于稳定的排序算法，希尔排序、快速排序、简单选择排序、堆排序属于不稳定的排序算法。第62页/共63页感谢您的观看！第63页/共63页