《内部排序》PPT课件

《《内部排序》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter10排序排序的基本概念直接插入排序起泡排序简单选择排序快速排序堆排序6.1基本概念排序排序在计算机程序设计中有着非常重要的地位，许多具体应用要求对数据进行排序，而许多复杂的算法也要求以排序为基础。排序排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。数据表(datalist):它是待排序数据对象的有限集合。主关键字(key):数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据，称为关键字。也称为排序码。排序有关排序的几个基本问题稳定与不

2、稳定内部排序与外部排序（本章只关注内部排序）性能的衡量排序方法的分类按照排序思想插入排序交换排序选择排序归并排序基数排序按照时间复杂度简单排序先进排序其他6.2直接插入排序直接插入排序基本思想：如果要向一个已经排序的顺序表中插入元素且保持表的有序性，则只需先依次比较，找到该元素的位置，然后移动元素进行插入即可。时间复杂度是O(n).基于这一思想，如果要对一个表进行排序，则可以将表看作两个部分，前N个元素已经排好序，再将第N+1个元素插入到前N个元素中。从N=0开始重复这个过程，直到N=L。直接插入排序

3、012345tempi=1i=2012345temp2108254925*162125084925*16252125084925*162125084925*16492125084925*16i=32125084925*1625*2125084925*16直接插入排序i=4i=52125084925*1616162125084925*162125084925*162125084925*1608直接插入排序直接插入排序的算法typedefintSortData;voidInsertSort(SortDat

4、aV[],intn){//按非递减顺序对表进行排序SortDatatemp;inti,j;for(i=1;i0;j--)//从后向前顺序比较if(temp

5、简化，因此折半插入排序仍然保值O(n^2)的时间复杂度。链表上的插入排序链表上的插入排序仍然无法回避比较的过程，但是无需移动元素，从总体上看比顺序表上插入排序的性能好一些。6.3起泡排序起泡排序基本思想：基于两两比较的思想，对于N个元素，如果从第一个开始两两比较，将较小（较大）的一个交换到后面，则经过N-1次比较之后，最小（最大）的元素就被移动到最后一个位置。基于这一思想，如果要对一个表进行排序，则可以先对全部元素进行两两比较，将最小（最大）的元素移动到最后，再对前N-1元素重复过程，再对前N-2个…

6、…直到所有的元素都排好序。起泡排序210825492516214925251608214925251608214925251608214925251608初始关键字第一趟排序第四趟排序第二趟排序第三趟排序214925251608第五趟排序起泡排序起泡排序的基本算法typedefintSortData;voidBubbleSort(SortDataa[],intn){for(inti=0;ia[j+1]){inttemp=0

7、;temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}起泡排序最多做n-1趟起泡就能把所有对象排好序。在对象的初始排列已经按排序码从小到大排好序时,此算法只执行一趟起泡,做n-1次排序码比较,不移动对象。这是最好的情形。时间复杂度是O(n^2)。起泡排序起泡排序的改进：在上面的程序中，如果序列经过很少几次循环就已经完成了排序，程序仍然会执行N-1次循环，造成多次循环做无用功。例如对于下面的序列，实际上经过一次循环就已经有序了。210825492516起泡排序对于这种情况，我们可

8、以设置一个标志，如果一次循环发生数据交换，则令标志为1；如果一次循环不发生数据交换，则令标志为0，当发现标志为0时，就意味着已经排序完成了。起泡排序typedefintSortData;voidBubbleSort(SortDataV[],intn){inti=1;intexchange=1;while(i=i;j--)if(V[j-1]>V[j])