数据结构(C语言版) 胡学钢 07-排序.ppt

《数据结构(C语言版) 胡学钢 07-排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、11数据结构DataStructure主讲人：史君华合肥师范学院计算机科学与技术系1第七章排序（sorting）第七章排序7.1概述7.2插入排序7.3交换排序7.4选择排序7.5归并排序27.1概述排序——将数据表（a1,a2,……，an）调整为按关键字从小（大）到大（小）排列的过程。几个术语——增排序减排序单关键字/多关键字稳定排序：排序过程中关键字相同的元素的相对次序不变。不稳定排序：排序过程中关键字相同的元素的相对次序发生变化。内部排序：所有数据在内存外部排序：部分数据在内存，部分数据在外存（涉及到内外存的交换）37.1概述基本方法：插入方法交换方法选择方法归并方法基数方

2、法评价指标：时间：比较/移动/交换元素的次数空间：辅助空间47.2插入排序直接插入排序希尔排序57.2插入排序—直接插入排序基本思想：将待排序表看作左右两部分，其中左边为有序区，右边为无序区,整个排序过程就是将右边无序区中的元素逐个插入到左边的有序区中，以构成新的有序区。67.2插入排序—直接插入排序实例用直接插入排序算法对数据表A=(12,5,4,9,5)从小到大进行排序。（125495）解：5（495）12125（95）12541254（455）9（45）1259121291295for(i=2;i<=n;i++)A[i]插入到有序表中后移插入77.2插入排序—直接插入排序算

3、法(1)voidinsertsort(elementtypeA[]){for(i=2;i<=n;i++){temp=A[i];j=i-1;while((A[j].key>temp.key)&&(j>=1)){A[j+1]=A[j];j--;}A[j+1]=temp;}}A12345n…………a1a2a3a4a5an87.2插入排序—直接插入排序算法(2)voidinsertsort(elementtypeA[]){for(i=2;i<=n;i++){A[0]=A[i];j=i-1;while(A[j].key>A[0].key){A[j+1]=A[j];j--;}A[j+1]=A

4、[0];}}A12345n…………a1a2a3a4a5an97.2插入排序—直接插入排序算法分析稳定性：稳定排序。空间性能:需要一个记录的辅助存储空间。时间性能:与数据表初始状态有关。P200最好（有序）最坏（逆序）平均比较：n-1(n+2)(n-1)/2O(n2)移动：2(n-1)(n+4)(n-1)/2因而适用于基本有序，规模小的数据练习：P199思考：能不能在进行一次插入过程中保证至少有一个元素停留在最终的位置上呢？107.2插入排序—希尔排序基本思想：将待排序列划分为若干组，在每组内进行直接插入排序，以使整个序列基本有序，然后再对整个序列进行直接插入排序。分组方法：对给定

5、的一个步长d(d>0)，将下标相差为d的倍数的元素分在一组。d的取值依次为:d1=n/2,d2=d1/2,……，dk=1117.2插入排序—希尔排序实例1008201614710550789D1=10/21234567891010082016147105507897820169100105507814D2=10/478201691001055078147891420167850105100D3=10/87891416205078100105127.2插入排序—希尔排序算法及分析voidshell_sort(elementtypeA[]){d=n/2;while(d>=1){//通

6、过步长控制排序的执行过程for(i=d+1;i<=n;i++){//依次插入元素A[i]到本组前面的有序子表中x=A[i];j=i-d;//j指向当前空位置的同一组的前一个位置while(j>0&&x.key

7、循环到第x次，步长为1，即终止循环，所以n/(2x)=1；X=log2n147.3交换排序交换排序基本思想：两两比较待排序元素，发现倒序即交换。冒泡排序快速排序157.3交换排序—冒泡排序基本思想：从一端开始，逐个比较相邻的两个元素，发现倒序即交换。这里按从后往前（从下往上）逐个比较相邻元素。167.3交换排序—冒泡排序实例用冒泡排序算法对数据表A=(12,5,4,9,5)从小到大进行排序。解：9559445512412595124512594512125945912125外层循