《数据结构》第10章：排序.ppt

《《数据结构》第10章：排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、王钢主编清华大学出版社数据结构第10章排序排序的基本概念常用内部排序外部排序直接插入排序直接插入排序是插入排序中最简单的排序方法，假设排序表中有n个记录，存储在一维数组R[n]中。直接插入排序的基本思想为：把待排记录按排序码大小插入到已排好序的有序表中。[算法10.1]直接插入排序算法voidD_InsertSort(ElemtypeR[],intn){//对记录序列R[1..n]作直接插入排序inti;for(i=2;i<=n;++i)if(R[i].key

2、-1;R[0].key

3、/对记录序列R[1..n]作折半插入排序inti,low,high,mid;for(i=2;i=high+1;--j)//high+1为插入位置R[j+1]=R[j];//记录后移R[high+1]=R[0]

4、;//插入记录}}希尔排序(又称缩小增量排序)希尔排序(Shell’ssort)又称缩小增量排序，是1959年由D.L.Shell提出来的。希尔排序可以理解为对直接插入排序的一种改进。直接插入排序是从第二个元素开始比较的，循环起始条件为i=2，可以将i=2写成i=1+1，将第一个1用dk代替，即循环初始条件为i=dk+1，dk是一个希尔增量序列，一般可取做dk={5,3,1}(当然也可以取其他素数序列，但最后一个必为1)，从第i个记录开始，间隔dk的记录为一组，每次用第i个关键字与第I–dk个关键字进行比较后做插入排序。例10.2已知排序表关键字序列为：49,38,65,97,7

5、6,13,27,49,55,04,则希尔排序的排序过程如图10.2所示。[算法10.3]希尔排序算法voidShellInsert(ElemtypeR[],intdk){//对R[1……..n]进行一趟插入排序，dk为步长因子inti,j;for(i=dk+1;i<=n;i++)//小于1时需将R[i]插入有序表if(R[i].key0&&R[0].key

6、llSort(DataTypeR[],intn,intd[],intt){//按增量序列[0，1…….t-1]对顺序表R[1…..n]作希尔排序for(k=0;k

7、，下一遍只检查比较到此为止，到所有记录都不发生下沉时，整个过程结束。所以n个元素实施冒泡排序，共需要n–1趟排序，每趟需要n–i次比较。[算法10.4]冒泡排序的基本算法voidBubble_Sort(ElemtypeR[],intn){inti,j,flag;for(i=1;iR[j+1].key){R[0]=R[j];//R[0]作为交换的中