[理学]第10章 排序.ppt

2009年10月29日 排序算法的性能指标 1. 时间开销： ⑴比较：关键码之间的比较； ⑵移动：记录从一个位置移动到另一个位置。 2. 空间开销： 辅助存储空间 3. 算法的稳定性 void shellInsert9sqlist L,int dk) { for(i=dk+1;i=L.length;++i) if (LT(L.r[i].key,L,r[i-dk].key) { L.r[0]=L.r[i]; for(j=i-dk;j0 LT(L.r[0].key,L.r[j].key);j-=dk) L.r[j+dk]=L.r[j]; L.r[j+dk]=L.r[0]; } } void shellsort (sqlist L,int dlta[],int t) { for(k=0;kt;++k) shellInsert(L,dlta[k]); } 冒泡排序需解决的关键问题 ⑴ 在一趟冒泡排序中，若有多个记录位于最终位置，应如何记录？ ⑵ 如何确定冒泡排序的范围，使得已经位于最终位置的记录不参与下一趟排序？ ⑶ 如何判别冒泡排序的结束？ 问题1：如何记载一趟排序过程中交换的多个记录？ 解决方法： 设变量exchange记录是否发生交换。 问题1：如何记载一趟排序过程中交换的多个记录？ 解决方法： 设变量exchange记载记录交换的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次交换的位置，且从此位置以后的所有记录均已经有序。 问题1：如何记载一趟排序过程中交换的多个记录？ 解决方法： 设变量exchange记载记录交换的位置，则一趟排序后，exchange记载的一定是这一趟排序中记录的最后一次交换的位置，且从此位置以后的所有记录均已经有序。 问题2：如何确定冒泡排序的范围？ 解决方法： 设bound位置的记录是无序区的最后一个记录，则每趟冒泡排序的范围是r[1] ~ r[bound]。 在一趟排序后，从exchange位置之后的记录一定是有序的，所以bound=exchange。 问题3：如何判别冒泡排序的结束？ 解决方法： 在每一趟冒泡排序之前，令exchange的初值为0，在以后的排序过程中，只要有记录交换，exchange的值就会大于0。 这样，在一趟比较完毕，就可以通过exchange的值是否为0来判别是否有记录交换，从而判别整个冒泡排序的结束。 问题1：如何选择轴值？ 选择轴值的方法： 1.使用第一个记录的关键码； 2.选取序列中间记录的关键码； 3.比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置； 4.随机选取轴值。 选取不同轴值的效果： 决定两个子序列的长度，子序列的长度最好相等。 简单选择排序 简单选择排序的主要思想是： 第i 趟在n-i+1（i=1,2,…,n-1）个记录中选取关键码最小的记录作为有序序列中的第i个记录。 需解决的关键问题? ⑴如何在待排序序列中选出关键码最小的记录？ ⑵如何确定待排序序列中关键码最小的记录在有序序列中的位置？ 问题1：如何在无序区中选出关键码最小的记录？ 解决方法： 设置一个整型变量k，用于记录在一趟比较的过程中关键码最小的记录位置。 问题1：如何在无序区中选出关键码最小的记录？ 解决方法： 设置一个整型变量k，用于记录在一趟比较的过程中关键码最小的记录位置。 问题2：如何确定最小记录的最终位置？ 解决方法： 第i趟简单选择排序的待排序区间是r[i] ~ r[n]，则r[i]是无序区第一个记录，所以，将index所记载的关键码最小的记录与r[i]交换。 3、直接选择排序算法描述 void selectsort（recdtype R[ ]，int n） { int i，j，m； recdtype temp； for( i=0；in-1 ; i ++) / * 做n-1趟选择排序*/ { m = i; /* 用m保存当前得到的最小关键字记录的下标，初值为i*/  for( j= i+1；j=n-1; j++) if( R[j].key R[m].key) m = j; /*记下最小关键字记录的位置*/ if(m!= I)/*交换R[i]和R[m]*/ { temp = R[i]； R[i]