计算机软件基础课件：排序

排序BasicsofComputerSoftware答辩人：XXX排序的概念内排序外排序1排序将一个数据元素的任意序列，重新排列成一个按关键字有序的序列2内排序在排序期间数据对象全部存放在内存的排序3外排序在排序期间全部对象个数太多，不能同时存放在内存，必须根据排序过程的要求，不断在内、外存之间移动的排序排序的基本概念排序的基本概念排序的时间开销02排序的稳定性01如果在对象序列中有两个对象r[i]和r[j],它们的排序码k[i]==k[j]，在排序之前,对象r[i]排在r[j]前面。如果在排序之后,对象r[i]仍在对象r[j]的前面,则称这个排序方法是稳定的,否则称这个排序方法是不稳定的排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销一般可用算法执行中的数据比较次数与数据移动次数来衡量。目录起泡排序1插入排序2选择排序3快速排序45希尔排序6归并排序7基数排序8堆排序起泡排序PART1基本方法：设待排序对象序列中的对象个数为n。一般地，第i趟起泡排序从1到n-i+1依次比较相邻两个记录的关键字，如果发现逆序，则交换之，其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。排序算法：起泡排序252149251682125251684921251682549211682525492125254916825214925168原始关键字第一趟排序第二趟排序第三趟排序第四趟排序第五趟排序voidBubbleSort(intV[],intn){inti=1;intexchange=1;while(i<n&&exchange){exchange=0; //标志置为0,假定未交换

for(intj=0;j<=n-1-i;j++)if(V[j]>V[j+1]){//逆序Swap(V[j],V[j+1]);//交换

exchange=1;//标志置为1,有交换

}i++;}}起泡排序的算法起泡排序分析1每趟排序，对象均向最终位置移动第i趟对序列V[0],…,V[n-i]进行排序，将最大的对象交换到V[n-i]的位置，其它对象也都向排序的最终位置移动2最多趟数最多做n-1趟起泡就能把所有对象排好序.3最少趟数在序列已经按从小到大排好序时，只执行一趟起泡排序，做n-1次排序码比较，不移动对象。这是最快的情形4最坏情形最坏的情形是算法执行n-1趟起泡，第i趟做n-i次排序码比较，执行n-i次对象交换。此时，共进行n(n-1)/2次比较和交换，起泡排序是一个稳定的排序方法。插入排序PART2具体来说：当插入第I(I

1)个对象时,前面的V[0],V[1],…,V[i-1]已经排好序。这时,用V[i]的排序码与V[i-1],V[i-2],…的排序码顺序进行比较,找到插入位置即将V[i]插入,原来位置上的对象向后顺移。具体来说02基本思想01每步将一个待排序的对象,按其排序码大小,插入到前面已经排好序的一组对象的适当位置上,直到对象全部插入为止。当插入第i个对象时，前面的V[0],V[1],…,V[i-1]已经排好序。这时，用V[i]的排序码与V[i-1],V[i-2],…的排序码顺序进行比较，找到插入位置即将V[i]插入，

原来位置上的对象向后顺移。排序算法：插入排序2516252149251682125492516821254916821252549825214925168原始关键字第一趟排序第二趟排序第三趟排序第四趟排序第五趟排序821252549162516temp排序算法：插入排序过程typedefintSortData;voidInsertSort(SortDataV[],intn){

SortDatatemp;inti,j;for(i=1;i<n;i++){temp=V[i];for(j=i;j>0;j--)//从后向前顺序比较

if(temp<V[j-1])V[j]=V[j-1];elsebreak;V[j]=temp;}}排序算法：插入排序算法插入排序算法分析1设待排序对象个数为n,则该算法的主程序执行n-1趟2排序码比较次数和对象移动次数与对象排序码的初始排列有关3最好情况下,排序前对象已按从小到大有序,每趟只需与前面有序序列的最后一个对象比较1次,移动2次对象,总的排序码比较次数为n-1,对象移动次数为2(n-1)4最坏情况下,第i趟时第i个对象必须与前面i个对象都做比较,并且每做1次比较就要做1次数据移动5直接插入排序是一种稳定的排序方法选择排序PART3将待排序数组分为有序和无序两组（初始情况下有序组为空，无序组是所有待排记录），每一趟（设第i趟）都从无序组中选择出排序码最小的记录,作为有序序列中的第i个记录。待到第n-1趟作完,待排序记录只剩下1个,就不用再选了。排序算法：选择排序基本思想直接选择排序的步骤1在一组对象V[i]～V[n-1]中选择具有最小排序码的对象2若它不是这组对象中的第一个对象,则将它与这组对象中的第一个对象对调在这组对象中剔除这个具有最小排序码的对象。在剩下的对象V[i+1]～V[n-1]中重复执行第1、2步,直到剩余对象只有一个为止325214925168ij25214925168kij25214925168两种选择排序的区别原始关键字一般选择排序直接选择排序2549252149251688214925162581649212581621252525214925168原始关键字第一趟排序第二趟排序第三趟排序第四趟排序第五趟排序25162125498kkkkkiiiiijjjjj直接选择排序的过程typedefintSortData;voidSelectSort(SortDataV[],intn){for(inti=0;i<n-1;i++){intk=i;//选择具有最小排序码的对象

for(intj=i+1;j<n;j++)if(V[j]<V[k])k=j;//当前具最小排序码的对象

if(k!=i)//对换到第i个位置

Swap(V[i],V[k]);} }直接选择排序算法直接选择排序算法分析1比较次数与对象的初始排列无关。有n个对象的序列,则第i趟排序的比较次数总是n-i次。总的排序码比较次数为：2对象的交换次数与对象序列的初始排列有关。当序列的初始状态是按其排序码从小到大有序时，,对象的交换次数为0，移动次数RMN=0，达到最少3最坏情况是每一趟都要进行交换，总的对象移动次数为RMN=3(n-1)4直接选择排序是一种不稳定的排序方法

