还剩7页未读,继续阅读
文本内容:
一、插入排序基本思想每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,序;使数列依然有直到待排序数据元素全部插入完为止排序过程【示例】初始关键字对按递增序进行插入排序是监视哨1挨次插入2查找的插入位置3将大于的元素后移4插入5
二、选择排序基本思想每一趟从待排序的数据元素中选出最小(或者最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完排序过程【示例】初始关键字第一趟排序后[第二趟排序后[第三趟排序后第四趟排序后第五趟排序后第六趟排序后第七趟排序后最后排序结果16对进行直接选择排序17做趟选择排序18在当前无序区中选最小的元素22232425交换和262728
三、冒泡排序基本思想两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止排序过程设想被排序的数组[]垂直竖立,将每一个数据元素看做有分量的气泡,根据轻气泡不能在重气泡之下的原则,从下往上扫描数组,凡扫描到违反本原则的轻气泡,就使其向上飘荡,如此反复进行,直至最后任何两个气泡都是轻者在上,重者在下为止【示例】3031从下往上扫描的起泡排序3233做趟排序3435置未排序的标志3637从底部往上扫描3839交换元素404142本趟排序中未发生交换,则终止算法44434546复制代码
四、快速排序()基本思想在当前无序区中任取一个数据元素作为比较的基准不妨记为,用此基准将当前无序区划分为摆布两个较小的无序区和,且左边的无序子区中数据元素均小于等于基准元素,右边的无序子区中数据元素均大于等于基准元素,而基准则位于最终排序的位置上,即,当和均非SS空时,分别对它们进行上述的划分过程,直至所有无序子区中的数据元素均已排序为止排序过程【示例】初始关键字]第一次交换后[]第二次交换后[]向左扫描,位置不变,第三次交换后[]向右扫描,位置不变,第四次交换后[]向左扫描[](一次划分过程)初始关键字一趟排序之后[]二趟排序之后[][][][]三趟排序之后[]最后的排序结果各趟排序之后的状态4748做划分,给以出本次划分后已被定位的基准元素的位置对无序区4950初始化,为基准51525354从右向左扫描,查找第个小于的元素55己找到〈565758相当于交换和59606162从左向右扫描,查找第个大于的元素636465已找到66相当于交换和676869基准已被最终定位71〃对快速排序〃72Procedure QuickSortVar R:FileType;S,T:Integer;R[S..T]73Begin〃当为空或者惟独一个元素是无需排序〃74lfST ThenR[S..T]75begin〃对做划分〃76PartionR,S,T;R[S..T]〃递归处理左区间77QuickSortR,S,l・1;R[S,I-1]//〃递归处理右区间78QuickSortR,1+1,T;R[I+
1..T]//79end;80End;//Quicksort//复制代码
五、堆排序基本思想堆排序是一树形选择排序,在排序过程中,将看成是一颗彻底二叉树的顺序存储结堆的定义个元素的序列称为堆,当且仅当该序列满足特性:构,利用彻底二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素堆实质上是满足如下性质的彻底二叉树树中任一非叶子结点的关键字均大于等于其孩子结点的关键字例如序列就是一个堆,它对应的彻底二叉树如上图所示这种堆中根结点(称为堆顶)的关键字最小,我们把它称为小根堆反之,若彻底二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字,则称之为大根堆排序过程:堆排序正是利用小根堆(或者大根堆)来选取当前无序区中关键字小(或者最大)的记录实现排序的我们不妨利用大根堆来排序每一趟排序的基本操作是将当前无序区调整为一个大根堆,选取关键字最大的堆顶记录,将它和无序区中的最后一个记录交换这样,正好和直接选择排序相反,有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区O【不例】对关键字序列,,,,,,,建堆在数组中调用,使得以它为彻底二叉树构成堆事先已知其左、右子树时均是堆81若是的左孩子82若当前被调整结点有左孩子83令指向关键字较大的右孩子84指向的左、右孩子中关键字较大者85孩子结点关键字较大86将换到双亲位置上87继续以为当前被调整结点往下层调整88调整完毕,退出循环89将最初被调整的结点放入正确位置90100复制代码〃对进行堆排序〃101Procedure HeapSort(VarR:FileType);R[
1..N]102Begin〃建立初始堆〃103For I:=N DivDownto1Do104进行趟排序//105For I:=N Downto2do//N-1106begin〃将当前堆顶记录和堆中最后一个记录交换//107T:=R
[1];R
[1]:=R;R:=T;将重成堆〃108SiftR,109end110End;//HeapSort//复制代码
六、几种排序算法的比较和选择选取排序方法需要考虑的因素待排序的元素数目;元素本身信息量的大小;关键字的结构及其分布情况;语言工具的条件,辅助空间的大小等小结若较小,则可以采用直接插入排序或者直接选择排序由于直接插入排序所需的记录挪移操作较直接选择排序多,于是当记录本身信息量较大时,用直接选择排序较好若文件的初始状态已按关键字基本有序,则选用直接插入或者冒泡排序为宜若较大,则应采用时间复杂度为的排序方法快速排序、堆排序或者归并排序快速排序是目前基于比较的内部排序法中被认为是最好的方法在基于比较排序方法中,每次比较两个关键字的大小之后,仅仅浮现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程,由此可以证明当文件的个关键字随机分布时,任何借助于比较的排序算法,至少需要的时间这句话很重要它告诉我们自己写的算法是有改进到最优固然没有必要向来追求最优当记录本身信息量较大时,为避免耗费大量时间挪移记录,可以用链表作为存储结构。