(4)算法评价 ●插入算法比较次数和交换次数约 为n2/2,因此,其时间复杂度 为0(n2)。 ●该算法是稳定的。 ●1234。 ●0123。。。N1 上一页 ●(n-1+1)(n-1)/2 停止放映 下一页 第16页
下一页 上一页 停止放映 第 16 页 （4）算法评价 ⚫ 插入算法比较次数和交换次数约 为 n 2 /2，因此，其时间复杂度 为O（ n 2 ）。 ⚫ 该算法是稳定的。 ⚫ 1 2 3 4 。。。N ⚫ 0 1 2 3。。。N-1 ⚫ (n-1+1)*(n-1)/2
2.选择排序(算法3-6) (1)基本思想:每次从待排序的记录中选出关键字 最小(或最大)的记录,顺序放在已有序的记录 序列的最后(或最前)面,直到全部数列有序。 {a1},{a2,a3,a4,…,an} (1) a a2(1) },{a3①,a an al(n-1) a2(n1) an 有序 无序 上一页 停止放映 下一页 第17页
下一页 上一页 停止放映 第 17 页 2.选择排序（算法3-6） ⚫ (1)基本思想：每次从待排序的记录中选出关键字 最小（或最大）的记录，顺序放在已有序的记录 序列的最后（或最前）面，直到全部数列有序。 {{a1}，{a2，a3，a4，…,an}} {{a1(1) ，a2(1)}，{a3(1) ，a4(1)…,an (1)}} …... {{a1(n-1) ，a2(n-1) ，…}, {an(n-1)}} 有序 无序
(2)选择排序算法步骤 ● StepI从原始数列{a1,a2,a3,…,an}开始进行 排序,比较n-1次,从中选出最小关键字,放在 有序数列中,形成{a1}、{a2,a3,…,an}有序数 列和无序数列两部分,完成第1趟排序。 ●Step2处理第i趟排序时(i=2,3,…,n),从剩下 的n-i+1个元素中找出最小关键字,放在有序数 列的后面。 上一页 ●SteD3重复Step2,共进行n-1趟的选择处理 数列全部有序。 停止放映 从大到小排序 下一页 第18页
下一页 上一页 停止放映 第 18 页 (2)选择排序算法步骤 ⚫ Step1 从原始数列{a1 , a2,a3,…,an}开始进行 排序，比较n-1次，从中选出最小关键字，放在 有序数列中，形成{a1}、 {a2,a3,…,an}有序数 列和无序数列两部分，完成第1趟排序。 ⚫ Step2 处理第i趟排序时(i=2,3,…,n),从剩下 的n-i+1个元素中找出最小关键字，放在有序数 列的后面。 ⚫ Step3 重复Step2，共进行n-1趟的选择处理， 数列全部有序。 ⚫ 从大到小排序
选择排序举例 设有数列{18,12,10,12,30,16} 初始状态:{},{18,12,10,12,30,16}比较次数 i=1 {10},{18,12,12,30,16} i=2 10,12},{12,18,30,16} 543 i=3 {10,12,12},{18,30,16} 上一页 「停止放映i=4 10,12,12,16},{18,30} 下一页 10,12,12,16,18},{30} 总计:15繁。页
下一页 上一页 停止放映 第 19 页 选择排序举例 设有数列{ 18，12，10，12，30，16 } 初始状态：{}，{18，12，10，12，30，16} 比较次数 i=1 {10}，{18，12，12，30，16} 5 i=2 {10，12}，{12，18，30，16} 4 i=3 {10，12，12}，{18，30，16} 3 i=4 {10，12，12，16}，{18，30} 2 i=5 {10，12，12，16，18}，{30} 1 总计： 15 次
(3)选择排序算法 select sort(int *item, int count) int i, j,k,t for(i=0;i< count-1;++i)/*n-1次循环 / k /*无序部分第1个元素*/ t=item[i] /*及位置 / for(j=i+1; Gcount;++j)/寻找最小值循环*/ I if(item]<t k=j;t=iten[j;}/*记录最小值及位置*/ 上一页 停止放映 item[k]=item[i];/*交换最小值与无序*/ 下一页 item[i]=t /*部分第1个元素位置*/ 第20页
下一页 上一页 停止放映 第 20 页 (3)选择排序算法 select_sort(int *item,int count) { int i,j,k，t; for(i=0;i<count-1;++i)/* n-1次循环 */ { k=i; /* 无序部分第1个元素 */ t=item[i]; /* 及位置 */ for(j=i+1;j<count;++j)/* 寻找最小值循环 */ { if(item[j]<t) { k=j; t=item[j]; }/* 记录最小值及位置 */ } item[k]=item[i]; /* 交换最小值与无序 */ item[i]=t; /* 部分第1个元素位置*/ } }