()插入排序(算法3-5) ●基本思想:将n个元素的数列分为已有序和无 序两个部分。 {a1},{a2,a3,a4,…,an} {a1 a2( },{a3),a4 ,an⑦; a1-1),a2-1),…},{an(m)]} 有序 无序 上一页 每次处理就是将无序数列的第一个元素与有序 停止放映 数列的元素从后往前逐个进行比较,找出插入 下一页 位置,将该元素插入到有序数列的合适位置中。 第11页
下一页 上一页 停止放映 第 11 页 ⑴插入排序（算法3-5） ⚫ 基本思想： 将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)}} 每次处理就是将无序数列的第一个元素与有序 数列的元素从后往前逐个进行比较,找出插入 位置,将该元素插入到有序数列的合适位置中。 有序 无序
插入排序算法步骤 ●Step1从有序数列{a,}和无序数列{an,an,…,a} 开始进行排序; ●Step2处理第i个元素时(i=2,3,…,n),数列 a,a2…a1-}是已有序的,而数列a;,a1+…,an 是无序的。用a1与a1、ax2…,a进行比较,找 上一页 出合适的位置将a1插入。 你止放·teD3重复Sten2,共进行n1的插入处理,数 下一页 列全部有序。 第12页
下一页 上一页 停止放映 第 12 页 插入排序算法步骤 ⚫ Step1 从有序数列{a1 }和无序数列{a2 ,a3 ,…,an } 开始进行排序; ⚫ Step2 处理第i个元素时(i=2,3,…,n),数列 {a1 ,a2 ,…,ai-1 }是已有序的,而数列{ai ,ai+1 ,…,an } 是无序的。用ai与ai-1、a i-2 ,…,a1进行比较,找 出合适的位置将ai插入。 ⚫ Step3 重复Step2，共进行n-1的插入处理，数 列全部有序
插入排序算法 insert sort(item, n) int *item,n i I inti,j,t for (i=1: i<n; i++) i t=item [il j=i-1 while(j>=0 & t< item[j]) I item[j+1]=itemLj J--; 上一页 停止放映 item[计1]=t; 下一页 第13页
下一页 上一页 停止放映 第 13 页 插入排序算法 insert_sort(item , n ) int *item ,n ; { int i，j，t ; for（i=1；i<n;i++ ) { 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 sorting\n") for(i=0;i<6;i++) printf(%3d,a[i]); printf(“\n”) insert sort(a, 6) printf(“ After sorting”); 上一页 for(i=0;i<6;i++) 停止放映 printf(%3d, ali]) 下一页 printf(“\n”); 第14页
下一页 上一页 停止放映 第 14 页 插入排序算法主程序 #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”); }
算法讨论 ●插入算法比较次数和交换次数 约为n2/2,因此,其时间复杂 度为0(n2) ●该算法是稳定的。 上一页 停止放映 下一页 第15页
下一页 上一页 停止放映 第 15 页 算法讨论 ⚫ 插入算法比较次数和交换次数 约为 n 2 /2，因此，其时间复杂 度为O（ n 2 ）。 ⚫ 该算法是稳定的