数据结构排序

第10章排序排序是数据处理过程中经常使用的一种重要的运算，排序的方法有很多种，本章主要讨论内部排序的各种算法，并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行了讨论。10.1概述假设一个文件是由n个记录R1，R2，…，Rn组成，所谓排序就是以记录中某个(或几个)字段值不减“正序”(或不增“逆序”)的次序将这n个记录重新排列，称该字段为排序码。能唯一标识一个记录的字段称为关键字，关键字可以作为排序码，但排序码不一定要是关键字。根据排序过程中使用到的存储介质，可以将排序分成两大类:内部排序和外部排序。

内部排序是指在排序过程中所有数据均放在内存中处理，不需要使用外存的排序方法。而对于数据量很大的文件，在内存不足的情况下，则还需要使用外存，这种排序方法称为外部排序。排序码相同的记录，若经过排序后，这些记录仍保持原来的相对次序不变，称这个排序算法是稳定的。否则，称为排序算法是不稳定的。内部排序算法的分类与性能分析：内部排序算法大致可分为5类：(1)插入排序(2)交换排序(3)选择排序(4)归并排序(5)基数排序内部排序算法的分类也可以从算法执行所需的时间，即根据排序过程中的比较次数和移动次数来划分。一般可以分为3类：(1)简单的排序算法，其时间复杂度为O(n2)；(2)先进的排序算法，其时间复杂度为O(nlogn)；(3)基数排序，其时间复杂度为O(d·n)；内部排序算法的分类与性能分析：采用不同的存储结构，对排序算法的记录移动次数也有影响。(1)如果采用线性表的顺序存储结构(数组)，则在排序过程中记录的移动是避免不了的。(2)若采用线性链表，则可避免移动记录，只需修改指针即可。这种排序称为链表排序。(3)记录采用顺序存储，另设一个地址数组，排序时只对地址数组操作，不对记录操作，这种排序称为地址排序。(如：索引文件)在本章讨论排序算法时，记录存储采用顺序表结构，记录按排序码（关键字）进行“正序”排序，排序码均为整数。有关定义如下：#defineMAXSIZE20//文件中记录个数的最大值typedefintKeyType;//定义关键字类型为整数类型typedefstruct{KeyTypekey;//记录的关键字InfoTypeotherinfo;//记录中其它数据项}RecordType;//记录类型