快速排序PART4基本思想排序算法：快速排序任取序列中某个对象作为基准,将整个对象序列划分为左右两个子序列：

左侧子序列中所有对象都小于等于基准对象右侧子序列中所有对象都大于基准对象基准对象排在这两个子序列中间（这也是该对象最终应安放的位置）。分别对这两个子序列重复上述方法，直到所有的对象都排在相应位置上为止。基准对象也称为枢轴（或支点）记录。2521492516882116252549排序算法：快速排序25214925168567834854536hl918480lh快速排序的分隔算法intPartition(SqListA[],intlow,inthigh){X=A[low];//子表的第一个记录作基准对象

While(low<high){While(low<high&&A[high]>=X)--high;A[low]=A[high];//小于基准对象的移到区间的左侧

While(low<high&&A[low]<=X)++low;A[high]=A[low];//大于基准对象的移到区间的右侧

}A[low]=X;returnlow;}快速排序的分隔算法voidQuickSort(SqList&A,intlow,inthigh){//在序列lowhigh中递归地进行快速排序

if(low<high){ intloc=Partition(A,low,high);//分割

QuickSort(A,low,loc-1);//对左序列同样处理

QuickSort(A,loc+1,high);//对右序列同样处理

}}快速排序算法快速排序算法分析1算法partition利用序列第一个对象作为基准，将整个序列划分为左右两个子序列。只要是小于基准对象都移到序列左侧,最后基准对象安放到位,返回其位置2快速排序是递归的，需要有一个栈存放每层递归调用时的指针和参数3可以证明,函数quicksort的平均计算时间也是O(nlog2n)。实验结果表明:就平均计算时间而言,快速排序是所有内排序方法中最好的一个。4快速排序是一种不稳定的排序方法快速排序算法分析5快速排序的趟数取决于原始数据的排列方式。6如果每次划分对一个对象定位后,该对象的左侧子序列与右侧子序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,这是最理想的在最坏的情况,即待排序对象序列已经按其排序码从小到大排好序,或是一个逆序序列的情况下,每次划分只得到一个比上一次少一个对象的子序列。总的排序码比较次数将达7希尔排序PART5主讲人：希尔排序是插入排序的一种，又称缩小增量排序，为解决插入排序每次只能将数据移动一位，在数组较大且基本无序的情况下性能出现的恶化，所以引入希尔算法。排序算法：希尔排序问题提出先取一个小于n的步长d1把表中全部记录分成d1个组，所有距离为d1的倍数的记录放在同一个组中，在各组中进行直接插入排序。然后取第二个步长d2<d1,重复上述过程，直到所取到的di=1,即所有记录已放在同一组中，再进行直接插入排序。由于此时已经具有较好的局部有序性，故可以很快得到最终结果。但到目前为止，尚未求得一个最好的增量序列，希尔提出的方法是d1=⌈n/2⌉，di+1=⌈di/2⌉

