例如,n=6,数组R的六个排序码分别为:17,3,25,14, 20,9。它的直接插入排序的执行过程如图所示。 初始状态17 25 20 第1次插入3 20 第2次插入3 17 25 14 9 第3次插入 17 20 第4次插入3 14 17 20 25 第5次插入
0 1 2 3 4 5 初始状态 17 3 25 14 20 9 第1次插入 3 17 25 14 20 9 第2次插入 3 17 25 14 20 9 第3次插入 3 14 17 25 20 9 第4次插入 3 14 17 20 25 9 第5次插入 3 9 14 17 20 25 例如，n=6，数组R的六个排序码分别为：17，3，25，14， 20，9。它的直接插入排序的执行过程如图所示
2.直接插入的算法实现 void insert sort( rectype RU) /待排序元素存于数组R,数据从R起,R0有特别用处。 i int i, j for(i=2;i<n;i+)插入R2]Rn-1 {R[0=R[i; ∥把待排序元素暂存于R[] whle(R|0key< RI.key)∥顺序比较和移动 iRIj+l=riil R[i+1=R[0;
void insert_sort ( rectype R[] ) //待排序元素存于数组R[]，数据从R[1]起，R[0]有特别用处。 { int i, j; for ( i=2; i<n; i++) { R[0] = R[i]; j=i-1; while ( R[0].key < R[j].key ) { R[j+1] = R[j]; j - - ; } R[j+1] = R[0]; } } 2．直接插入的算法实现 //插入R[2]…R[n-1] //把待排序元素暂存于R[0] // 顺序比较和移动
R]的作用:暂存R];监视是否j<1 void insert-sort2 (rectype RI D int I rectype t, //t为中间变量 for(i=2; isn; i++) {x=R[j;//把待排序元素赋给x while((>=0)&&(x key<Ri.key)) {R[i+1=R[j; j--;}//顺序比较和移动 R[i+1=x;
R[0]的作用：暂存R[i]；监视是否j<1 void insert-sort2 (rectype R[ ]) { int i, j; rectype t; // t 为中间变量 for ( i=2; i<n; i++) { x=R[i]; //把待排序元素赋给x j=i-1; while ((j>=0)&& ( x.key<R[j].key)) { R[j+1]=R[j]; j - -; } // 顺序比较和移动 R[j+1]=x; } }
3.直接插入排序的效率分析 ●从空间来看,它只需要一个元素的辅助空间,用于元素的位 置交换。 从时问分析, 首先外层循环要进行n-次插入, 每次插入最少比较一次(正序),移动两次; 最多比较次,移动+2次(逆序)(i=1,2,…,n-1)。 ●因此,直接插入排序的时间复杂度为O(n2)。 ●直接插入算法的元素移动是顺序的,该方法是稳定的
3．直接插入排序的效率分析 从空间来看，它只需要一个元素的辅助空间，用于元素的位 置交换。 从时间分析， 首先外层循环要进行n-1次插入， 每次插入最少比较一次（正序），移动两次； 最多比较i次，移动i＋2次（逆序）（i=1，2，…，n-1）。 因此，直接插入排序的时间复杂度为O（n 2）。 直接插入算法的元素移动是顺序的，该方法是稳定的
922希尔排序 希尔排序的基本思想 希尔排序,又称为“缩小增量排序”。是1959年由D.L.Shl 提出来的。 该方法的基本思想是 先将整个待排元素序列分割成若干个子序列(由相隔某 个“增量”的元素组成的)分别进行直接插入排序 待整个序列中的元素基本有序(增量足够小)时,再对 全体元素进行一次直接插入排序 因为直接插入排序在元素基本有序的情况下(接近最好情 况),效率是很高的,因此希尔排序在时间效率上有较大 提高
9.2.2希尔排序 1．希尔排序的基本思想 • 希尔排序, 又称为“缩小增量排序” 。是1959年由D.L.Shell 提出来的。 • 该方法的基本思想是： • 先将整个待排元素序列分割成若干个子序列（由相隔某 个“增量”的元素组成的）分别进行直接插入排序， • 待整个序列中的元素基本有序（增量足够小）时，再对 全体元素进行一次直接插入排序。 • 因为直接插入排序在元素基本有序的情况下（接近最好情 况），效率是很高的，因此希尔排序在时间效率上有较大 提高