Algorithms and DataStructures:Sorting 2、插入排序 2、 shell排序 e.g:将序列49、38、65、97、76、13、27、49、55、4用shell排序的方法进行排序 1、选定步长序列，如选为8、4、2、1 2、针对步长序列进行排序，从最大的步长开始，逐步减少步长，最后一次选择的 的步长肯定为1。 步长2：49、4、27、49、55、13、65、97、76、38 步长227、4、1小、6、65、4、7 36 SORT
36 物料管理 SORT Algorithms and DataStructures:Sorting 36 2、插入排序 2、 shell 排序 e.g: 将序列 49、38、65、97、76、13、27、49、55、4 用 shell 排序的方法进行排序 1、选定步长序列，如选为 8、4、2、1 2、针对步长序列进行排序，从最大的步长开始，逐步减少步长，最后一次选择的 的步长肯定为 1 。 步长 2：27、 4、49、13、55、38、65、49、76、 97 步长 2：49、 4、 27、49、55、13、65、97、76、38
Algorithms and DataStructures:Sorting 2、插入排序 2、 shel排序 e.g:将序列49、38、65、97、76、13、27、49、55、4用shell排序的方法进行排序 1、选定步长序列，如选为8、4、2、1 2、针对步长序列进行排序，从最大的步长开始，逐步减少步长，最后一次选择的 的步长肯定为1。 步长1：27、4、49、13、55、33、65、49、76、97 步长1：4、13、27、38、49、49、55、65、76、97 最后的排序结果 分析：shel排序的分析非常困难，原因是何种步长序列最优难以断定。通常认为时间 复杂性为：0(n32). 较好的步长序列：.121、40、13、4、1；可由递推公式S=3S11+1产生。 程序实现：类似于直接插入排序的程序。见书P272 注意修改步长。 37 SORT
37 物料管理 SORT Algorithms and DataStructures:Sorting 37 2、插入排序 2、 shell 排序 e.g: 将序列 49、38、65、97、76、13、27、49、55、4 用 shell 排序的方法进行排序 1、选定步长序列，如选为 8、4、2、1 2、针对步长序列进行排序，从最大的步长开始，逐步减少步长，最后一次选择的 的步长肯定为 1 。 步长 1：27、 4、49、13、55、33、65、49、76、 97 步长 1：4、 13、27、38、49、49、55、65、76、 97 最后的排序结果 分析: shell 排序的分析非常困难，原因是何种步长序列最优难以断定。通常认为时间 复杂性为：O（n3/2）. 较好的步长序列：. 121、40、13、4、1; 可由递推公式 Si= 3Si-1 + 1 产生。 程序实现: 类似于直接插入排序的程序。见书P272 注意修改步长
Algorithms and DataStructures:Sorting 3、快速排序 1、起泡排序 ·原理：若序列中有n个元素，通常进行n-1趟。第1趟，针对第r[1]至r[n个元 素进行。第2趟，针对第r[1们至rn一1]个元素进行。.第n-1趟，针对 第r[1]至r[2]个元素进行。 每一趟进行的过程： 从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确 ，则进行交换；否则继续比较下面两个相邻的元素。 结束条件：在任何一趟进行过程中，未出现交换。 e.g:将序列49、38、65、97、76、13、27、49用起泡排序的方法进行排序。 0 5 4 6 8 49 38 65 97 76 13 27 49 49 38 65 97 76 13 27 49 38 SORT
38 物料管理 SORT Algorithms and DataStructures:Sorting 38 3、快速排序 1、 起泡排序 • 原理: 若序列中有 n 个元素，通常进行 n - 1 趟。第 1 趟，针对第 r[1] 至 r[n] 个元 素进行。第 2 趟，针对第 r[1] 至 r[n－1] 个元素进行。. 第 n-1 趟，针对 第 r[1] 至 r[2] 个元素进行。 每一趟进行的过程： 从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确 ，则进行交换；否则继续比较下面两个相邻的元素。 结束条件：在任何一趟进行过程中，未出现交换。 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 0 1 2 3 4 5 6 7 8 49 49 38 38 65 65 97 97 76 76 13 13 27 27 49 49
Algorithms and DataStructures:Sorting 3、快速排序 1、起泡排序 ·原理：若序列中有n个元素，通常进行n-1趟。第1趟，针对第r[1们至r[个元 素进行。第2趟，针对第r[1们至rn一1)个元素进行。.第n-1趟，针对 第r[1]至r[2]个元素进行。 每一趟进行的过程： 从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确 ，则进行交换；否则继续比较下面两个相邻的元素。 结束条件：在任何一趟进行过程中，未出现交换。 e.g:将序列49、38、65、97、76、13、27、49用起泡排序的方法进行排序。 0 1 2 4 5 6 8 49 38 65 97 76 13 27 49 38 49 65 97 76 13 27 49 39 SORT
39 物料管理 SORT Algorithms and DataStructures:Sorting 39 3、快速排序 1、 起泡排序 • 原理: 若序列中有 n 个元素，通常进行 n - 1 趟。第 1 趟，针对第 r[1] 至 r[n] 个元 素进行。第 2 趟，针对第 r[1] 至 r[n－1] 个元素进行。. 第 n-1 趟，针对 第 r[1] 至 r[2] 个元素进行。 每一趟进行的过程： 从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确 ，则进行交换；否则继续比较下面两个相邻的元素。 结束条件：在任何一趟进行过程中，未出现交换。 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 0 1 2 3 4 5 6 7 8 49 38 49 38 65 65 97 97 76 76 13 13 27 27 49 49
Algorithms and DataStructures:Sorting 3、快速排序 1、起泡排序 ·原理：若序列中有n个元素，通常进行n-1趟。第1趟，针对第r[1]至r[个元 素进行。第2趟，针对第r[1们至rn一1]个元素进行。.第n-1趟，针对 第r[1]至r[2]个元素进行。 每一趟进行的过程： 从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确 ，则进行交换；否则继续比较下面两个相邻的元素。 结束条件：在任何一趟进行过程中，未出现交换。 e.g:将序列49、38、65、97、76、13、27、49用起泡排序的方法进行排序。 0 1 2 5 4 5 6 8 49 38 65 97 76 13 27 49 38 49 65 97 76 13 27 49 40 SORT
40 物料管理 SORT Algorithms and DataStructures:Sorting 40 3、快速排序 1、 起泡排序 • 原理: 若序列中有 n 个元素，通常进行 n - 1 趟。第 1 趟，针对第 r[1] 至 r[n] 个元 素进行。第 2 趟，针对第 r[1] 至 r[n－1] 个元素进行。. 第 n-1 趟，针对 第 r[1] 至 r[2] 个元素进行。 每一趟进行的过程： 从第一个元素开始，比较两个相邻的元素。若相邻的元素的相对位置不正确 ，则进行交换；否则继续比较下面两个相邻的元素。 结束条件：在任何一趟进行过程中，未出现交换。 e.g: 将序列 49、38、65、97、76、13、27、49 用 起泡排序的方法进行排序。 0 1 2 3 4 5 6 7 8 49 38 49 38 65 65 97 97 76 76 13 13 27 27 49 49