令例:对于关键字序列{38,20,46,38,74,91, 12,25}进行直接插入排序,写出排序过程中每趟排序 的结果。 初始状态[38][20463874911225] 第一趟[2038][463874911225] 第二趙[203846][3874911225] 第三趙[20383846][74911225] 第四趟[2038384674][911225] 第五趟[203838467491][1225]
计 算 机 软 件 基 础 ❖ 例：对于关键字序列{38，20，46，38，74，91， 12，25}进行直接插入排序，写出排序过程中每趟排序 的结果。 初始状态 [38] [20 46 38 74 91 12 25] 第一趟 [20 38] [46 38 74 91 12 25] 第二趟 [20 38 46] [38 74 91 12 25] 第三趟 [20 38 38 46] [74 91 12 25] 第四趟 [20 38 38 46 74] [91 12 25] 第五趟 [20 38 38 46 74 91] [12 25]
令例:对于关键字序列{38,20,46,38,74,91, 12,25}进行直接插入排序,写出排序过程中每趟排序 的结果。 初始状态[38][20463874911225] 第一趟[2038][463874911225] 第二趙[203846][3874911225] 第三趙[20383846][74911225] 第四趟[2038384674][911225] 第五趟[203838467491][1225] 第六趙[12203838467491][25]
计 算 机 软 件 基 础 ❖ 例：对于关键字序列{38，20，46，38，74，91， 12，25}进行直接插入排序，写出排序过程中每趟排序 的结果。 初始状态 [38] [20 46 38 74 91 12 25] 第一趟 [20 38] [46 38 74 91 12 25] 第二趟 [20 38 46] [38 74 91 12 25] 第三趟 [20 38 38 46] [74 91 12 25] 第四趟 [20 38 38 46 74] [91 12 25] 第五趟 [20 38 38 46 74 91] [12 25] 第六趟 [12 20 38 38 46 74 91] [25]
例。对千关键字席列〔38.20.A6.38.7A.91 某趟排序,将lt插入有序表ist1l-isti-1中 的结果。 初始状态[38][20463874911225] 第一趟[2038][463874911225] 第二趙[203846][3874911225] 第三趙[20383846][74911225] 第四趟[2038384674][911225] 第五趟[203838467491][1225] 第六趙[12203838467491][25] 第七趙[1220253838467491]
计 算 机 软 件 基 础 ❖ 例：对于关键字序列{38，20，46，38，74，91， 12，25}进行直接插入排序，写出排序过程中每趟排序 的结果。 初始状态 [38] [20 46 38 74 91 12 25] 第一趟 [20 38] [46 38 74 91 12 25] 第二趟 [20 38 46] [38 74 91 12 25] 第三趟 [20 38 38 46] [74 91 12 25] 第四趟 [20 38 38 46 74] [91 12 25] 第五趟 [20 38 38 46 74 91] [12 25] 第六趟 [12 20 38 38 46 74 91] [25] 第七趟 [12 20 25 38 38 46 74 91] 某趟排序，将list[i]插入有序表list[1]~list[i-1]中
算法描述 冷算法功能:实现将一个长度为n的线性表st上的所 有元素按关键字升序排列。 void insertsort(ElemType listI, int n) intJ趟排序所做的操作 for(i=2;iκ=n;i++)/外循环控制排序的总趟数* I listoFlist D: IFi; while((fsilolkey< fsitpkeyD ∥在衔序表唧寻插入位翬 s们 s萨吧i sinsersort*/
计 算 机 软 件 基 础 二. 算法描述 ❖ 算法功能：实现将一个长度为n的线性表list上的所 有元素按关键字升序排列。 void insertsort (ElemType list[] , int n) {int i,j; for (i=2;i<=n;i++) /*外循环控制排序的总趟数*/ { list[0]=list[i]; j=i-1; while (list[0].key< list[j].key) /*在有序表中寻找插入位置*/ { list[j+1]=list[j]; j--; } list[j+1]=list[0]; } } /*insersort*/ //第i趟排序所做的操作 { list[0]=list[i]; j=i-1; while (list[0].key< list[j].key) /*在有序表中寻找插入位置*/ { list[j+1]=list[j]; j--; } list[j+1]=list[0]; }
ist[0]的作用 ●用于保存待插记录isti的值,以免在 后移过程中被覆盖而丢失。 ●作为“监视哨”,防止数组下标越界。 012345678 122038384674911225
• list[0]的作用 用于保存待插记录list[i]的值，以免在 后移过程中被覆盖而丢失。 作为“监视哨”，防止数组下标越界。 0 1 2 3 4 5 6 7 8 12 20 38 38 46 74 91 12 25