C语言常见排序算法PPT学习课件

上章回顾,二叉树的定义树深度的定义什么样的二叉树是满二叉树中序遍历的规则,2020/5/2,常见排序算法,第六章,2020/5/2,预习检查,2020/5/2,课程目标,本章概述几种常见排序算法。本章目标熟悉常见的查找算法和排序算法难点快速排序算法,2020/5/2,本章结构,数据结构与算法初步,常见的排序算法,2020/5/2,6.1常见的排序算法,冒泡排序快速排序直接插入排序希尔排序选择排序堆排序归并排序,2020/5/2,6.1.1冒泡排序,算法描述设待排序记录序列中的记录个数为n一般地，第i趟起泡排序从1到n-i+1依次比较相邻两个记录的关键字，如果发生逆序，则交换之其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。,2020/5/2,6.1.1冒泡排序,算法实例,21,25,25*,16,08,012345,21,25*,49,25,16,49,chang=1,08,25*,chang=1,08,16,chang=1,25*,25,21,49,21,25,16,08,49,2020/5/2,6.1.1冒泡排序,算法实例,25*,012345,i=4,49,16,chang=1,08,25,21,25*,i=5,49,16,chang=0,08,25,21,2020/5/2,6.1.1冒泡排序,算法实例,2020/5/2,6.1.1冒泡排序,算法实现,#includemain()inta11,i,j,t;printf(Input10numbers:n);for(i=1;iai+1)t=ai;ai=ai+1;ai+1=t;printf(Thesortednumbers:n);for(i=1;i11;i+)printf(%d,ai);,2020/5/2,6.1.2快速排序,算法特点：快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分一部分所有记录的关键码大于等于支点记录的关键码另一部分所有记录的关键码小于支点记录的关键码,2020/5/2,6.1.2快速排序,算法描述：任取待排序记录序列中的某个记录(例如取第一个记录)作为基准(枢),按照该记录的关键字大小,将整个记录序列划分为左右两个子序列左侧子序列中所有记录的关键字都小于或等于基准记录的关键字右侧子序列中所有记录的关键字都大于基准记录的关键字基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。然后分别对这两个子序列重复施行上述方法，直到所有的记录都排在相应位置上为止。基准记录也称为枢轴（或支点）记录。取序列第一个记录为枢轴记录，其关键字为Pivotkey指针low指向序列第一个记录位置指针high指向序列最后一个记录位置,2020/5/2,6.1.2快速排序,算法实例：,2020/5/2,6.1.2快速排序,算法实例：,15,2020/5/2,6.1.2快速排序,算法分析：快速排序是一个递归过程;利用序列第一个记录作为基准，将整个序列划分为左右两个子序列。只要是关键字小于基准记录关键字的记录都移到序列左侧；快速排序的趟数取决于递归树的高度。如果每次划分对一个记录定位后,该记录的左侧子序列与右侧子序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,这是最理想的情况,16,2020/5/2,6.1.3直接插入排序,算法描述：记录存放在数组R0.n-1中，排序过程的某一中间时刻，R被划分成两个子区间R0i-1和Ri.n-1，其中：前一个子区间是已排好序的有序区；后一个子区间则是当前未排序的部分。基本操作将当前无序区的第1个记录Ri插入到有序区R0.i-1中适当的位置，使R0i变为新的有序区,2020/5/2,6.1.3直接插入排序,操作细节：当插入第i(i1)个对象时,前面的r0,r1,ri-1已经排好序。用ri的关键字与ri-1,ri-2,的关键字顺序进行比较(和顺序查找类似)，如果小于，则将rx向后移动(插入位置后的记录向后顺移)找到插入位置即将ri插入,2020/5/2,6.1.3直接插入排序,实用例子：已知待序的一组记录的初始排列为：21,25,49,25*,16,08,2020/5/2,6.1.3直接插入排序,实用例子：,2020/5/2,6.1.3直接插入排序,实用例子：,2020/5/2,6.1.3直接插入排序,算法实现：,voidInsertSort(intr,intn)/假设关键字为整型，放在向量r中inti,j,temp;for(i=1;i0;j-)/从后向前顺序比较，并依次后移if(temprj-1)rj=rj-1;elsebreak;rj=temp;,2020/5/2,6.1.3直接插入排序,算法分析：关键字比较次数和记录移动次数与记录关键字的初始排列有关。最好情况下,排序前记录已按关键字从小到大有序,每趟只需与前面有序记录序列的最后一个记录比较1次,移动2次记录,总的关键字比较次数为n-1,记录移动次数为2(n-1)在平均情况下的关键字比较次数和记录移动次数约为n2/4。直接插入排序是一种稳定的排序方法直接插入排序最大的优点是简单，在记录数较少时，是比较好的办法,2020/5/2,6.1.4希尔排序,希尔排序又称缩小增量排序是1959年由D.L.Shell提出来的算法描述先取定一个小于n的整数d作为第一个增量，把表的全部记录分成d组所有距离为d1的倍数的记录放在同一组中，在各组内进行直接插入排序然后取第二个增量d2d1重复上述的分组和排序，直至增量d1，即所有记录放在同一组中进行直接插入排序为止。,2020/5/2,6.1.4希尔排序,算法特点先取定一个小于n的整数d作为第一个增量，把表的全部记录分成d组所有距离为d1的倍数的记录放在同一组中，在各组内进行直接插入排序然后取第二个增量d2d1重复上述的分组和排序，直至增量d1，即所有记录放在同一组中进行直接插入排序为止。,2020/5/2,6.1.4希尔排序,运用实例先取定一个小于n的整数d作为第一个增量，把表的全部记录分成d组所有距离为d1的倍数的记录放在同一组中，在各组内进行直接插入排序然后取第二个增量d2d1重复上述的分组和排序，直至增量d1，即所有记录放在同一组中进行直接插入排序为止。,2020/5/2,6.1.4希尔排序,算法描述首先取一个整数gapn(待排序记录数)作为间隔,将全部记录分为gap个子序列,所有距离为gap的记录放在同一个子序列中在每一个子序列中分别施行直接插入排序。然后缩小间隔gap,例如取gap=gap/2重复上述的子序列划分和排序工作，直到最后取gap=1,将所有记录放在同一个序列中排序为止。,2020/5/2,6.1.4希尔排序,运用实例已知待排序的一组记录的初始排列为：21,25,49,25*,16,08,2020/5/2,6.1.4希尔排序,运用实例,2020/5/2,6.1.4希尔排序,算法分析开始时gap的值较大,子序列中的记录较少,排序速度较快随着排序进展,gap值逐渐变小,子序列中记录个数逐渐变多,由于前面大多数记录已基本有序,所以排序速度仍然很快Gap的取法有多种。shell提出取gap=n/2，gap=gap/2，直到gap=1。,2020/5/2,6.1.5选择排序,排序过程：首先通过n-1次比较，从n个数中找出最小的，将它与第一个数交换第一趟选择排序，结果最小的数被安置在第一个元素位置上再通过n-2次比较，从剩余的n-1个数中找出关键字次小的记录，将它与第二个数交换第二趟选择排序重复上述过程，共经过n-1趟排序后，排序结束,2020/5/2,6.1.5选择排序,排序实例：,例,初始：49386597761327,i=1,13,49,一趟：13386597764927,i=2,27,38,六趟：13273849657697,2020/5/2,6.1.5选择排序,算法实例：,21,25,25*,16,08,012345,21,25*,i=1,49,25,16,25,16,08,49,08,25*,49,21,i=2,i=3,08,16,25*,25,21,初始,49,2020/5/2,6.1.5选择排序,算法实例：,25*,012345,25*,25,16,08,49,25*,49,21,08,16,25,21,最小者25*无交换,最小者25无交换,25,21,16,08,各趟排序后的结果,2020/5/2,6.1.5选择排序,算法实例：,012345,49,16,08,25*,49,21,08,25*,25,21,i=2时选择排序的过程,ikj,49,25,08,25*,16,21,ikj,4925,25*25,16,25,1625,ikj,2020/5/2,6.1.5选择排序,算法实例：,49,25,08,25*,16,21,012345,ikj,2116,k指示当前序列中最小者,2020/5/2,6.1.5选择排序,算法实现：,#includemain()inta11,i,j,k,x;printf(Input10numbers:n);for(i=1;i11;i+)scanf(%d,2020/5/2,各种排序算法对比分析,排序法平均时间最差情形稳定度额外空间备注冒泡O(n2)O(n2)稳定O(1)n小时较好交换O(n2)O(n2)不稳定O(1)n小时较好选择O(n2)O(n2)不稳定O(1)n小时较好插入O(n2)O(n2)稳定O(1)大部分已排序时较好基数O(logRB)O(logRB)稳定O(n)B是真数(0-9)，R（个十百）ShellO(nlogn)O(ns)1s2不稳定O(1)s是所选分组快速O(nlogn)O(n2)不稳定O(nlogn)n大时较好归并O(nlogn)O(nlogn)稳定O(1)n大时较好堆O(nlogn)O(nlogn)不稳定O(1)n大时较好,2020/5/2,阶段小节,几种常见的排序算法冒泡排序的特点快速排序的特点，一趟排序的子过程,2020/5/2,本章总结,数据结构与算法初步,常见的排序算法,重点讲述冒泡排序和快速排序的