第8讲 排序技术 I.ppt

《第8讲 排序技术 I.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机软件技术基础第8讲排序技术I排序的基本概念排序：给定一组记录的集合{r1,r2,……,rn}，其相应的关键码分别为{k1,k2,……,kn}，排序是将这些记录排列成顺序为{rs1,rs2,……,rsn}的一个序列，使得相应的关键码满足ks1≤ks2≤……≤ksn（称为升序）或ks1≥ks2≥…≥ksn（称为降序）。排序的基本概念排序的稳定性：若记录序列中的任意两个记录Rx、Ry的关键字Kx=Ky；如果在排序之前和排序之后，它们的相对位置保持不变，则这种排序方法是稳定的，否则是不稳定的。排序的基本概念内排序和外排序：内排序：指

2、在排序的整个过程中，待排序的所有记录全部被放置在内存中外排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果排序算法性能评价对记录的排序所需关键字的比较次数；对记录的排序所需记录的移动次数；排序过程中所需的辅助空间。在下述讨论中约定：文件的存储结构采用顺序结构，即使用一维数组R[n]表示n个记录。排序算法分类排序方法插入类排序选择类排序交换类排序归并排序直接插入排序折半插入排序简单选择排序堆排序起泡排序多关键字排序分配类

3、排序链式基数排序基数排序的顺序表结构快速排序树形选择排序希尔排序插入类排序插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。也就是说，将待序列表分成左右两部分，左边为有序表（有序序列），右边为无序表（无序序列）。整个排序过程就是将右边无序表中的记录逐个插入到左边的有序表中，构成新的有序序列。根据不同的插入方法，插入排序算法主要包括：直接插入排序折半插入排序希尔排序直接插入排序基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当

4、位置，直到全部记录插入完成为止。设数组为a[0…n-1]。初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。i++并重复第二步直到i==n-1。排序完成。直接插入排序voidInsertSort(inta[],intn){inti,j,k;inttemp;for(i=1;i=0;j--)if(a[j]

5、适的位置if(j!=i-1){//将比a[i]大的数据向后移temp=a[i];for(k=i-1;k>j;k--)a[k+1]=a[k];//将a[i]放到正确位置上a[k+1]=temp;}}}直接插入排序voidlnsertSort(inta{],intn){inti，j,temp；for(i=1;i0 && temp

6、写，将搜索和数据后移这二个步骤合并。即每次a[i]先和前面一个数据a[i-1]比较，如果a[i]>a[i-1]说明a[0…i]也是有序的，无须调整。否则就令j=i-1,temp=a[i]。然后一边将数据a[j]向后移动一边向前搜索，当有数据a[j]a[j]，就交换a[j]和a[j-1]，再j--直到a[j-1]<=a[j]。这样也可以实现将一个新

7、数据新并入到有序区间。。voidInsertsort3(inta[],intn){inti,j;for(i=1;i=0&&a[j]>a[j+1];j--)Swap(a[j],a[j+1]);}直接插入排序-性能分析若设待排序的对象个数为n，则该算法的主程序执行n-1趟。关键码比较次数和对象移动次数与对象关键码的初始排列有关。最好情况下，排序前对象已经按关键码大小从小到大有序，每趟只需与前面的有序对象序列的最后一个对象的关键码比较1次，移动2次对象，总的关键码比较次数为n-1，对象移动次数为2(n

8、-1)。最坏情况下，第i趟时第i个对象必须与前面i个对象都做关键码比较，并且每做1次比较就要做1次数据移动。则总的关键码比较次数KCN和对象移动次数RMN分别为直接插入排序-性能分析若待排序对象序列中出现各种可能排列的概率相同，则可取