数据结构-ch10排序第

1第十章内排序2概述插入排序（直接插入、希尔排序）交换排序（起泡排序、快速排序）选择排序（简单选择排序、堆排序）归并排序基数排序小结310.1概述排序：将一组杂乱无章的数据排列成一个按关键字有序的序列。

关键字(key):

通常数据对象有多个属性域，即多个数据成员组成，其中有一个属性域可用来区分对象，该域即为关键字，作为排序依据。排序的目的：便于查找。4排序算法的稳定性:

数据集合中有Ri和Rj，它们的关键字相同Ki=Kj排序前，Ri排在Rj前面排序后，Ri仍在对象Rj前面，则该排序方法是稳定的否则不稳定排序前146981167689排序后146

6891167

89不稳定排序5内部排序和外部排序

内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序6内部排序分类按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序按排序所需工作量简单的排序方法：T(n)=O(n²)

先进的排序方法：T(n)=O(nlogn)

基数排序：T(n)=O(d*n)7在排序过程中，一般进行两种基本操作：（1）比较两个关键字的大小；

（2）将记录从一个位置移动到另一个位置。

排序的时间开销:

排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。810.2插入排序(InsertSorting)基本方法：每步将一个待排序的对象，按其关键字大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。9直接插入排序(StraightInsertionSort)基本思想当插入第i(i1)个对象r[i]时前面的r[1],…,r[i-1]已经排好序用r[i]的关键字与r[i-1],r[i-2],…,r[1]的关键字顺序比较将所有关键字大于K[i]的记录依次向后移动一个位置，直到遇见一个关键字小于或者等于K[i]的记录r[j]，此时r[j]后面必为空位置，将第i个记录插入空位置即可。10i=1(12)201889182316排序结果：（89121618182023

）i=2(20)(1220)1889182316i=3(18)(121820)89182316i=4(8)(8121820)9

182316i=5(9)(89121820)182316i=6(18)(8912181820)2316i=7(23)(891218182023)16i=8(16)(89121618182023)直接插入排序过程示意监视哨11算法描述

voidInsertSort(SqList&L){ for(i=2；i<=L.length；++i) if(L.r[i]<L.r[i-1]) {L.r[0]=L.r[i]；

L.r[i]=L.r[i-1]；

for(j=i-2；L.r[0]<L.r[j]；j--) L.r[j+1]=L.r[j]；

L.r[j+1]=L.r[0]；

}}注只有当前元素比前一个元素的值小的时候才需要进行移动注设置“监视哨”注从后向前比较直到发现不比L.r[0]大的元素为止typedefstruct{ElemTyper[MAXSIZE+1];intlength;}SqList;12效率分析

空间效率：仅用了一个辅助单元。空间复杂度为O(1)。时间效率：向有序表中逐个插入记录的操作进行了n-1趟，每一趟的时间都浪费在比较和移动元素上。则，若待排序记录按关键字逆序

关键字比较次数：记录移动次数：

故，时间复杂度为O(n2)

思考：若有n个元素，直接插入排序最少移动元素多少次？稳定性：直接插入排序是稳定的排序算法13直接插入排序特点是一种稳定的排序方法；实现容易；只适宜于记录个数较少，且记录关键字基本有序的情况。14其他插入排序（折半插入、希尔排序等）——

希尔排序（Shell’sSort，缩小增量排序）基本思想：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。排序过程：先取一个正整数d1<n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。15例对下列序列采用希尔排序49386597761327495504第一趟希尔排序增量为54938659776132749550413492738496597550476012345678916例对下列序列采用希尔排序49386597761327495504第二趟希尔排序增量为31349273849659755047613385576042765494997012345678917例对下列序列采用希尔排序49386597761327495504第三趟希尔排序增量为11338550427654949977604132738494955657697012345678918算法描述voidShellInsert(SqList&L，intdk){for(i=dk+1；i<=L.length；++i)if(L.r[i].key<L->r[i-dk].key){L.r[0]=L.r[i]；

for(j=i-dk;j>0&&(L.r[0].key<L.r[j].key);j-=dk) L->r[j+dk]=L->r[j]；

L->r[j+dk]=L->r[0]；

}}voidShellSort(SqList&L，intdlta[]，intt){for(k=0；k<t；++k)ShellInsert(L，dlta[k])；

}注对表L做一趟希尔排序，增量为dk注按照增量dlta[0..t-1]对L做希尔排序是设置哨兵吗？1919

希尔排序特点

子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序。

希尔排序可提高排序速度，因为分组后n值减小，所以T(n)从总体上看是减小了

关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序