typedefstruct{RecordTyper[MAXSIZE+1];//r[0]闲置或用作“哨兵”单元intlength;//记录的个数}SqList;//顺序表的类型10.2插入排序插入排序的基本思想是:将待排序表中的记录，逐个地按其关键字值的大小插入到目前已经排好序的若干个记录组成的表中的适当位置，并保持新表中记录有序。10.2.1直接插入排序直接插入排序算法的思路是:初始可认为表中的第1个记录己排好序，然后将第2个到第n个记录依次插入已排序的记录组成的表中。在对第i个记录Ri进行插入时，R1，R2，…，Ri-1已排序，将记录Ri的关键字keyi与已经排好序的关键字从右向左依次比较，找到Ri应插入的位置，将该位置以后直到Ri-1各记录顺序后移，空出该位置让Ri插入。一组记录的关键字分别为:312，126，272，226，28，165，123初始时将第1个关键字作为已经排好序的，把排好序的数据记录放入中括号[]中，表示有序表，剩下的在中括号外，如下所示：[312]，126，272，226，28，165，123设前3个记录的关键字已重新排列有序，构成一个含有3个记录的有序表:[126，272，312]，226，28，165，123现在要将第4个关键字226插入！直接插入排序的过程：[126，272，312]，226，28，165，123现在要将第4个关键字226插入！将待插入的关键字226和已经有序的最后一个关键字312比较，因为待插入的关键字226小于312，所以226肯定要置于312的前面，至于是否就是置于312的前一个位置，此时还不能确定，需要继续向左比较；将所有大于待插入关键字226的那两个关键字312和272依次后移一个位置，在空出的位置插入待排序的关键字226，得一含有4个记录的有序表：[126，226，272，312]，28，165，123直接插入排序的过程(续)：voidInsertSort(SqList&L){for(i=2;i<=L.length;i++)//依次插入从第2个开始的所有元素 if(L.r[i].key<L.r[i-1].key){ L.r[0]=L.r[i];//设置哨兵(将当前记录存入0元素) L.r[i]=L.r[i-1];//将有序表中的记录后移一个位置 for(j=i-2;L.r[0].key<L.r[j].key;--j) L.r[j+1]=L.r[j];//将有序表中的记录继续后移一个位置 L.r[j+1]=L.r[0];//将当前记录插入到指定位置}}//InsertSort直接插入排序算法：该算法是稳定的！设待排序的7记录的关键字为{312，126，272，226，28，165，123}，直接插入排序算法的执行过程如下：哨兵关键字初始（）[312]，126，272，226，28，165，123i=2：（126）[126，312]，272，226，28，165，123i=3：（272）[126，272，312]，226，28，165，123i=4：（226）[126，226，272，312]，28，165，123i=5：（28）[28，126，226，272，312]，165，123i=6：（165）[28，126，165，226，272，312]，123i=7：（123）[28，123，126，165，226，272，312]直接插入排序算法的执行过程直接插入排序算法执行时间的分析：最好的情况：即初始关键字开始就是正序(递增)的情况下，该算法外循环共执行n-1次，其循环体内由于条件不成立，不需要进行移动操作。所以在最好情况下，直接插入排序算法的比较次数为(n-1)次，移动次数为0次。最坏的情况：即初始关键字开始是逆序(递减)的情况下，当插入第i个关键字时，该算法内循环要执行i-1次，每次要移动1个记录，而外循环体要执行n-l次，在循环体内不含内循环每次循环要进行3次移动操作，所以在最坏情况下，比较次数为2+…+n=(n+2)(n-1)/2，移动次数为(3+4+…+n+1)=(n+4)(n-1)/2。若待排序的记录以各种排列出现的概率相同，则可取上述最小值和最大值的平均值作为直接插入排序算法的比较次数和移动次数，约为n2/4。由此，直接插入排序算法的时间复杂度为O(n2)。10.2.2其他插入排序1.折半插入排序根据插入排序的基本思想，在找第i个记录的插入位置时，前i-l个记录已排序，将第i个记录的关键字key和已排序的前i-1个的中间位置记录的关键字进行比较，如果key小于中间位置记录关键字，则可以在前半部继续使用二分法查找，否则在后半部继续使用二分法查找，直到查找范围为空，即可确定key的插入位置。当n较大时，折半插入排序的比较次数远少于直接插入排序的平均比较次数，但二者所要进行的移动次数相等，故折半插入排序的时间复杂度也是O(n2)。voidBInsertSort(SqList&L){for(i=2;i<=L.length;i++){//依次插入从第2个开始的所有元素 L.r[0]=L.r[i];//保存待插入的元素 low=1;high=i-1; while(low<=high){//在r[low..high]中查找有序插入的位置 mid=(low+high)/2;//折半if(L.r[0].key<L.r[mid].key)high=mid-1; elselow=mid+1; }//while for(j=i-1;j>=low;--j)L.r[j+1]=L.r[j];//记录后移 L.r[low]=L.r[0];//插入}//for}//BInsertSort折半插入排序算法2.2-路插入排序2-路插入排序是在折半插入排序的基础，对插入排序中移动元素的操作进行改进。其基本思想是：将插入区域分成大致等长的两段，选择性地插入到其中一段。具体过程如下：01234563428817922165534firstfinal3428firstfinal348128firstfinal34798128firstfinal3479812228firstfinal347981162228firstfinal34557981162228firstfinal3.表插入排序折半插入排序比较次数通常比直接插入排序的比较次数少，但移动次数相等。表插入排序将在不进行记录移动的情况下，利用存储结构有关信息的改变来达到排序的目的。给每个记录附设一个所谓的指针域next，它的类型为整型，表插入排序的思路：在插入第i个记录Ri时，R1，R2，…，Ri-1已经通过各自的指针域next按关键字不减的次序连接成一个（静态链）表，将记录Ri的关键字keyi与表中已经排好序的关键字从表头向右、或称向后依次比较，找到Ri应插入的位置，将其插入在表中，使表中各记录的关键字仍然有序。#defineMAXSIZE100/*文件中记录个数的最大值*/typedefstruct{RecordTyperc; //记录项intnext; //指针项}SLNode; //表结点类型typedefstruct{SLNoder[MAXSIZE]; //0号单元为表头结点intlength; //链表长度(记录数)}SLinkList; //静态链表类型表插入排序的存储结构初始时，r[0].next用于存放表中第1个记录的下标，r[0].next的值为1，排序结束时，r[0].next中存放的是所有关键字中值最小的对应记录的下标，其它的关键字记录通过各自的指针域next按不减的次序连接成一个（静态链）表，最大的关键字记录的next为0。具体过程如下：表插入排序算法4938659776132749201------初始012345678i=2493865977613274923140----i=34938659776132749231504---49386597761327496315042--i=6493865977613274963150472-i=7493865977613274910-------49386597761327492310-----i=44938659776132749681504723i=8i=5012345678voidTableInsertSort(SLinkList&SL){SL.r[0].next=1;SL.r[1].next=0;//第1个元素为有序静态表for(i=2;i<=SL.length;i++){//依次插入从第2个开始的所有元素 q=0;p=SL.r[0].next;//p指向表中第1个元素，q指向p的前驱元素位置 while(p!=0&&(SL.r[p].rc.key<SL.r[i].rc.key){//找插入位置 q=p;p=SL.r[p].next;//继续查找 }//while SL.r[i].next=p; SL.r[q].next=i;//将第i个元素插入q和p所指向的元素之间}//for}//TableInsertSort表插入排序算法(续)10.2.3Shell(希尔)排序Shell排序的基本思想是：对n个记录进行排序，首先取一个整数d<n，将这n个记录分成d组，所有位置相差为d的倍数的记录分在同一组，在每组中使用直接插入排序进行组内排序，然后缩小d的值，重复进行分组和组内排序，一直到d=1结束。因此又称“缩小增量排序”。设待排序的9记录的关键字为{312，126，274，226，28，85，28，165，123}，开始取d=9/2=4，以后每次让d缩小一半，其排序过程为：初始状态：312126274226288528165123第1步：d=4288528165123126274226312第2步：d=2288528126123165274226312第3步：d=1282885123126165226274312voidShellSort(SqList&L){d=L.length/2;while(d>=1){ for(i=d+1;i<=L.length;i++){ //从第d+1个元素开始,将所有元素有序插入相应分组中 L.r[0]=L.r[i];//保存第i个元素 j=i-d;//向前找插入位置 while(L.r[0].key<L.r[j].key&&j>0){//找插入位置并后移 L.r[j+d]=L.r[j];//后移 j=j-d; //继续向前查找 }//while L.r[j+d]=L.r[0];//插入第i个元素 }//for d=d/2;}//while}//ShellSortShell排序算法Shell排序的分析是一个复杂的数学问题，算法的时间复杂度与增量d有关。一般是O(n3/2)。对于增量d，尽量取素数，且最后d=1。10.3交换排序交换排序的基本思路：对待排序记录两两进行关键字比较，若不满足排序顺序则交换这对记录，直到任何两个记录的关键字都满足排序要求为止。冒泡排序(BubbleSort)的基本思想为：第1趟，对所有记录从左到右每相邻两个记录的关键字进行比较，如果这两个记录的关键字不符合排序要求，则进行交换，这样一趟做完，将关键字最大者放在最后一个位置；第2趟，对剩下的n-l个待排序记录重复上述过程，又将一个关键字放于最终位置，反复进行n-l次，可将n-l个关键字对应的记录放至最终位置，剩下的即为关键字最小的记录，它在第1的位置处。如果在某一趟中，没有发生交换，则说明此时所有记录已经按排序要求排列完毕，排序结束。10.3.1冒泡排序voidBubbleSort(SqList&L){i=1;done=1;while(i<=L.length&&done){ //最多进行length次冒泡，如没有发生交换则结束 done=0; for(j=1;j<=L.length-i;j++) if(L.r[j+1].key<L.r[j].key){//两个记录不符合排序规则 L.r[0]=L.r[j]; //交换两个记录位置 L.r[j]=L.r[j+1]; L.r[j+1]=L.r[0]; done=1; }//if i++;}//while}//BubbleSort冒泡排序算法该算法是稳定的！时间复杂度与插入算法一样。例如：待排序的9个记录的关键字序列为{312，126，272，226，8，165，123，12，28}，使用冒泡排序算法进行的排序过程如下图所示：10.3.2快速排序快速排序(QuickSort)是对冒泡排序的一种改进，它的基本思想是：通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均小于另一部分记录的关键字，然后分别对这两部分记录继续进行排序，以达到整个序列有序。快速排序的实现方法是：从n个待排序的记录中任取一个记录(不妨取第1个记录，该记录称为枢轴或支点)，将该记录放置于排序后它最终应该放的位置，使它前面的记录关键字都不大于它的关键字，而后面的记录关键字都大于它的关键字，这个过程称为一趟快速排序（或一次划分）。然后对前、后两部分待排序记录重复上述过程，可以将所有记录放于排序成功后的相应位置，排序即告完成。一趟快速排序(划分)的具体做法是：附设两个指针low和high，其初值分别是1和L.length，设枢轴记录的关键字为pivotkey，其初值为low指针所指记录的关键字。首先从high位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录互相交换，然后从low所指位置起向后搜索，找到第一个关键字大于pivotkey的记录和枢轴记录互相交换，重复这两步直至low=high为止。具体算法如下：1.快速排序的实现intPartition(SqList&L,intlow,inthigh){pivotkey=L.r[low].key;while(low<high){ while(low<high&&L.r[high].key>=pivotkey)--high; L.r[low]↔L.r[high];//两个记录互换位置 while(low<high&&L.r[low].key<=pivotkey)++low; L.r[low]↔L.r[high];//两个记录互换位置}returnlow;}//Partition设待排序的7个记录的关键字序列为{126，272，12，165，123，12，28}，一次划分的过程如图所示：初始状态：pivoekey=126126272121651231228lowhigh282721216512312126lowhigh第1次循环281261216512312272lowhigh281212165123126272lowhigh第2次循环281212126123165272lowhigh281212123126165272lowhigh第3次循环281212123126165272lowhigh快速排序是不稳定的！因此，上述7个记录的关键字{126，272，12，165，123，12，28}经快速排序后的结果如下：第1次划分后：{28，12，12，123}，126，{165，272}第2次划分后：{12，12}，28，{123}，126，{165，272}第3次划分后：{12，12}，28，{123}，126，165，{272}第4次划分后：12，{12}，28，{123}，126，165，{272}voidQuickSort(SqList&L,intlow,inthigh){if(low<high){ pivotloc=Partition(L,low,high); QuickSort(L,low,pivotloc-1);//对低端子表递归调用本函数 QuickSort(L,pivotloc+1,high);//对高端子表递归调用本函数}}//QuickSort2.快速排序算法intPartition(SqList&L,intlow,inthigh){//改进的一趟排序算法L.r[0]=L.r[low];pivotkey=L.r[low].key;while(low<high){ while(low<high&&L.r[high].key>=pivotkey)--high; L.r[low]=L.r[high];//两个记录互换位置 while(low<high&&L.r[low].key<=pivotkey)++low; L.r[high]=L.r[low];//两个记录互换位置}L.r[low]=L.r[0];returnlow;}//Partition快速排序算法的时间复杂度是O(nlogn)。是该量级平均性能最好的算法。10.4选择排序选择排序的基本思想是：每次从待排序的文件中选择出关键字最小的记录，将该记录放于已排序文件的指定位置，直到已排序文件记录个数等于初始待排序文件的记录个数为止。10.4.1简单(直接)选择排序首先从所有n个待排序记录中选择关键字最小的记录，将该记录与第1个记录交换，再从剩下的n-l个记录中选出关键字最小的记录和第2个记录交换。重复这样的操作直到剩下2个记录时，再从中选出关键字最小的记录和第n-1个记录交换。剩下的那1个记录肯定是关键字最大的记录，这样排序即告完成。voidSimpleSelectSort(SqList&L){for(i=1;i<=L.length-1;i++){ k=i;//记下当前最小元素的位置 for(j=i+1;j<=L.length;j++)//向右查找更小的元素 if(L.r[j].key<L.r[k].key)k=j;//修改当前最小元素的位置 if(k!=i){//如果k不等于i，则将第k、i个元素交换 L.r[0]=L.r[k];//以第0个元素作为中间单元进行交换 L.r[k]=L.r[i]; L.r[i]=L.r[0]; }//if}//for}//SimpleSelectSort简单(直接)选择排序算法该算法是不稳定的！且最好最坏情况的时间复杂度均为O(n2)10.4.2树型选择排序树形选择排序(又称锦标赛排序)是一种按淘汰赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后对其中的较小者再进行两两比较，如此重复，直到选出最小关键字的记录为止。树形选择排序的过程如下图所示。38131338384965976513137627502710.4.2树型选择排序(续)当输出最小关键字后，根据关系的传递性，欲选出次小关键字，仅需将叶子结点中的最小关键字(13)改为“最大值”，然后从该叶子结点开始，和其左(或右)关键字进行比较，修改从叶子结点到根的路径上各结点的关键字，则根结点的关键字为次小关键字。同理，可以依此选出从小到大的所有关键字。38272738384965976576∞76275027该排序方法的时间复杂度为O(nlogn)10.4.3堆排序树形选择排序尚有辅助存储空间较多、和“最大值”进行多余的比较等缺点。为了弥补，Willioms和Floyd在1964年提出的称为堆排序的选择排序算法。堆是一个序列{k1,k2,…,kn}，它满足下面的条件：ki≤k2i并且ki≤k2i+1，当i=1,2,…,n/2（小顶堆）或者：ki≥k2i并且ki≥k2i+1，当i=1,2,…,n/2（大顶堆）采用顺序方式存储这个序列，就可以将这个序列的每一个元素ki看成是一颗有n个结点的完全二叉树的第i个结点，其中k1是该二叉树的根结点。把堆对应的一维数组(即该序列的顺序存储结构)看作一棵完全二叉树的顺序存储，那么堆的特征可解释为：完全二叉树中任一分支结点的值都小于等于(或大于等于)它的左、右儿子结点的值。堆的元素序列中的第一个元素k1（即对应的完全二叉树根结点）的值是所有元素中值最小的(或最大的)。堆排序方法就是利用这一点来选择最小(最大)元素。1224308553475391(a)小顶堆（逆序排序）大顶堆（正序排序）96278311389(b)1112302453855347919683273811911在确定n个元素中最小值或最大值（堆顶元素）之后，若再将剩余n-1个元素的序列重新建成一个堆，则又可得到次小值或次大值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。由此可见，实现堆排序要解决两个问题：如何将一个无序序列建成一个堆？在交换堆顶元素后，如何调整剩余元素成为一个新的堆？

假设将待排序列A作递减（逆序）排序，堆排序的过程如下：将待排序列A[1…n]调整为一个小顶堆；将堆顶元素A[1]（即最小排序码）与堆尾元素（即堆中最后一个元素）交换，从堆中除去堆尾元素（即最小排序码），然后调整堆中剩余元素，使它们恢复堆属性；重复进行步骤(2)，直至堆中只有1个元素。下面先讨论第二个问题。例如有一个小顶堆，当交换堆顶元素后，堆的调整过程如下。我们称这个自堆顶向叶子的调整过程为“筛选”。1224308553475391(1)调整堆9124308553475312(1)将12与91交换12302453855347919130245385534712将24与91交换2447308553915312(2)2430475385539112调整堆9147308553245312(2)9130475385532412将30与53交换3053479185532412调整堆5347538591243012(3)53534791853024123047538591245312(3)将47与85交换4753538591243012(4)4753539185302412调整堆8553534791243012(4)8553539147302412将53与91交换5353854791243012(5)5385539147302412调整堆9153854753243012(5)9185535347302412将53与91交换5391854753243012(6)5385915347302412调整堆9153854753243012(6)9185535347302412将85与91交换8553914753243012(7)8591535347302412排序结束9153854753243012(7)9185535347302412下面讨论第一个问题：如何建“堆”？从一个无序序列建堆的过程就是一个“筛选”的过程。若将此无序序列看成一棵完全二叉树，则最后一个非终端结点是第n/2个元素，“筛选”的过程就从此元素开始。例如：无序序列为{85,53,47,91,30,53,24,12}，其对应的完全二叉树为：8547533091245312(1)筛选从此结点开始91与12交换8547533012245391(2)47与24交换855347913053241285534712305324918524533012475391(3)53与12交换8524123053475391(4)85与12,再与30交换855324123053479185122453305347911224308553475391(5)最后得到的“堆”1230245385534791堆排序算法见p-282堆排序的时间复杂度：O(nlogn)。堆排序仅需一个记录大小供交换用的辅助存储空间。

归并排序是又一类不同的排序方法。所谓“归并”就是将两个或两个以上的有序表组合成一个新的有序表。

归并排序的基本思路是：将初始序列中的n个记录看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]个长度为2或1的有序子序列，再两两归并，……，如此重复，直至得到一个长度为n的有序序列为止。这种排序方法称为2-路归并排序。10.5归并排序初始关键字：[49][38][65][97][76][38][27]2-路归并排序的过程一趟归并之后：[38，49][65，97][38，76][27]二趟归并之后：[38，49，65，97][27，38，76]三趟归并之后：[27，38，38，49，65，76，97]2-路归并排序的核心操作是将一维数组中前后相邻的两个有序表归并成一个有序表。其算法见p-283。2-路归并排序的算法

