例如,n=8,数组R的八个元素分别为:17,3,30, 25,14,17,20,9。下面用图9-2给出希尔排序算法 y的执行过程。 初始状态,I=4 17330251417209 第一趟结果,I=2 14320917173025 第二趟结果,I=1 17920173025 第三趟结果 39141717202530 图9-2希尔排序算法的执行过程
例如，n=8，数组R的八个元素分别为：17，3，30， 25，14，17，20，9。下面用图9-2给出希尔排序算法 的执行过程。 初始状态，I=4 17 3 30 25 14 17 20 9 第二趟结果，I=1 14 3 17 9 20 17 30 25 第三趟结果 3 9 14 17 17 20 25 30 第一趟结果，I=2 14 3 20 9 17 17 30 25 图 9-2 希尔排序算法的执行过程
?由于希尔排序对个子序单独比较,在比f时进行元 希尔排序是不稳定的。例如,给定排序码3,4,2,2, 则希尔排序的结果变成2,2,3,4。 9.3交换排序 931冒泡排序 1.冒泡排序的基本思想 冒泡排序( Bubble Sorting)的基本思想是:是通过对 待排序序列从后向前(从下标较大的元素开始),依 次比较相邻元素的排序码,若发现逆序则交换,使排 序码较小的元素逐渐从后部移向前部(从下标较大的 单元移向下标较小的单元),就象水底下的气泡一样 逐渐向上冒。 因为排序的过程中,各元素不断接近自己的位置,如 果一趟比较下来没有进行过交换,就说明序列有序, 因此要在排序过程中设置一个标志fag判断元素是否进 行过交换。从而减少不必要的比较
由于希尔排序对每个子序列单独比较，在比较时进行元 素移动，有可能改变相同排序码元素的原始顺序，因此 希尔排序是不稳定的。例如，给定排序码3，4，2，2， 则希尔排序的结果变成2，2，3，4 。 9．3 交换排序 9.3.1 冒泡排序 1．冒泡排序的基本思想 冒泡排序（Bubble Sorting）的基本思想是：是通过对 待排序序列从后向前（从下标较大的元素开始），依 次比较相邻元素的排序码，若发现逆序则交换，使排 序码较小的元素逐渐从后部移向前部（从下标较大的 单元移向下标较小的单元），就象水底下的气泡一样 逐渐向上冒。 因为排序的过程中，各元素不断接近自己的位置，如 果一趟比较下来没有进行过交换，就说明序列有序， 因此要在排序过程中设置一个标志flag判断元素是否进 行过交换。从而减少不必要的比较
2.冒泡排序的算法实现 下面给出冒泡排序算法。 void Bubblesort(Elem Type ril, int n int flag:=1;∥当fag为0则停止排序 for (int i=; K<n; 1++) 作表示趟数,最多n-1趟 fag=0;/开始时元素未交换 for (int j=n-1; j>=1; j--) if(R[i]<R-1]){发生逆序 Elem Type t=R[i R[j]=R[j-1] R[j-1]=t;fag=1;}∥交换,并标记发生了交换 if(flag==Return;
2．冒泡排序的算法实现 下面给出冒泡排序算法。 void Bubblesort(ElemType R[],int n) { int flag=1; //当flag为0则停止排序 for (int i=1; i<n; i++) { //i表示趟数，最多n-1趟 flag=0;//开始时元素未交换 for (int j=n-1; j>=i; j--) if (R[j]<R[j-1]) { //发生逆序 ElemType t=R[j]; R[j]=R[j-1]; R[j-1]=t;flag=1; } //交换，并标记发生了交换 if(flag==0)return; }}
例如,n=6,数组R的六个排序码分别为:17,3,25,14, x20,9。下面用图9-3给出冒泡排序算法的执行过程 RIOT R[2] R[3] R[4] R[5] 初始状态(17 20 第一趟排序 (17 9 25 14 20) 第二趟排序 (17 第三趟排序3 (17 20 25) 第四趟排序3 14 17 20 25 图9-3冒泡排序示例
例如，n=6，数组R的六个排序码分别为：17，3，25，14， 20，9。下面用图9-3给出冒泡排序算法的执行过程。 图 9-3 冒泡排序示例 R[0] R[1] R[2] R[3] R[4] R[5] 第一趟排序 3 (17 9 25 14 20) 第二趟排序 3 9 (17 14 25 20) 第三趟排序 3 9 14 (17 20 25) 第四趟排序 3 9 14 17 20 25 初始状态 （17 3 25 14 20 9)