c数据结构chapt10教程.ppt
文本预览下载声明
第十章 内部排序;10.1 基本概念;10.1 基本概念;10.1 基本概念;排序的时间开销:
排序的时间开销是衡量算法好坏的最重要的标志。排序的时间开销可用算法执行中的数据比较次数与数据移动次数来衡量。各节给出算法运行时间代价的大略估算一般都按平均情况进行估算。对于那些受对象关键码序列初始排列及对象个数影响较大的,需要按最好情况和最坏情况进行估算。
;静态排序:
排序的过程是对数据对象本身进行物理地重排,经过比较和判断,将对象移到合适的位置。这时,数据对象一般都存放在一个顺序的表中。
动态排序:
给每个对象增加一个链接指针,在排序的过程中不移动对象或传送数据,仅通过修改链接指针来改变对象之间的逻辑顺序,从而达到排序的目的。
;10.2 插入排序;;;16;25;void InsertSort(RecType R[],int n) /*对R[0..n-1]按递增有序进行直接插入排序*/
{ int i,j; RecType temp;
for (i=1;in;i++)
{ temp=R[i];
j=i-1; /*从右向左在有序区R[0..i-1]找R[i]的插入位置*/
while (j=0 temp.keyR[j].key)
{ R[j+1]=R[j]; /*将关键字大于R[i].key的记录后移*/
j--;
}
R[j+1]=temp; /*在j+1处插入R[i]*/
}
}; 例11.1 设待排序的表有10个记录,其关键字分别为{9,8,7,6,5,4,3,2,1,0}。说明采用直接插入排序方法进行排序的过程。 ;10.2 插入排序;10.2 插入排序;10.2 插入排序;10.2 插入排序;;10.2 插入排序;10.2 插入排序;;;;10.2 插入排序;10.2 插入排序;void ShellSort(RecType R[],int n) /*希尔排序算法*/
{ int i,j,d;RecType temp;
d=n/2; /*d取初值n/2*/
while (d0)
{ for (i=d;in;i++) /*将R[d..n-1]分别插入各组当前有序区*/
{ j=i-d;
while (j=0 R[j].keyR[j+d].key)
{ temp=R[j]; /*R[j]与R[j+d]交换*/
R[j]=R[j+d];R[j+d]=temp;
j=j-d;
}
}
d=d/2; /*递减增量d*/
}
}; 例11.2 设待排序的表有10个记录,其关键字分别为{9,8,7,6,5,4,3,2,1,0}。说明采用希尔排序方法进行排序的过程。;对特定的待排序对象序列,可以准确地估算关键码的比较次数和对象移动次数。
但想要弄清关键码比较次数和对象移动次数与增量选择之间的依赖关系,并给出完整的数学分析,还没有人能够做到。
Knuth利用大量的实验统计资料得出,当 n 很大时,关键码平均比较次数和对象平均移动次数大约在 n1.25 到 1.6n1.25 的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。
;交换排序 ( Exchange Sort );冒泡排序(Bubble Sorting)的基本思想是:
是通过对待排序序列从后向前(从下标较大的元素开始),依次比较相邻元素的排序码,若发现逆序则交换,使排序码较小的元素逐渐从后部移向前部(从下标较大的单元移向下标较小的单元),就象水底下的气泡一样逐渐向上冒。
因为排序的过程中,各元素不断接近自己的位置,如果一趟比较下来没有进行过交换,就说明序列有序,因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较。
;;;void BubbleSort(RecType R[],int n)
{ int i,j; RecType temp;
for (i=0;in-1;i++)
{ for (
显示全部