基数排序(RadixSort)不同于前面介绍的排序方法，它无需比较关键字，二是通过“分组”与“收集”两个过程来完成排序任务，其中借助了多关键字排序的实现。即将排序的关键字看成是有多个关键字分量复合而成，如整数可视为若干数位的集合，每个数位的取值范围为0~9（基数为10），然后根据各关键字分量从低位到高位进行“分组”、“收集”完成排序。

例如，要对24,2,56,102,98,4,81,112进行基数排序，过程如下：（1）准备工作：将待排序的关键字编成统一长度的排序码：024,002,056,102,098,004,081,112；并根据基数设置10个的队列（分别为0~9）；（2）根据各关键字的个位数，将各关键字依次进入相应的队列，完成第一次“分组”；然后将0~9个队列中的关键字依次出队，完成第一次“收集”；（3）重复第（2）步的过程，依次完成对“十位数”、“百位数”的“分组”与“收集”，完成整个排序。10.6基数排序基数排序过程实例（按个位数分组、收集）队列0108120021020021123402456056780989待排序的关键字：024,002,056,102,098,002,081,112；分组收集收集后的关键字：081,002,102,002,112,024,056,098；基数排序过程实例（按十位数分组、收集）队列0002102002111220243450566780819098待排序的关键字：081,002,102,002,112,024,056,098

；分组收集收集后的关键字：002,102,002,112,024,056,081,098；基数排序过程实例（按百位数分组、收集）队列0002002024056081098110211223456789待排序的关键字：002,102,002,112,024,056,081,098

；分组收集收集后的关键字：002,002,024,056,081,098,102,112；内部排序算法的稳定性分析假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，Ri=Rj，且Ri在Rj之前，而在排序后的序列中，Ri仍在Rj之前，则称这种排序算法是稳定的；否则称为不稳定的。(1)冒泡排序

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。我们知道，冒泡排序的交换条件是：a[j]>a[j+1]或者a[j]<a[j+1]很明显不包括相等的情况，所以如果两个元素相等，他们不会交换；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序不会改变，所以冒泡排序是一种稳定排序算法。内部排序算法的稳定性分析(2)选择排序

选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果当前元素比一个元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5

8

5

2

9，

我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。内部排序算法的稳定性分析(3)插入排序

插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。即和冒泡排序一样：a[j]>a[j+1]或者a[j]<