算法分析与设计八大排序.docx
- 文档编号:12984405
- 上传时间:2023-06-09
- 格式:DOCX
- 页数:31
- 大小:202.03KB
算法分析与设计八大排序.docx
《算法分析与设计八大排序.docx》由会员分享,可在线阅读,更多相关《算法分析与设计八大排序.docx(31页珍藏版)》请在冰点文库上搜索。
算法分析与设计八大排序
算法八大排序详解
1.排序的基本概念:
排序是各门语言中的核心,也是计算机数据处理中的核心运算,是我们学过的“数据结构与算法”课程的重点。
排序算法能够体现算法设计和算法分析的精神。
有效的排序算法在一些算法(例如搜索算法与合并算法)中是重要的,如此这些算法才能得到正确解答。
这篇博文主要包含了8大内部排序的算法复杂度,稳定性以及描述算法和可视化过程,花时间总结了很久,但是肯定仍有不足,希望各位大神能指点迷津。
小注:
刚发现,可视化过程的图片是gif格式,但是传上去之后好像不动,不好意思。
请在点连接:
可视化视图视觉直观感受
7种常用的排序算法(在最后的参考资料中也有)
(1)排序算法的输出必须遵守下列两个原则:
a)输出结果为递增串行(递增是针对所需的排序顺序而言);
b)输出结果是原输入的一种排列、或是重组。
(2)被排序的对象-文件
被排序的对象--文件由一组记录组成。
记录则由若干个数据项(或域)组成。
其中有一项可用来标识一个记录,称为关键字项。
该数据项的值称为关键字(Key)。
(3)排序运算的依据--关键字
关键字,可以是数字类型,也可以是字符类型。
关键字的选取应根据问题的要求而定。
2.排序的分类
1)按是否涉及内外存交换:
(1)内部排序:
待排序的记录全部存放在内存中进行排序的过程。
(2)外部排序:
待排序的记录的数量很大,以至于内存不能容纳全部记录,在排序过程中需要对外存进行访问的排序过程。
2)按策略划分内部排序方法
(1)插入排序:
直接插入排序,折半插入排序;
(2)选择排序:
快速排序,冒泡排序;
(3)交换排序:
简单选择排序,堆排序;
(4)归并排序:
归并排序;
(5)分配排序:
基数排序;
3)按稳定性划分内部排序
(1)稳定排序:
直接插入排序,冒泡排序,归并排序,基数排序
(2)不稳定排序:
简单选择排序,希尔排序,快速排序,堆排序
3.内部排序算法的操作
大多数排序算法都有两个基本的操作:
比较和移动;
(1)比较两个关键字的大小;
(2)改变指向记录的指针或移动记录本身。
操作的实现依赖于待排序记录的存储方式(①待排序的记录存放在连续的一组存储单元上,类似于线性表的顺序存储;②待排序的记录存放在静态链表中;③待排序的记录本身存储在一组地址连续的存储单元内,同时另设一个指示各个记录存储位置的地址向量,排序时不移动记录本身,而是移动地址向量中这些记录的地址)。
4.内部排序各算法代码图示详解
(1)冒泡排序
a)冒泡排序代码:
[objc]viewplaincopyprint?
1. 14px;">voidbubbleSort(){ 2.for(i=0;i 3.change=false; 4.for( rgb(51,51,51);">j=0;j 5.if(a[j]>a[j+1]){ 6.a[j]←→a[j+1]; 7.change=true; 8.} 9.if(! change){ 10.break; 11.} 12.} 13.} 14.} voidbubbleSort(){ for(i=0;i change=false; for(j=0;j if(a[j]>a[j+1]){ a[j]←→a[j+1]; change=true; } if(! change){ break; } } } } b)冒泡排序的可视化试图: (2)选择排序: a)选择排序代码: [objc]viewplaincopyprint? 1. 14px;">voidselectionSort(){ 2.for(i=0;i 3.k=i; 4.for(j=i+1;j 5.if(a[j] 6.k=j; 7.} 8.if(k! =i){ 9.a[i]←→a[k]; 10.} 11.} 12.} 13.} voidselectionSort(){
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 分析 设计 八大 排序