《软件技术基础第三章2基本排序》由会员分享，可在线阅读，更多相关《软件技术基础第三章2基本排序（69页珍藏版）》请在金锄头文库上搜索。
1、冒泡排序与快速排序(交换排序法) 简单插入排序与希尔排序(插入排序法) 简单选择排序与堆排序(选择排序法) 其他排序方法简介,排序是数据处理的重要内容,是指将一个无序序列整理成按值非递减顺序排列的有序序列(本章仅介绍内部排序:即能够在内存中完成的排序),基本排序,交换排序,交换排序的思想是通过交换元素以达到消除逆序的目的 冒泡排序 (1)从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后。 (2)除去最后已
2、经冒出的元素,对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时冒出的元素构成的线性表已经变为有序。,逆序：在数组An中,存在iAj则称Ai和Aj构成一个逆序,5 1 7 3 1 6 9 4 2 8 6,冒泡排序需要经过(n-1)+(n-2)+(n-3)+1=n(n-1)/2次比较 算法复杂度量级为O(n2),双向冒泡排序 (1)从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后。 (2)从后到前扫
3、描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将剩下线性表中的最小者换到了表的最前面 (3)对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。,bubsort(p，n) int n； ET p； int m，k，j，i； ET d； k0； mn1； while (km) /*子表未空*/ jm1； m0； for(ik；ij；i) /*从前往后扫描*/ if (pipi1) /*发现逆序进行交换*/ dp
4、i；pipi+1；pi+1d；mi； jk1； k0； for (im；ij；i) /*从后往前扫描*/ if (pi1 pi) /*发现逆序进行交换*/ dpi；pipi-1；pi-1d；ki； return； ,输入：无序序列P(1：n)。 输出：有序序列P(1：n)。,虽然从算法上优化了冒泡法排序,但是其最坏算法复杂度量级依然是O(n2),快速排序: 解决冒泡排序中一次仅通过交换两个相邻元素完成一个逆序的消除的效率不高的问题 快速排序的思想为:从线性表中取一个元素,设为T,小于T的元素移到T前,大于T的元素移到T后从而将线性表以T为分界分成两个子表. 关键是对线性表的分割.,首先，在表的
5、第一个、中间一个与最后一个元素中选取其中一项作为枢纽， 设为P(k)，并将P(k)赋给T，再将表中的第一个元素移到 P(k)的位置上。 然后设置两个指针i和j分别指向表的起始与最后的位置。反 复作以下两步： (1)将j逐渐减小，并逐次比较P(j)与T，直到发现一个 P(j)T为止，将P(j)移到P(i)的位置上。 (2)将i逐渐增大，并逐次比较P(i)与T，直到发现一个 P(i)T为止，将P(i)移到P(j)的位置上。 上述两个操作交替进行，直到指针i与j指向同一个位置 （即ij）为止，此时将T移到P(i)的位置上。,算法描述,9,例: 将序列 49、38、65、97、76、13、27、49
6、用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,10,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,11,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,
7、13,13,27,27,49,49,49,界点,12,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,13,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,14,e.g: 将序列 49、38、65、97、76、13、27、49
8、用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,15,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,16,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,
9、13,13,27,27,49,49,49,界点,17,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,18,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,19,e.g: 将序列 49、38、65、97、76、13、27、49
10、用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,20,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,13,13,27,27,49,49,49,界点,21,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,49,38,38,65,65,97,97,76,76,
11、13,13,27,27,49,49,49,界点,22,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,界点,23,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,界点,24,e.g: 将序列 49、38、65、97、76、13、27、49
12、用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,界点,25,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,27,38,38,13,65,97,49,76,76,13,97,65,27,49,49,49,界点,26,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,27,38,38,13,65,97,49,76,76,
13、13,97,65,27,49,49,49,界点,27,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,界点,28,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3 4 5 6 7 8,13,38,27,38,65,97,49,76,76,13,97,65,27,49,49,49,界点,29,e.g: 将序列 49、38、65、97、76、13、27、49 用 快速排序的方法进行排序。,0 1 2 3
