9.2.3希尔排序1.希尔排序的基本思想希尔排序（ShellSort）又称为“缩小增量排序”。是1959年由D.L.Shell提出来的。该方法的基本思想是：先将整个待排元素序列分割成若于个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。3.希尔排序的效率分析虽然我们给出的算法是三层循环，最外层循环为log,n数量级，中间的for循环是n数量级的，内循环远远低于n数量级，因为当分组较多时，组内元素较少：此循环次数少；当分组较少时，组内元素增多，但已接近有序，循环次数并不增加。因此，希尔排序的时间复杂性在0（nlog,n）和O（n2）之间，大致为O（nl.3）
9.2.3希尔排序 1．希尔排序的基本思想 希尔排序（Shell Sort）又称为“缩小增量排序” 。是 1959年由D.L.Shell提出来的。该方法的基本思想是：先 将整个待排元素序列分割成若干个子序列（由相隔某个 “增量”的元素组成的）分别进行直接插入排序，待整 个序列中的元素基本有序（增量足够小）时，再对全体 元素进行一次直接插入排序。因为直接插入排序在元素 基本有序的情况下（接近最好情况），效率是很高的， 因此希尔排序在时间效率上比前两种方法有较大提高。 3．希尔排序的效率分析 虽然我们给出的算法是三层循环，最外层循环为log2 n数 量级，中间的for循环是n数量级的，内循环远远低于n数 量级，因为当分组较多时，组内元素较少；此循环次数 少；当分组较少时，组内元素增多，但已接近有序，循 环次数并不增加。因此，希尔排序的时间复杂性在O （nlog2 n）和O（n 2 ）之间，大致为O（n 1. 3）
例如，n=8，数组R的八个元素分别为：17，3，30,25，14，17，20，9。下面用图9-2给出希尔排序算法的执行过程。17330251420917初始状态，I-4/20917302514317第一趟结果，I-291720173025143第二趟结果，I-139172025141730第三趟结果图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 希尔排序算法的执行过程
由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同排序码元素的原始顺序，因此希尔排序是不稳定的。例如，给定排序码3，4，2，2，则希尔排序的结果变成2，2，3，4°9.3交换排序9.3.1冒泡排序1：冒泡排序的基本思想冒泡排序（BubbleSorting）的基本思想是：是通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较大的元素逐渐从前部移向后部（从下标较小的单元移向下标较大的单元），关键字小的记录就象水底下的气泡一样逐渐向上冒，而关键字大的记录往下沉。因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag判断元素是否进行过交换。从而减少不必要的比较
由于希尔排序对每个子序列单独比较，在比较时进行元 素移动，有可能改变相同排序码元素的原始顺序，因此 希尔排序是不稳定的。例如，给定排序码3，4，2，2， 则希尔排序的结果变成2，2，3，4 。 9．3 交换排序 9.3.1 冒泡排序 1．冒泡排序的基本思想 冒泡排序（Bubble Sorting）的基本思想是：是通过对待排 序序列从前向后（从下标较小的元素开始），依次比较相邻 元素的排序码，若发现逆序则交换，使排序码较大的元素逐 渐从前部移向后部（从下标较小的单元移向下标较大的单 元），关键字小的记录就象水底下的气泡一样逐渐向上冒， 而关键字大的记录往下沉。 因为排序的过程中，各元素不断接近自己的位置，如果一趟 比较下来没有进行过交换，就说明序列有序，因此要在排序 过程中设置一个标志flag判断元素是否进行过交换。从而减 少不必要的比较
2．冒泡排序的算法实现下面给出冒泡排序算法void Bubblesort(sqlist L)( flag=l;/当flag为0则停止排序for (i-L.length; i>l; i--)（//i表示趟数，最多n-1趟flag=0;//开始时元素未交换for (j=l; j<i; j++)if (L.r[i]<L.r[i+1) { t=-L.ri];L.r[i]-L.r[i+1];L.r[j+1]=t;flag=l;}//交换，并标记发生了交换if(flag==0) return;
2．冒泡排序的算法实现 下面给出冒泡排序算法。 void Bubblesort(sqlist L) { flag=1; //当flag为0则停止排序 for ( i=L.length; i>1; i-) { //i表示趟数，最多n-1趟 flag=0;//开始时元素未交换 for ( j=1; j<i; j++) if (L.r[j]<L.r[j+1]) { t=L.r[j]; L.r[j]=L.r[j+1]; L.r[j+1]=t;flag=1; } //交换，并标记发生了交换 if(flag==0) return; }}
例如，n=6，数组R的六个排序码分别为：17，3，25，1420，9。下面用图9-3给出冒泡排序算法的执行过程R[1]R[0]R[2]R[3]R[4]R[5](1739)初始状态2514201714209)25(3第一趟排序25(39)20第二趟排序141717149)2025第三趟排序(39325第四趟排序141720图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 14 20 9) 25 第二趟排序 ( 3 14 17 9) 20 25 第三趟排序 ( 3 14 9 ) 17 20 25 第四趟排序 3 9 14 17 20 25 初始状态 （17 3 25 14 20 9)