1插入排序(算法3-5) ●(1)基本思想:将n个元素的数列分为已有序 和无序两个部分。 {al},{a2,a3 a 4 ss, an {a1 a2( },{a3①,a4 an fal 2 },{anm1)}} 有序 无序 每次处理:将无序数列的第一个元素与有序数 上一页 列的元素从后往前逐个进行比较,找出插入位 置,将该元素插入到有序数列的合适位置中。 停止放映 从前往后,若比ai小,则放在ai前面 下一页 从后往前,若比ai大,则放在ai后边。 第11页
下一页 上一页 停止放映 第 11 页 1.插入排序（算法3-5） ⚫ (1)基本思想： 将n个元素的数列分为已有序 和无序两个部分。 {{a1}，{a2，a3，a4，…,an}} {{a1 (1) ，a2 (1) }，{a3 (1) ，a4 (1) …,an (1) }} …... {{a1(n-1) ，a2(n-1) ，…}, {an(n-1)}} 每次处理：将无序数列的第一个元素与有序数 列的元素从后往前逐个进行比较,找出插入位 置,将该元素插入到有序数列的合适位置中。 从前往后，若比ai小，则放在ai前面 从后往前，若比ai大，则放在ai后边。 有序 无序
(2)插入排序算法步骤 ●Step1从有序数列a}和无序数列a2,a3,…an3 开始进行排序; ●Step2处理第i个元素时(i=2,3,…,n),数列 a,a2…a1-}是已有序的,而数列{a,a1t1…,an 是无序的。用a1与a1-1、a12…,a1进行比较,找 上一页 出合适的位置将a插入。(从后往前比较) 停止放映。S23重复522,共进行n-1的插入处理,数 下一页 列全部有序。(从小到大排序) 第12页
下一页 上一页 停止放映 第 12 页 (2)插入排序算法步骤 ⚫ Step1 从有序数列{a1 }和无序数列{a2 ,a3 ,…,a n } 开始进行排序; ⚫ Step2 处理第i个元素时(i=2,3,…,n),数列 {a1 ,a2 ,…,ai-1 }是已有序的,而数列{ai ,ai+1 ,…,a n } 是无序的。用ai与ai-1、a i-2 ,…,a1进行比较,找 出合适的位置将ai插入。（从后往前比较） ⚫ Step3 重复Step2，共进行n-1的插入处理，数 列全部有序。（从小到大排序）
插入排序举例 设有数列{18,12,10,12,30,16} 初始状态:{18},{12,10,12,30,16}比较次数 i=1 {18},{12,10,12,30,16} i=2 [12,18},{10,12,30,16} i=3 {10,12,18},{12,30,16} 上一页 i=4 10,12,12,18},{30,16} 停止放映 下一页 i=5 10,12,12,18,30},{16} 10,12,12,16,18,30} 总计:9次 页
下一页 上一页 停止放映 第 13 页 插入排序举例 设有数列{ 18，12，10，12，30，16 } 初始状态：{18}，{12，10，12，30，16} 比较次数 i=1 {18}，{12，10，12，30，16} 1 i=2 {12，18}，{10，12，30，16} 2 i=3 {10，12，18}，{12，30，16} 2 i=4 {10，12，12，18}，{30，16} 1 i=5 {10，12，12，18，30}，{16} 3 {10，12，12，16，18，30 } 总计： 9 次
(3)插入排序算法实现 insert sort(item, n) int skite,n t int i,j,t for(i=1;i<n;i++)/*n-1次循环 t=iten[i];/*要插入的元素 / /*有序部分起始位置*/ while(j>=0&&t<item[j)/*寻找插入位置*/ item[j+1]=item[j;/*当前元素后移*/ 上一页 停止放映 下一页 item[j+1]=t /*插入该元素*/ 第14页
下一页 上一页 停止放映 第 14 页 (3)插入排序算法实现 insert_sort(item , n ) int *item ,n ; { int i，j，t ; for（i=1；i<n;i++ )/* n-1次循环 */ { t=item[i]; /* 要插入的元素 */ j = i - 1; /* 有序部分起始位置 */ while(j>=0 && t < item[j])/* 寻找插入位置*/ { item[j+1]=item[j]; /* 当前元素后移 */ j- - ; } item[j+1]=t; /* 插入该元素 */ } }
插入排序算法主程序 # include“ stdio.h main() inti,a[]={18,12,10,12,30,16} printf("Before sortingIn") for(i=0;i<6;i++) printf(%3d,a[i]); printf(“\n”);/*打印 insert sort(a,6);/*调用插入排序函数*/ 上一页 printf(“ After sortingⅦn); 停止放映 for(i=0;i<6;i++) 下一页 printf(%3d,a[ij);/*排序后打印* printf(n”); 示例 第15页
下一页 上一页 停止放映 第 15 页 插入排序算法主程序 #include “stdio.h” main( ) { int i,a[ ]={18,12,10,12,30,16}; printf(“Before sorting\n”); for(i=0;i<6;i++) printf(“%3d”,a[i]); printf(“\n”);/*打印 */ insert_sort(a,6); /* 调用插入排序函数 */ printf(“After sorting\n”); for(i=0;i<6;i++) printf(“%3d”,a[i]);/* 排序后打印 */ printf(“\n”); } 示例