,并且最后一个增量等于1。排序算法：希尔排序算法思想406549132750763827134938655013273850657697769797493865977613原始关键字第一趟排序5027d=4d=2第二趟排序d=1第三趟排序排序算法：希尔排序voidShellSort(ElemTypeA[],intn){for(d=n/2;d>=1;d=d/2)//步长变化

for(i=d+1;i<=n;++i)if(A[i]<A[i-d])//需将A[i]插入有序增量子表{

A[0]=A[i];for(j=i-d;j>0&&A[0]<A[j];j=j-d)A[j+d]=A[j];//记录后移，查找插入位置

A[j+d]=A[0];//插入}//if}希尔排序算法排序的时间复杂度02排序的稳定性01当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序，因此，希尔排序是一种不稳定的排序方法。O(n*log2n)希尔排序算法分析归并排序PART6归并排序有两种实现方法：自顶向下和自底向上。1.自顶向下的方法 

采用分治法进行自顶向下的算法设计，形式更为简洁，用递归，效率不如自底向上2.自底向上的方法 基本思想是：第1趟归并排序时，将待排序的数列A[1..n]看作是n个长度为1的有序子序列，将这些子序列两两归并形成⌈n/2⌉个有序子序列第2趟归并则是将第1趟归并所得到的⌈n/2⌉个有序的子序列两两归并，如此反复，直到最后得到一个长度为n的有序序列为止。

上述的每次归并操作，均是将两个有序的子序列合并成一个有序的子序列，故称其为"二路归并排序"。排序算法：归并排序493865977613原始关键字5027第一趟排序38496597137650273849659713277650第二趟排序1327384950659776第三趟排序排序算法：归并排序归并排序算法分析排序的时间复杂度02排序的稳定性01归并排序中归并的算法并不会将相同关键字的元素改变相对次序，所以归并排序是稳定的。O(n*log2n)基数排序PART7比如，扑克牌的花色基数为4，面值基数为13。在整理扑克牌时，既可以先按花色整理，也可以先按面值整理。按花色整理时，先按♠、♥、♣、♦的顺序分成4摞（分配），再按此顺序再叠放在一起（收集），然后按面值的顺序分成13摞（分配），再按此顺序叠放在一起（收集），如此进行二次分配和收集即可将扑克牌排列有序。如果反过来，先按面值整理，再按花色整理，也能将扑克牌排列有序，但和上面的排序结果是不一样的排序算法：基数排序多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：最高位优先法，简称MSD法和最低位优先，简称LSD法，我们现在看LSD法在数值排序中的应用对数字型或字符型的单关键字，可以看作由多个数位或多个字符构成的多关键字，此时可以采"分配-收集”的方法进行排序，这一过程称作基数排序法，其中每个数字或字符可能的取值个数称为基数。在“分配-收集”的过程中，为保证排序的稳定性，分配过程中装箱及收集过程中的连接必须按先进先出原则进行。排序算法：基数排序557322934314原始数据第一趟7665398165289727012345678965813914654328932276972773554381227393142765657697552839012345678965813914654328932276972773553914222728438165657376559397第二趟排序算法：基数排序前面说的几大排序算法，大部分时间复杂度都是O(n2)，也有部分排序算法时间复杂度是O(nlog2n)。而基数排序却能实现O(n)的时间复杂度。但基数排序的缺点是：首先是空间复杂度比较高，需要的额外开销大。排序有两个数组的空间开销，一个存放待排序数组，一个就是所谓的桶。初看起来，基数排序的执行效率似乎好的让人无法相信，所有要做的只是把原始数据项从数组复制到桶，然后再复制回去。如果有n个数据项，数据位数最多是d位，则有n*d次复制，复制的次数与数据项的个数成正比，即O(n)。这是我们看到的效率最高的排序算法。不幸的是，数据项越多，就需要更长的关键字，如果数据项增加10倍，那么关键字必须增加一位（多一轮排序）。复制的次数和数据项的个数与关键字长度成正比，可以认为关键字长度是N的对数。因此在大多数情况下，基数排序的执行效率倒退为O(N*logN)，和快速排序差不多。基数排序的算法分析堆排序PART8堆是一棵顺序存储的完全二叉树。其中：小顶堆：每个结点的关键字都不大于其孩子结点的关键字

大顶堆：每个结点的关键字都不小于其孩子结点的关键字排序算法：基数排序121191610732845堆排序的过程1首先将序列构建成为大顶堆这样满足了大顶堆那条性质：位于根节点的元素一定是当前序列的最大值2取出当前大顶堆的根节点，将其与序列末尾元素进行交换此时：序列末尾的元素为已排序的最大值；但位于根节点的值并不一定满足堆的性质3对交换后的n-1个序列元素进行调整，使其满足大顶堆的性质将剩余序列重新调整成堆4重复2-3步，直至堆中只有1个元素为止实现序列排序1234567891011121314732293435514286539816576972712345678910111213147322934355142865398165769727堆排序演示：堆的建立1234567891011121314978193656576284339552273142712345678910111213149781936565762843395522731427第1趟堆排序演示：第1趟1234567891011121314938176656573284339552227149712345678910111213149381766565732843395522271497第2趟堆排序演示：第2趟1234567891011121314816576436573281439552227939712345678910111213148165764365732814395522279397第3趟堆排序演示：第3趟1234567891011121314766573436527281439552281939712345678910111213147665734365272814395522819397第4趟堆排序演示：第1趟1234567891011121314736528436527221439557681939712345678910111213147365284365272214395576819397第5趟堆排序演示：第5趟1234567891011121314656528435527221439737681939712345678910111213146565284355272214397376819397第6趟堆排序演示：第6趟1234567891011121314655528433927221465737681939712345678910111213146555284339272214657376819397第7趟堆排序演示：第7趟1234567891011121314554328143927226565737681939712345678910111213145543281439272265657376819397第8趟堆排序演示：第8趟1234567891011121314433928142227556565737681939712345678910111213144339281422275565657376819397第9趟堆排序演示：第9趟1234567891011121314392728142243556565737681939712345678910111213143927281422435565657376819397第10趟堆排序演示：第10趟1234567891011121314282722143943556565737681939712345678910111213142827221439435565657376819397第11趟堆排序演示：第11趟1234567891011121314271422283943556565737681939712345678910111213142714222839