插入排序解析课件

v概述概述v插入排序插入排序v快速排序快速排序v选择排序选择排序v归并排序归并排序第八章第八章 内部排序内部排序概述第八章 内部排序18.1 概概 述述 n排排序序：将将一一个个数数据据元元素素的的任任意意序序列列，重重新新排排列列成成一一个按关键字有序的序列。个按关键字有序的序列。n数数据据表表(datalist):它它是是待待排排序序数数据据对对象象的的有有限限集集合。合。n主主关关键键字字(key):数数据据对对象象有有多多个个属属性性域域,即即多多个个数数据据成成员员组组成成,其其中中有有一一个个属属性性域域可可用用来来区区分分对对象象,作为排序依据，称为关键字。也称为作为排序依据，称为关键字。也称为排序码排序码。8.1 概 述 排序：将一个数据元素的任意序列，重新2n排序方法的稳定性排序方法的稳定性:如果在对象序列中有两如果在对象序列中有两 个对象个对象Ri和和Rj,它们的排序码它们的排序码 Ki=Kj,且在排序之前且在排序之前,对象对象Ri排在排在Rj前面。如果在排序之后前面。如果在排序之后,对象对象Ri仍在仍在对象对象Rj的前面的前面,则称这个排序方法是则称这个排序方法是稳定稳定的的,否则否则称这个排序方法是称这个排序方法是不稳定不稳定的。的。n内排序与外排序内排序与外排序:内排序内排序是指在排序期间数据对是指在排序期间数据对象全部存放在内存的排序；象全部存放在内存的排序；外排序外排序是指在排序期间是指在排序期间全部对象个数太多，不能同时存放在内存，必须根全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排据排序过程的要求，不断在内、外存之间移动的排序。序。排序方法的稳定性:如果在对象序列中有两 个对象Ri和Rj,3n排序的时间开销排序的时间开销:排序的时间开销排序的时间开销是衡量算法好坏的最重要的标志。排序是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的的时间开销可用算法执行中的数据比较数据比较次数次数与与数据移动次数数据移动次数来衡量。来衡量。排序的时间开销:排序的时间开销是衡量算法好坏的最重要的4内排序分类内排序分类n依不同原则依不同原则插入排序插入排序、交换排序交换排序、选择排序选择排序、归并归并排序排序、和计数排序等和计数排序等。n依所需工作量依所需工作量简单排序简单排序-时间复杂度时间复杂度O(n2)先进排序方法先进排序方法-时间复杂度时间复杂度O(n logn)基数排序基数排序-时间复杂度时间复杂度O(d.n)内排序分类依不同原则58.2 插入排序插入排序(Insert Sorting)v基本思想基本思想 每步将一个待排序的对象每步将一个待排序的对象,按其按其排序码大小排序码大小,插入到前面已经排好序的一组插入到前面已经排好序的一组对象的适当位置上对象的适当位置上,直到对象全部插入为止。直到对象全部插入为止。8.2 插入排序(Insert Sorting)基本思想 6n基本思想基本思想 当插入第当插入第i(i 1)个对象时个对象时,前面的前面的V0,V1,Vi-1已经排好序。这时已经排好序。这时,用用Vi的排序码与的排序码与Vi-1,Vi-2,的排序码顺序进的排序码顺序进行比较行比较,找到插入位置即将找到插入位置即将Vi插入插入,原来位置上原来位置上的对象向后顺移。的对象向后顺移。v直接插入排序直接插入排序 (Straight Insert Sort)基本思想 当插入第i(i 1)个对象时,前面的V7void InsertSort(SqList&L)/按非递减顺序对表进行排序 for(i=2;i L.length;+i)if LT(L.ri.key,L.ri-1.key)/”=2&change;-i)change=FALSE;/假定未交换 for(j=1;j aj+1)/逆序 aj aj+1;/交换 change=TRUE;/有交换 起泡排序的算法（教材 page 16)15 n第第i趟趟对对待待排排序序记记录录序序列列a1,a2,an-i+-i+1进进行行排排序序,结结果果将将该该序序列列中中关关键键字字最最大大的的记记录录交交换换到到序序列列的的第第n-i+1个个位位置置,其其它它记记录录也也都都向向排排序序的的最最终终位位置移动。置移动。n最多做最多做n-1趟起泡就能把所有记录排好序。趟起泡就能把所有记录排好序。n在在记记录录的的初初始始排排列列已已为为正正序序时时,算算法法只只执执行行一一趟趟起起泡泡,做做n-1次次关关键键字字比比较较,不不移移动动记记录录。这这是是最最好好的的情情形形。第i趟对待排序记录序列a116n最最坏坏的的情情形形是是初初始始序序列列为为逆逆序序，算算法法执执行行n-1趟趟起起泡泡,第第i趟趟做做 n-i 次次关关键键字字比比较较,执执行行 n-i 次次记记录录交交换换。总总的的关关键键字字比比较较次次数数KCN和和记记录录移移动动次次数数RMN为：为：最坏时间复杂度为最坏时间复杂度为O(n2)n起泡排序是一个起泡排序是一个稳定稳定的排序方法的排序方法。最坏的情形是初始序列为逆序，算法执行n-1趟起泡,第i趟做 17快速排序快速排序 (Quick Sort)n基本思想：基本思想：任取待排序记录序列中的某个记录任取待排序记录序列中的某个记录(例例如取第一个记录如取第一个记录)作为基准作为基准,按照该记录的关键按照该记录的关键字大小字大小,将整个记录序列划分为左右两个子序列：将整个记录序列划分为左右两个子序列：u左侧子序列中所有记录的排序码都小于或等于左侧子序列中所有记录的排序码都小于或等于基准记录的排序码基准记录的排序码 u右侧子序列中所有记录的排序码都大于基准记右侧子序列中所有记录的排序码都大于基准记录的排序码录的排序码u基准记录则排在这两个子序列中间基准记录则排在这两个子序列中间(这也是该记这也是该记录最终应安放的位置录最终应安放的位置)。快速排序(Quick Sort)基本思想：任取待排序记录序18n分别对这两个子序列重复施行上述方法，分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为止。直到所有的记录都排在相应位置上为止。n基准记录也称为基准记录也称为枢轴（或支点）枢轴（或支点）(pivot)记记录。录。插入排序解析课件19QuickSort(List)if(List的长度大于1)将序列List划分为两个子序列 LeftList 和 Right List;QuickSort(LeftList);QuickSort(RightList);将两个子序列 LeftList 和 RightList 合并为一个序列List;快速排序算法描述快速排序算法描述QuickSort(List)快速排序算法描述20快速排序的过程快速排序的过程212108082525494925*25*1616初始关键字初始关键字08082525494925*25*1616212108082525494925*25*161608082525494925*25*161608082525494925*25*161608082525494925*25*16162121pivotkey一次交换一次交换二次交换二次交换三次交换三次交换四次交换四次交换完成一趟排序完成一趟排序ijijjiijji ji快速排序的过程2108254925*16初始关键字082542108082525494925*25*16162121完成一趟排序完成一趟排序分别进行快速排序分别进行快速排序08082525494925*25*16162121有序序列有序序列08082525494925*25*1616212108254925*1621完成一趟排序分别进行快速排序08222 快速排序的算法快速排序的算法void QuickSort(SqList&L,int low,int high)/在序列lowhigh 中递归地进行快速排序 if(low high)pivotloc=Partition(L,low,high);/划分 QuickSort(L,low,pivotloc-1);/对左序列同样处理 QuickSort(L,pivotloc+1,high);/对右序列同样处理 算法算法 10.7 快速排序的算法23int Partition(SqList&L,int low,int high)L.r0=L.rlow;/子表的第一个记录作枢轴记录 pivotkey=L.rlow.key;/枢轴记录关键字 While(lowhigh)While(low=pivotkey)-high;L.rlow=L.rhigh;/小于枢轴记录的移到区间的左侧 While(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;/大于枢轴记录的移到区间的右侧 L.rlow=L.r0;/枢轴记录到位 return low;算法 10.6(b)int Partition(SqList&L,int24 n算法算法Partition利用序列第一个对象作为基准，将整个序利用序列第一个对象作为基准，将整个序列划分为左右两个子序列。算法中执行了一个循环列划分为左右两个子序列。算法中执行了一个循环,只要只要是排序码小于基准对象排序码的对象都移到序列左侧是排序码小于基准对象排序码的对象都移到序列左侧,最最后基准对象安放到位后基准对象安放到位,函数返回其位置。函数返回其位置。212125*25*25*2525494908081616算法算法Quicksort是一个递归的算法是一个递归的算法,其其递归树递归树如图所示。如图所示。算法Partition利用序列第一个对象作为基准，将25算法分析算法分析n快速排序的趟数取决于递归树的高度。快速排序的趟数取决于递归树的高度。n如果每次划分对一个记录定位后如果每次划分对一个记录定位后,该记录的左侧子序列与右该记录的左侧子序列与右侧子序列的长度相同侧子序列的长度相同,则下则下 一步将是对两个长度减半的子一步将是对两个长度减半的子序列进行排序序列进行排序,这是最理想的情况。这是最理想的情况。n在在 n个元素的序列中个元素的序列中,对一个记录定位所需时间为对一个记录定位所需时间为 O(n)。若设若设 t(n)是对是对 n 个元素的序列进行排序所需的时间个元素的序列进行排序所需的时间,而而且每次对一个记录正确定位后且每次对一个记录正确定位后,正好把序列划分为长度相等正好把序列划分为长度相等的两个子序列的两个子序列,此时此时,总的计算时间为：总的计算时间为：算法分析快速排序的趟数取决于递归树的高度。26 T(n)cn+2T(n/2)/c 是一个常数是一个常数 cn+2(cn/2+2T(n/4)=2cn+4T(n/4)2cn+4(cn/4+2T(n/8)=3cn+8T(n/8)cn log2n+nT(1)=O(n log2n)n可可以以证证明明,函函数数quicksort的的平平均均计计算算时时间间也也是是O(nlog2n)。实实验验结结果果表表明明:就就平平均均计计算算时时间间而而言言,快快速速排排序序是是所所有有内内排排序方法中最好的一个序方法中最好的一个。n快快速速排排序序是是递递归归的的，需需要要有有一一个个栈栈存存放放每每层层递递归归调调用用时时的的指指针和参数。针和参数。T(n)cn+2T(n/2)/27n最最大大递递归归调调用用层层次次数数与与递递归归树树的的高高度度一一致致,理理想想情情况况为为 log2(n+1)。因此，要求存储开销为。因此，要求存储开销为 O(log2n)。n在在最最坏坏的的情情况况,即即待待排排记记录录序序列列关关键键字字有有序序（正正序序或或逆逆序序）时时,其其递递归归树树成成为为单单支支树树,每每次次划划分分只只得得到到一一个个比比上一次少一个对象的子序列。总的关键字比较次数将达上一次少一个对象的子序列。总的关键字比较次数将达 此时得到算法的最坏时间复杂度为此时得到算法的最坏时间复杂度为O(n2)n改进枢轴记录的选取：改进枢轴记录的选取：“三者取中三者取中”n快速排序是一种快速排序是一种不稳定不稳定的排序方法。的排序方法。最大递归调用层次数与递归树的高度一致,理想情况为 log228 基本思想：基本思想：每一趟在每一趟在 n-i+1(i=1,n-1)个个记录中选出关键字最小的记录记录中选出关键字最小的记录,作为有序序列作为有序序列中的第中的第 i 个记录。个记录。8.4 选择排序选择排序（Selection Sort)选准了再做记录移动 基本思想：每一趟在 n-i+1(i=1,29简单选择排序是一种简单的排序方法简单选择排序是一种简单的排序方法,它的基本步它的基本步骤是：骤是：在一组对象在一组对象 rirn-1 中选择具有最小关键字的记录；中选择具有最小关键字的记录；若若它它不不是是这这组组对对象象中中的的第第一一个个对对象象,则则将将它它与与这这组组对对象象中中的第一个对象对调的第一个对象对调;在在这这组组对对象象中中剔剔除除这这个个具具有有最最小小排排序序码码的的对对象象。在在剩剩下下的的对对象象Vi+1Vn-1中中重重复复执执行行第第、步步,直直到到剩剩余余对象只有一个为止。对象只有一个为止。简单选择排序简单选择排序 (Simple Selection Sort)简单选择排序是一种简单的排序方法,它的基本步骤是：简单选3021212525494925*25*16160808 1 2 3 4 5 6212125*25*i=1=14949252516162525161608084949080825*25*49492121i=2=2i=3=30808161625*25*25252121初始初始初始初始最小者最小者 08 08交换交换交换交换21,0821,08最小者最小者 16 16交换交换交换交换25,1625,16最小者最小者 21 21交换交换交换交换49,2149,21 简单选择排序的过程简单选择排序的过程21254925*1608 1 2 31最小者最小者 25*25*无交换无交换无交换无交换494925*25*1 2 3 4 5 625*25*i=5=5252516160808494925*25*49492121结果结果i=4=40808161625252121最小者最小者 25 25无交换无交换无交换无交换2525212116160808各趟排序后的结果各趟排序后的结果最小者 25*4925*1 2 32直接选择排序的算法直接选择排序的算法void SelectSort(SqList&L)for(i=1;i L.length;+i)/共n-1趟 k=i;/选择具有最小关键字的记录 for(int j=i+1;j n;j+)if(L.rj L.rk)k=j;/当前具最小关键字的记录 if(k!=i)/对换到第 i 个位置 L.ri L.rk);算法 10.9直接选择排序的算法33关键字比较次数关键字比较次数 KCN 与记录的初始排列无关。与记录的初始排列无关。设有 n 个记录,则第 i 趟选择具有最小关键字记录所需的比较次数总是 n-i 次。总的关键字比较次数为n记录的移动次数记录的移动次数RMN与记录序列的初始排列有关。与记录序列的初始排列有关。当初始序列为正序时，RMN取最小值“0”；最坏情况是每一趟都要进行交换，RMN取最大值为 3(n-1)。n总的时间复杂度为总的时间复杂度为O(n2)n简单选择排序是一种简单选择排序是一种不稳定不稳定的排序方法。的排序方法。关键字比较次数 KCN 与记录的初始排列无关。记录的移动次数34堆排序堆排序(Heap sort)v堆堆(Heap)的定义：的定义：设有一个关键字集合，按完全二叉树的顺序存储方式存设有一个关键字集合，按完全二叉树的顺序存储方式存放在一个一维数组中。对它们从根开始，自顶向下，同放在一个一维数组中。对它们从根开始，自顶向下，同一层自左向右从一层自左向右从 1开始连续编号。若满足开始连续编号。若满足 Ki K2i&Ki K2i+1 或或 Ki K2i&Ki K2i+1,则称该关键字集合构成一个则称该关键字集合构成一个堆堆。前者称为前者称为小根（顶）堆小根（顶）堆，后者称为，后者称为大根（顶）堆大根（顶）堆。堆排序(Heap sort)堆(Heap)的定义35完全二叉树完全二叉树 顺序表示顺序表示Ki K2i&Ki K2i+1完全二叉树完全二叉树 顺序表示顺序表示Ki K2i&Ki K2i+1090987877878454565653131532323531717完全二叉树完全二叉树0909878778784545656536v堆排序的步骤堆排序的步骤（以小根堆为例）（以小根堆为例）1.根据初始的输入数据，形成初始堆；根据初始的输入数据，形成初始堆；2.输出堆顶元素（最小记录）；输出堆顶元素（最小记录）；3.对剩余元素做调整，形成新的堆；对剩余元素做调整，形成新的堆；4.重复步骤重复步骤2,3，直到剩余元素个数为零。，直到剩余元素个数为零。堆排序堆排序堆排序的步骤（以小根堆为例）堆排序374949252525*25*2121161608081234560808252525*25*16162121494913654249 25 21 25*16 0849 25 21 25*16 0808 25 21 25*16 08 25 21 25*16 4949交换交换交换交换 1 1号与号与号与号与 6 6 号元素号元素号元素号元素,6 6号元素就位号元素就位号元素就位号元素就位初始大根堆初始大根堆初始大根堆初始大根堆堆排序过程堆排序过程(大根堆）大根堆）492525*211608123456082525*162138252525*25*0808212116164949123456161625*25*080825252121494913654225 25*21 08 16 25 25*21 08 16 494916 25*21 08 16 25*21 08 2525 4949交换交换交换交换 1 1 号与号与号与号与 5 5 号元素号元素号元素号元素,5 5号元素就位号元素就位号元素就位号元素就位从从从从 1 1号到号到号到号到 5 5 号号号号 重新重新重新重新调整为大根堆调整为大根堆调整为大根堆调整为大根堆2525*082116491234561625*0825213925*25*161608082121252549491234560808161625*25*25252121494913654225*16 21 08 25*16 21 08 2525 494908 16 21 08 16 21 25*25*2525 4949交换交换交换交换 1 1 号与号与号与号与 4 4 号元素号元素号元素号元素,4 4 号元素就位号元素就位号元素就位号元素就位从从从从 1 1 号到号到号到号到4 4 号号号号 重新重新重新重新调整为大根堆调整为大根堆调整为大根堆调整为大根堆25*1608212549123456081625*2521402121161625*25*0808252549491234560808161625*25*25252121494913654221 16 08 21 16 08 25*25*2525 494908 16 08 16 2121 25*25*2525 4949交换交换交换交换 1 1 号与号与号与号与 3 3 号元素号元素号元素号元素,3 3号元素就位号元素就位号元素就位号元素就位从从从从 1 1 号到号到号到号到 3 3 号号号号 重新重新重新重新调整为大根堆调整为大根堆调整为大根堆调整为大根堆211625*082549123456081625*2521411616080825*25*2121252549491234560808161625*25*25252121494913654216 08 21 16 08 21 25*25*2525 494908 08 16 16 2121 25*25*2525 4949交换交换交换交换 1 1号与号与号与号与 2 2 号元素号元素号元素号元素,2 2 号元素就位号元素就位号元素就位号元素就位从从从从 1 1 号到号到号到号到 2 2 号号号号 重新重新重新重新调整为大根堆调整为大根堆调整为大根堆调整为大根堆160825*212549123456081625*252142v两个关键问题两个关键问题：1.如何由一个无序序列建成一个堆如何由一个无序序列建成一个堆?2.如何在输出堆顶元素后，调整剩余元素成为一个如何在输出堆顶元素后，调整剩余元素成为一个新的堆？新的堆？两个关键问题：43方法方法：自顶向下地：自顶向下地“筛选筛选”堆的调整（问题堆的调整（问题2 2）38657649972713499765763849271349rc=38sjsjs方法：自顶向下地“筛选”堆的调整（问题2）38657649944void HeapAdjust(HeapType&H,int s,int m)/已知H.rs.m中记录的关键字除H.rs.key之外均满足堆的定义，本函 /数调整H.rs的关键字，使H.rs.m成为一个大根堆(对其中记录的关键/字而言 rc=H.rs;for(j=2*s;j=m;j*=2)/沿key较大的孩子结点向下筛选 if(j0;-i)/把H.r1.H.length建成大根堆 HeapAdjust(H,i,H.length);for(i=H.length;i1;-i)H.r1H.ri;/将堆顶记录和当前未经排序子序列H.r1.i中 /最后一个记录相互交换 HeapAdjust(H,1,i-1);/将H.r1.I-1重新调整为大根堆 算法 10.11堆的建立算法堆的建立算法void HeapSort(HeapType&H)49n堆排序的最坏时间复杂度为堆排序的最坏时间复杂度为O(nlog2n)，优，优于快速排序的最坏时间复杂度于快速排序的最坏时间复杂度O(n2)。n算法的空间复杂度为算法的空间复杂度为O(1)。n堆排序是一个堆排序是一个不稳定不稳定的排序方法。的排序方法。（为什么？）（为什么？）堆排序的算法分析堆排序的算法分析堆排序的最坏时间复杂度为O(nlog2n)，优于快速排序的最508.5 归并排序归并排序（Merging Sort)n归并归并 将两个或两个以上的有序表合并成一个新的有序表。将两个或两个以上的有序表合并成一个新的有序表。n2-路归并路归并(2-way merging)原始序列原始序列initList 中两个有序表中两个有序表 initListl initListm和和initListm+1 initListn，它们，它们可归并成一个有序表可归并成一个有序表,存于另一记录序列存于另一记录序列mergedList的的 l n 中中。8.5 归并排序（Merging Sort)归并51left mid mid+1 rightleft mid mid+1 rightinitListinitListi ji jleft rightleft rightk kmergeListmergeListn设变量设变量 i 和和 j 是表是表initListl m和和initList m+1 n的当前检测指针。的当前检测指针。k 是存放指针。是存放指针。u当当 i 和和 j 都在两个表的表长内变化时都在两个表的表长内变化时,根据对应项根据对应项的关键字的大小的关键字的大小,依次把关键字小的记录排放到新依次把关键字小的记录排放到新表表 k 所指位置中；所指位置中；u当当 i 与与 j 中有一个已经超出表长时，将另一中有一个已经超出表长时，将另一 个表中个表中的剩余部分照抄到新表中。的剩余部分照抄到新表中。08 21 25 25*49 62 72 93522路归并排序算法路归并排序算法 算法思想算法思想 假设初始对象序列有假设初始对象序列有 n 个对象，首先把它看个对象，首先把它看成是成是 n 个长度为个长度为 1 的有序子序列的有序子序列(归并项归并项)，先做两两归并，得到，先做两两归并，得到 n/2 个长度为个长度为 2 的归并项的归并项(如果如果 n 为奇数，则最后一个有序为奇数，则最后一个有序子序列的长度为子序列的长度为1)；再做两两归并，；再做两两归并，如，如此重复，最后得到一个长度为此重复，最后得到一个长度为 n 的有序序列。的有序序列。2路归并排序算法 算法思想532-路归并算法路归并算法void Merge(RcdType SR,RcdType&TR,int i,int m,int n)/将有序的SRI.m和SRm+1.n归并为有序的TRi.n for(j=m+1,k=i;i=m&j=n;+k)/平移指针，一次扫描 if LQ(SRi.key,Srj.key)TRk=SRi+;else TRk=SRj+;if(j=m)TRk.n=SRi.m;/将剩余的SRi.m复制到TR if(j=n)TRk.n=SRj.n;/将剩余的SRj.n复制到TR 算法 10.122-路归并算法54void Msort(RcdType SR,RcdType&TR1,int s,int t)/将SRs.t归并排序为TRs.t if(s=t)TR1s=SRs;else m=(s+t)/2;/将SRs.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归并到TR1m.t 算法 10.13递归形式的递归形式的2-路归并排序算法路归并排序算法void Msort(RcdType SR,RcdTyp55Void MergeSort(SqList&L)/对顺序表对顺序表L L作归并排序作归并排序 Msort(L.r,L.r,1,L.length);算法10.14特点：形式简洁，效率很低Void MergeSort(SqList&L)特点：形56迭代（非递归）的归并排序算法迭代（非递归）的归并排序算法h h=1=1h h=2=2h h=4=4h h=8=8h h=16=16迭代（非递归）的归并排序算法212525*93627208357一趟归并排序的情形一趟归并排序的情形n设设initList0到到initListn-1中中 n 个对象已经分个对象已经分为一些长度为为一些长度为 h 的归并项的归并项,将这些归并项两两归将这些归并项两两归并并,归并成长度为归并成长度为 2h 的归并项的归并项,结果放到结果放到mergedList 中。中。n如果如果n不是不是2h的整数倍的整数倍,则一趟归并到最后则一趟归并到最后,可能可能遇到两种情形：遇到两种情形：u 剩下一个长度为剩下一个长度为h的归并项和另一个长度不足的归并项和另一个长度不足len的归并项的归并项,可用可用merge算法将它们归并成算法将它们归并成一个长度小于一个长度小于 2h的归并项。的归并项。u只剩下一个归并项，其长度小于或等于只剩下一个归并项，其长度小于或等于h,将它将它直接抄到直接抄到mergedList 中。中。一趟归并排序的情形设initList0到initList58v时间复杂度为时间复杂度为O(nlog2n)：做一趟两路归并排序,要调用n/(2*h)O(n/h)次merge；整个归并过程需进行log2n 趟,所以算法总的时间复杂度为O(nlog2n)。空间复杂度为空间复杂度为O(n)归并排序占用附加存储较多,需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。归并排序是一个归并排序是一个稳定稳定的排序方法。的排序方法。迭代的归并排序算法性能分析迭代的归并排序算法性能分析时间复杂度为O(nlog2n)：迭代的归并排序算法性能分析59各种排序方法的比较各种排序方法的比较各种排序方法的比较60n作业：习题集 9.21(page 57)hash查找 习题集 10.34(page 65)-堆排序n课后阅读：DSDEMO课件中的相关排序算法作作 业业 12作业：作 业 1261数据库原理部分王珊、陈红，数据库系统原理教程，清王珊、陈红，数据库系统原理教程，清华大学出版社，华大学出版社，1998数据库原理部分62