当前位置:首页 » 《随便一记》 » 正文

数据结构:排序_Z2658172512的博客

13 人参与  2022年04月09日 08:53  分类 : 《随便一记》  评论

点击全文阅读


当当当当~~~~欢迎大家阅读,接下来我们一起学习数据结构中的排序

一、目录

一、排序相关的知识点

二、插入排序

(一)直接插入排序

(二)希尔排序

三、交换排序

(一)冒泡排序

(二)双向冒泡排序

(三)快速排序

四、选择排序

(一)直接选择排序

(二)堆排序

五、归并排序

六、分配排序

(一)箱排序

(二)基数排序


快来一起学习呀~~~~ 

二、学习内容

一、排序相关的知识点

(1)排序:就是要整理文件中的记录,使得它按给定的关键字递增或递减的次序排列
(2)内外排序:若整个待排序数据都在内存中处理,不涉及数据的内外存交换,则称这种排序为内部排序,反之为外排序
(3)内部排序方法:插入、选择、交换、归并、分配
(4)排序过程中需要进行的两种基本操作:比较两个关键字的大小、改变指向记录的指针或移动记录本身
(5)待排序记录的存储方式:顺序结构、链式结构、辅助表形式
(6)评价排序算法的标准:执行算法需要的时间、算法所需要的附加空间

二、插入排序

(一)直接插入排序

       将数组R划分成两个子区间,前一个为排好序的有序区,后一个为无需区,每次从无需区中取一个元素插入到有序区的适当位置,直到无序区为空

(二)希尔排序

       取一个小于n的整数作为第一个增量,元素分成n个组,距离为n的倍数的元素放在同一个组,接着个组内进行直接插入排序,直到n=1把所有的元素放在同一个组进行直接插入排序

三、交换排序

(一)冒泡排序

通过相邻元素之间的比较和交换,是关键字较小的元素逐渐从底部移向顶部 ,小的上浮,大的下沉

(二)双向冒泡排序

        交替改变扫描方向,即一趟从下向上通过两个相邻关键字的比较,将关键字最小的记录换至最上面位置,再一趟则是从第二个记录开始,向下通过两个相邻关键字的比较,换至最下面的位置

(三)快速排序

        任取一个记录作为排序比较的基准,并使左边的无序区所记录的关键字均小于等于基准的关键字,右边的无序区所记录的关键字均于大等于基准的关键字,分别对他们进行划分,直到所有的无序区的记录均已排好序为止

四、选择排序

(一)直接选择排序

每次从待排序的无序区中选择出关键字值最小的记录,将该记录与该区的第一个记录交换位置

(二)堆排序

       利用完全二叉树中双亲结点和孩子节点之间的内在关系,在当前无序区中选择关键字最大或最小记录,每个结点表示一个记录,依次逐层从左到右顺序排列,构成一棵完全二叉树,把较小的关键字逐层筛下去,而较大的被逐层选上来

五、归并排序

       首先将待排序文件看成N个长度为一的有序子文件,把这些子文件两两归并,直到最后得到一个长度为n的有序文件为止

六、分配排序

(一)箱排序

          箱排序其基本思想是:设置若干个箱子,依次扫描待排序的记录R[0],R[1],…,R[n-1],把关键字等于k的记录全都装入到第k个箱子里(分配),然后按序号依次将各非空的箱子首尾连接起来(收集)。

(二)基数排序

       不断装箱的过程,首先按个未进行装箱,各位相同的按其出现的顺序进行装箱,后装入的记录用尾指针指向,装完后按箱子序号从小到大排成一个新序列,在对新序列按百位进行装箱,即百位数字相同的按其先后装入箱子,再按箱子的序号从小到大排成一个新序列,直到新序列全部有序为止。

以上就是数据结构中排序的内容啦,希望我的文章对你有所帮助,如果有错误的地方还望大家批评指正,谢谢大家阅读!


点击全文阅读


本文链接:http://zhangshiyu.com/post/37576.html

排序  记录  关键字  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1