增量序列取法无除1以外的公因子最后一个增量值必须为120时间性能：希尔排序的分析非常困难，原因是何种步长序列最优难以断定。空间性能：只用一个额外空间，空间复杂度为O(1)；稳定性：希尔排序是不稳定的排序算法效率分析

21课堂练习已知序列｛70,83,100,65,10,32,7,9},请给出采用直接插入排序法对该序列进行升序排序时的每一趟的结果。解：初始:(70),83,100,65,10,32,7,91趟:(70,83),100,65,10,32,7,92趟:(70,83,100),65,10,32,7,9 3趟:(65,70,83,100),10,32,7,94趟:(10,65,70,83,100),32,7,95趟:(10,32,65,70,83,100),7,96趟:(7,10,32,65,70,83,100),97趟:(7,9,10,32,65,70,83,100)22已知序列｛70,83,100,65,10,32,7,9},采用希尔排序法（增量依次为5，3，1），写出每一趟的结果。例：{70,83,100,65,10,32,7,9}一趟结果{32，7，9，65，10，70，83，100}二趟结果{32，7，9，65，10，70，83，100}三趟结果{7，9，10，32，65，70，83，100}增量取5：70328371009

增量取3：326583710100970增量取1：32，7，9，65，10，70，83，100课堂练习2310.3快速排序

快速排序是交换排序的一种。所有交换排序的基本思想是：两两比较待排序记录的关键码，如果发生逆序（即排列顺序与排序后的次序正好相反），则交换之，直到所有记录都排好序为止。交换排序的主要算法有：起泡排序快速排序24起泡排序的基本方法是：设待排序对象序列中的对象个数为n，最多作

n-1趟排序。在第i

趟中相邻两个元素进行比较，如果逆序就交换起泡排序(BubbleSort)基本思想：大数沉底，小数冒出（小数沉底，大数冒出）25有n个元素，走n-1趟第i趟，比较n-i次

改进：起泡排序的结束条件是“在某一趟排序过程中没有进行记录交换的操作”。26voidBubbleSort(SqList&L){for(i=1;i<L.length;i++){

}

}//BubbleSortif(Exchange==false)return;

if(L.r[j+1]<L.r[j])

{

L.r[j+1]←→L.r[j];}

for(j=1;j<=L.length-i;j++)Exchange=false;Exchange=true27时间分析:最好的情况（关键字在记录序列中顺序有序）：只需进行一趟起泡“比较”的次数：最坏的情况（关键字在记录序列中逆序有序）：需进行n-1趟起泡“比较”的次数：0“移动”的次数：“移动”的次数：n-1-128时间复杂度：O(n2)

空间复杂度：O(1)

稳定性：稳定29快速排序(QuickSort)快速排序方法的基本思想是任取待排序对象序列中的某个对象(常取第一个对象)作为枢轴(pivot)，按照该对象的关键字大小，将整个对象序列划分为左右两个子序列：左侧子序列中所有对象的关键字都小于枢轴对象的关键字右侧子序列中所有对象的关键字都大于枢轴对象的关键字枢轴对象则排在这两个子序列中间(这也是该对象最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。30例对下列序列采用快速排序4938659776132749第趟快速排序14938659776132749枢轴lowhigh49lowhighlowhighhighlow==high则此位置就是枢轴49的最终位置第一趟快速排序结束31例对下列序列采用快速排序4938659776132749第趟快速排序122738134976976549枢轴首先对49之前的数据采用快速排序27lowhighlow==high27枢轴27之前和之后都只有一个值，不再需要排序133832例对下列序列采用快速排序4938659776132749第趟快速排序2然后对49之后的数据采用快速排序13384976976549枢轴76lowhighlowLow==high76枢轴76后面的97也不需再次排序2797第二趟快速排序结束33例对下列序列采用快速排序4938659776132749第趟快速排序231338494965762797枢轴对76之前的数据采用快速排序49highlowlow==high4965整个排序结束34

算法实现QuickSort(List){if(List的长度大于1){

将序列List划分为两个子序列

LeftList和RightList;

QuickSort(LeftList);

QuickSort(RightList); }}35voidQSort(Sqlist&L,intlow,inthigh){if(low<high){pivotloc=Partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}}注：快速排序的算法，采用递归思想完成36注

对从下标low到high的顺序表做一趟快速排序算法描述intpartition(sqlist&L,intlow,inthigh){pivotkey=L.r[low];while(low<high){while(low<high&&L.r[high]>=pivotkey)--high;L.r[low]=L.r[high];while(low<high&&L.r[low]<=pivotkey)++low;L.r[high]=L.r[low];}L.r[low]=pivotkey;returnlow;}注

将低下标设置为枢轴注当low=high时，结束本趟排序注返回值是枢轴的排序位置37

通常，快速排序被认为是在所有同数量级(O(nlogn))的排序方法中，其平均性能最好。算法评价时间复杂度快速排序在平均情况下的时间复杂性为O(nlog2n)最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n²)稳定性快速排序为不稳定的排序算法38练习：

