C语言常见排序算法.ppt

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