排序的基本概念

《排序的基本概念》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、9．1排序的基本概念9．2插入排序9．3交换排序9．4选择排序9．5归并排序9．6基数排序9．7各种排序方法的比较排序是数据处理中经常使用的一种很重要的运算第九章排序19.1排序的基本概念如果没有特别说明，本章中的待排序数据元素都是存储在数组中的一组记录。数组中的每一个记录都有一个域称为排序关键字，简称为关键字。这个关键字可以是任何一种可比的有序数据类型，例如，整数、实数、字符、字符串、或者别的更复杂的类型。2给定一组记录R1，R2，…，Rn，其关键字分别为k1,k2,…,kn，排序就是将这些记录排成顺序为Rs1

2、，Rs2，…，Rsn的一个序列S，该序列满足条件ks1≤ks2≤…≤ksn。换句话说，排序就是按照关键字值重排一组记录，使记录的关键字值具有不减的次序。9.1排序的基本概念3根据定义，排序中的记录可以具有相同的关键字值。当对具有相同关键字值的多个记录来说，如果一种排序方法不改变这些记录的相对顺序，则称所用的排序方法是稳定的，否则是不稳定的。9.1排序的基本概念4如果排序过程中，待排序元素是存储在计算机随机存储器中，这种排序称为内排序。如果待排序元素太多，以至于内存中存放不下，可借助于外存，排序过程中需要不断地进行

3、内存和外存之间的元素交换，这种排序称为外排序。本章只讨论内排序。9.1排序的基本概念5注意:本章在讨论各种内排序算法时，假定n个待排序记录存于一维数组a中，记录类型为ELEMTYPE，而且我们也假设比较关键字的运算符已经有了定义。另外我们认为对于任何一种记录都可以找到一个取得它的关键字函数，记为key。算法中所用到函数swap用于交换两个记录的内容。69．2插入排序9．2．1直接插入排序9．2．2折半插入排序9．2．3希尔(shell)排序79．2．1直接插入排序直接插入排序是一种最简单的排序方法。对n个待排序的

4、记录来说，直接插入排序首先取出第二个记录，根据其关键字值将其插入到已排好序的记录中（第一个记录），接着处理第3个记录，将其插入到前面已排好序的两个记录的合适位置，依此类推，直到最后一个记录，将其与前面已排好序的n-1个记录进行比较，并将其插入到正确的位置。下面是直接插入排序的C语言实现。8算法9.1voidinsertsort(ElemTypea[],intn){inti,j,temp;for(i=1;i=0)&&(key(a[j])>key(te

5、mp))){a[j+1]=a[j];j--;}a[j+1]=temp;}}9．2．1直接插入排序9考虑insertsort处理第i个记录的情况，a[0],a[1],…,a[i-1]已经是排好序的记录序列。取出第i个记录将其暂存于变量temp中，temp依此与第j（j=i-1,…,0）个记录比较，当temp的关键字值小于记录a[j]的关键字值时，就把记录a[j]后移一个位置，temp接着同前一个记录比较，直到遇到一个关键字值比temp小或者temp与它相等的记录时，本次插入完成，因为再往前记录的关键字值一定都比它小

6、了。数组的第j+1位置即为第i个记录的位置。直接插入排序过程如图9.1所示。9．2．1直接插入排序104630829056179515i=13046829056179515i=23046829056179515i=33046829056179515i=43046568290179515i=51730465682909515i=61730465682909515i=71517304656829095图9.1直接插入排序说明9．2．1直接插入排序11直接插入排序由两个嵌套的循环组成。for循环总共执行n-1次。whi

7、le循环执行次数依赖于在第i个记录前的i-1个记录中有多少个记录的关键字值大于第i个记录的关键字值。最差的情况是如果数组中记录是逆序的，每个记录都必须移动到数组的顶端。这时while循环共做i-1次比较。9．2．1直接插入排序129．2．2折半插入排序前面介绍的直接插入排序算法中，第i次插入时，为了寻找第i个记录的插入位置，我们需要不断地与0~i-1的记录进行顺序比较与交换。回顾8.2.2节介绍的折半查找算法，其性能优于顺序查找。因此，我们不妨利用折半查找方法来确定第i个记录的插入位置。如此进行的插入排序称为折半

8、插入排序。其算法如下：13算法9.2voidbinsort(ELEMTYPEa[],intn){inti,j,l,h,m,temp;for(i=1;il;j--)a[j]=a