各种排序算法总结(C语言版)ppt课件.ppt
《各种排序算法总结(C语言版)ppt课件.ppt》由会员分享,可在线阅读,更多相关《各种排序算法总结(C语言版)ppt课件.ppt(35页珍藏版)》请在三一办公上搜索。
1、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
2、.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 快速排序,算法特点:快速排
3、序是通过比较关键码、交换记录,以某个记录为界(该记录称为支点),将待排序列分成两部分一部分所有记录的关键码大于等于支点记录的关键码另一部分所有记录的关键码小于支点记录的关键码,6.1.2 快速排序,算法描述:任取待排序记录序列中的某个记录(例如取第一个记录)作为基准(枢),按照该记录的关键字大小,将整个记录序列划分为左右两个子序列左侧子序列中所有记录的关键字都小于或等于基准记录的关键字 右侧子序列中所有记录的关键字都大于基准记录的关键字基准记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。然后分别对这两个子序列重复施行上述方法,直到所有的记录都排在相应位置上为止。基准记录也称为枢轴(
4、或支点)记录。取序列第一个记录为枢轴记录,其关键字为Pivotkey指针low指向序列第一个记录位置指针high指向序列最后一个记录位置,6.1.2 快速排序,算法实例:,6.1.2 快速排序,算法实例:,10,6.1.2 快速排序,算法分析:快速排序是一个递归过程;利用序列第一个记录作为基准,将整个序列划分为左右两个子序列。只要是关键字小于基准记录关键字的记录都移到序列左侧;快速排序的趟数取决于递归树的高度。如果每次划分对一个记录定位后, 该记录的左侧子序列与右侧子序列的长度相同, 则下一步将是对两个长度减半的子序列进行排序, 这是最理想的情况,11,6.1.3 直接插入排序,算法描述:记录
5、存放在数组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 直接插入排序,实用例子:已知待序的一组记录的初始排
6、列为: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 直接插入排序,算法分析:关键字比较次数和记录移动次数与记录关键字的初始排列有关。最好情况下, 排序前记录已按关
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 各种 排序 算法 总结 语言版 ppt 课件

链接地址:https://www.31ppt.com/p-1408740.html