《12程序设计算法1》由会员分享，可在线阅读，更多相关《12程序设计算法1（15页珍藏版）》请在金锄头文库上搜索。
1、之排序算法排序算法排序算法排序就是将排序就是将杂乱无章的数据元素，通乱无章的数据元素，通过一定一定的方法按关的方法按关键字字顺序排列的序排列的过程。程。一、一、 简单排序排序二、快速排序二、快速排序三、希三、希尔排序排序四、堆排序与二叉四、堆排序与二叉树排序排序五、五、归并排序并排序六、六、 线形排序形排序七、各种排序算法的比七、各种排序算法的比较一、一、 简单排序排序1.选择排序选择排序的基本思想是：对待排序的记录序列进行n-1遍的处理，第1遍处理是将L1.n中最小者与L1交换位置，第2遍处理是将L2.n中最小者与L2交换位置，.，第i遍处理是将Li.n中最小者与Li交换位置。这样，经过i遍
2、处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。见见ex12_1.pas一、一、 简单排序排序2.插入排序3.冒泡排序又称交换排序其基本思想是:对待排序的记录的关键字进行两两比较,如发现两个记录是反序的,则进行交换,直到无反序的记录为止。见见ex12_2.pas二、快速排序二、快速排序快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处理直到每一个待处理的序列的长度为1,处理结束.三、希三、希尔排序排序基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序或冒泡排序。序列分割方法：将相隔某个增量h的元素构
3、成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序或冒泡排序，排序就完成。增量序列一般采用：d1=ndiv2,di=di-1div2；i=2,3,4.其中n为待排序序列的长度。96827n=5d=272869n=5d=226789n=5d=1四、堆排序与二叉四、堆排序与二叉树排序排序 1.堆排序堆：设有数据元素的集合（R1,R2,R3,.Rn)它们是一棵顺序二叉树的结点且有Ri=R2i和Ri=)堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。堆排序的思想是：1）建初始堆（将结点n/2,n/2-1,.3,2,1分别调成堆）2）当未排
4、序完时输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。四、堆排序与二叉四、堆排序与二叉树排序排序2.二叉树排序每一个参加排列的数据对应二叉树的一个结点，且任一结点如果有左（右）子树，则左（右）子树各结点的数据必须小（大）于该结点的数据。中序遍历排序二叉树即得排序结果。五、归并排序归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge).归并排序就是n长度为1的子序列,两两归并最后变为有序的序列。六、线形排序以上我们讨论的算法均是基于比较的排序算法，在排序算法中有基于数字本身的算法：计数、桶、基数排序。1.计数排序基本思想是对于序列中的每一元素x,确
5、定序列中小于x的元素的个数。fori:=1tondoread(ai);fori:=1tomdoci:=0;fori:=1tondocai:=cai+1;六、线形排序2.桶排序桶排序的思想是等待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值,顺序输出各桶的值,将得到有序的序列。fori:=1tondobeginread(k);bk:=bk+1;end;fori:=0to100dowhilebi0dobeginwrite(i:6);bi:=bi-1end;六、线形排序3.基数排序基本思想是对n个元素依次按k,k-1,.1位上的数字进行桶排序。七、各种排序算法
6、的比七、各种排序算法的比较1.稳定性比较插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的；选择排序、希尔排序、快速排序、堆排序是不稳定的2.时间复杂性比较插入排序、冒泡排序、选择排序的时间复杂性为O(n2)其它非线形排序的时间复杂性为O(nlog2n)线形排序的时间复杂性为O(n);3.辅助空间的比较线形排序、二路归并排序的辅助空间为O(n),其它排序的辅助空间为O(1);试题：将5个数的序列排序，不论原先的顺序如何，最少都可以通过（）次比较，完成从小到大的排序。A.6B.7C.8D.9E.10.对给定的整数序列(54,73,21,35,67,78,63,24,89)进行从小到大的排序时,采用快速排序的第一趟扫描的结果是()A)(24,21,35,54,67,78,63,73,89)B)(24,35,21,54,67,78,63,73,89)C)(24,21,35,54,67,63,73,78,89)D)(21,24,35,54,63,67,73,78,89)E)(24,21,35,54,67,63,73,78,89)下列关于排序说法正确的是().A)插入排序、冒泡排序是稳定的B)选择排序的时间复杂性为O(n2)C)选择排序、希尔排序、快速排序、堆排序是不稳定的D)希尔排序、快速排序、堆排序的时间复杂性为O(nlog2n)E)快速排序是速度最快的排序
