《排序算法设计》教学课件2

排序算法设计排序基本概念定义排序是将无序的记录序列调整为有序记录序列的一种操作。例如，将下列记录序列

{52,49,80,36,14,58,61,23,97,75}调整为序列

{14,23,36,49,52,58,61,75,80,97}排序基本概念关键字(key)假定被排序的数据是由一组记录组成的表，而记录则由若干个数据项组成，其中有一项可用来标识一个记录，称为关键字项，该数据项的值称为关键字。关键字可用作排序算法的依据。也称为排序码。排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序排序算法的稳定性：假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。排序算法的性能指标1.时间开销：⑴比较：关键码之间的比较；⑵移动：记录从一个位置移动到另一个位置。2.空间开销：辅助存储空间3.算法的稳定性我们从以下几方面来学习每一种排序方法思想实现时间性能空间性能稳定性适用情况直接选择排序基本思想：将数据元素序列分成有序区和无序区两部分。每趟排序都从无序区中选取出关键字最小的数据元素放在有序区的最后，直到全部数据元素排序完毕。要点：把元素集合划分为有序区和无序区初始时，有序区为空每趟排序过程中，从无序区中选出关键字最小的数据元素与无序区的第一个元素交换，以达到扩大有序区长度的目的。初始：[49386597761327]minjjjjjjmin一趟：13[386597764927]minminjjjjj二趟：1327[6597764938]三趟：132738[97764965]四趟：13273849[769765]五趟：1327384965[9776]六趟：132738496576[97]min直接选择排序flash演示void

SelectSort(DataTypeL[],intlen){ inti,j,min;

DataTypetmp;//临时变量，用于元素交换

for(i=0;i<len-1;i++) {//i+1为排序次数 min=i; for(j=i+1;j<len;j++)//查找最小元素 if(L[j].key<L[min].key) min=j;if(min!=i) { tmp=L[i];L[i]=L[min];L[min]=tmp; }}}划分为两个表(i>=0)有序表：L[0]～L[i]（第i+1次排序后）无序表：L[i+1]～L[len-1]（第i+1次排序后）两个循环大循环for(i=0;i<len-1;i++)确定比较的新元素L[i]，min=i小循环for(j=i+1;j<len;j++)确定当前的最小值排序前无序表最小值下标为min直接选择排序性能分析直接选择排序比较和移动的次数无论记录序列的初始状态如何，比较次数均相同；移动次数取决于待排记录序列的状态，当待排记录处于“正序”的情况时，所需进行的记录移动的次数最少；当待排记录处于“逆序”的情况时，所需进行的记录移动的次数最多；直接选择排序性能分析算法评价时间复杂度：T(n)=O(n²)空间复杂度：S(n)=O(1)只使用i、j、k和tmp4个辅助变量，与问题规模n无关。直接选择排序算法是一种不稳定的排序算法；直接选择排序算法简单、容易实现，适用于从大量记录中选择一部分排序；插入排序插入排序的基本思想是：将待排序表看做是左、右两部分，其中左边为有序区，右边为无序区，整个排序过程就是将右边无序区中的记录依次按关键字大小逐个插入到左边有序区中，以构成新的有序区，直到全部记录都排好序。三种插入排序方法：直接插入排序、二分法插入排序（也叫折半插入排序）和希尔排序。直接插入排序基本思想：将数据元素集合分成两部分，一部分为有序区，一部分为无序区。每次从无序区中取出一个数据元素，按其关键字大小将其插入到有序区的适当位置上，直到全部数据元素都插入到有序区中为止。有序序列无序序列r1r2ri-1rirnri+1…………r'1r'2r'i-1r'i……rnri+1……需解决的关键问题：（1）如何构造初始的有序序列？（2）如何查找待插入记录的插入位置?直接插入排序要点：把元素集合划分为有序区和无序区初始时，第一个元素默认构成有序区每趟排序过程中，将无序序列的第一个元素插入到有序序列的适当位置，以达到扩大有序区长度的目的。查找的方向：将待插入元素对有序区按照从后向前的顺序比较查找其插入位置；查找的标准：对有序区从后向前查找第一个不大于待插入元素的记录位置，即在查找插入位置过程中，若待插入元素小于当前有序区元素，则将当前有序区元素后移。49386597761327i=1(3849)6597761327i=2(384965)97761327i=3

(38496597)761327i=4

(3849657697)1327i=5

(133849657697)27初始

()i=6(133849657697)27271376976538jjjjjj977665493827直接插入排序flash演示void

InsertSort(DataTypeL[],intlen){ inti,j; DataTypetmp;

for(i=1;i<len;i++) {//i代表排序次数 tmp=L[i];;//存放待插入元素 for(j=i-1;j>=0;j--)//有序表数据比较和移动 ｛ if(tmp.key<L[j].key)//关键字比较 L[j+1]=L[j];//记录移动 else break; ｝ L[j+1]=tmp;//插入位置为j+1 }}structRecord{ intdata1;

intdata2;

intkey;};typedefRecordDataType;划分为两个表(i>=1)有序表：L[0]～L[i-1]（第i次排序前）无序表：L[i]～L[len-1]（第i次排序前）两个循环大循环for(i=1;i<len;i++)确定插入到有序表的新元素L[i]小循环for(j=i-1;j>=0;j--)有序表排序新元素L[i]插入在j+1位置上j的起始位置是i-1，终止位置为-1或第一个符合tmp.key

>=L[j].key的位置直接插入排序性能分析排序中的两个基本操作是：（关键字间的）比较和（记录的）移动。排序的时间性能取决于排序过程中这两个操作的次数。直接插入排序这两个操作的次数操作次数取决于待排记录序列的状态，当待排记录处于“正序”的情况时，所需进行的关键字比较和记录移动的次数最少，当待排记录处于“逆序”的情况时，所需进行的关键字比较和记录移动的次数最多，直接插入排序性能分析算法评价时间复杂度：T(n)=O(n²)空间复杂度：S(n)=O(1)只使用i、j和tmp3个辅助变量，与问题规模n无关。直接插入排序算法是一种稳定的排序算法。直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较少时。当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。已知一组数据的排序码为：{265，301，751，129，937，863，742，694，76，439}要求排序后数据从小到大排列，写出利用直接插入排序和直接选择排序的过程。初始26530175112993786374269476439第1趟第2趟第3趟第4趟第5趟第6趟第7趟第8趟第9趟初始26530175112993786374269476439第1趟76301751129937863742694265439第2趟76129751301937863742694265439第3趟76129265301937863742694751439第4趟76129265301937863742694751439第5趟76129265301439863742694751937第6趟76129265301439694742863751937第7趟76129265301439694742863751937第8趟76129265301439694742751863937第9趟76129265301439694742751863937直接选择排序初始26530175112993786374269476439第1趟26530175112993786374269476439第2趟26530175112993786374269476439第3趟12926530175193786374269476439第4趟12926530175193786374269476439第5趟12926530175186393774269476439第6趟129265301