1、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为

()

40,38,46,56,79,84

2、在对一组记录（54,38,96,23,15,72,60,45,83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次。

解：当要插入60时，前6个元素已经有序，即为：15，23，38，54，72，96，需从后向前比较到54为止，故要比较3次。339练习：2、快速排序方法在（）情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数

C40

选择排序(SelectionSort)的基本思想是：每一趟在n-i+1(i=1，2，…，n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。其中最简单、且最熟悉的是简单选择排序(SimpleSelectionSort)。10.4选择排序(SelectionSort)41直接（简单）选择排序第一趟排序869327原始数据869327第一趟排序26938

7第二趟排序269387第二趟排序2

39687第三趟排序2

39687第三趟排序2

3

6

987第四趟排序2

3

6987第四趟排序2

3

6

7

89第五趟排序2

3

6

7

89第五趟排序2

3

6

7

891、求数组的最小元素2、交换数组中的两个元素42排序过程:首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换重复上述操作，共进行n-1趟排序后，排序结束。

voidSelectSort(SqList&L){

//对顺序表L作简单选择排序

for(i=1;i<L.length；++i){

//选择第i小的记录，并交换到位

Min=SelectMinKey(L，i)；

//在L.r[i..L.length]中选择key最小的记录

if(i!=Min)L.r[i]←→L.r[Min]；//与第i个记录交换

}}

43效率分析

时间效率移动次数：最少0次，最多为3(n-1)次比较次数：时间复杂度：O(n2)空间复杂度：O(1)。稳定性简单选择排序是不稳定的排序算法。44选择排序-----堆排序

堆的定义：n个元素的序列{k1,k2,…,kn}当且仅当满足下关系时，称之为堆。

ki≤k2iki≥k2i

或

ki≤k2i+1，ki≥k2i+1(i=1,2,…,n/2)

例：{96,83,27,38,11,9}{12,36,24,85,47,30,53,91}

12362485473053919683273811945

基本思想：将无序序列建成一个堆，得到关键字最小（或最大）的记录；输出堆顶的最小（大）值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次小值；

重复执行，得到一个有序序列，这个过程叫堆排序。

由此，实现堆排序需要解决两个问题：

(1)如何由一个无序序列建成一个堆?(2)如何在输出堆顶元素之后，调整剩余元素成为一个新的堆?第二个问题解决方法——筛选筛选方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”。`46例对下面堆进行筛选382749766549973813274976654997131313此时13从原来堆中脱离剩下的序列不再是堆需要调整97的替入导致原来的堆在该位置失去平衡故从顶端97开始调整调整方法是先在97的2个孩子结点位置找到比较小的值，再和97交换47例对下面堆进行筛选3827497665499713382749766549139797的替入再次导致该位置失去平衡不再是堆继续调整9797此时序列再次调整成堆继续筛选279797272727随着筛选的进行，越来越多的堆顶被移动到存储结构靠后的位置。此过程不再描述，最后结果如上图977665494938977665494938筛选结束排序结束48第一个问题（初始建堆）的解决方法

从无序序列的第n/2个元素（即此无序序列对应的完全二叉树的最后一个非终端结点）起，至第一个元素止，进行反复筛选。例含8个元素的无序序列（49，38，65，97，76，13，27，50）4965382713769750496538271376509749133827657650974913382765765097132738496576509749voidHeapAdjust(SqList＆H，ints，intm){

//已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，

//本函数调整H.r[s]的关键字，使H.r[s..m]成为一个大顶堆

rc=H.r[s];for(j=2*s;j<=m;j*=2){//沿key较大的孩子结点向下筛选

//j为key较大的记录的下标

if(j<m&&(H.r[j].key<H.r[j+1].key))++j;if(rc.key>=H.r[j].key)break;//rc应插入在位置s上

H.r[s]=H.r[j]；s=j；

}H.r[s]=rc;//插入}//HeapAdjust

算法10.10最大堆的向下调整算法50voidHeapSort(HeapType&H){

//对顺序表H进行堆排序。

for(i=H.length/2;i>0;--i)

//把H.r[1..length]建成大顶堆

HeapAdjust(H，i，H.