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

一、目录

一、排序相关的知识点

二、插入排序

(一)直接插入排序

(二)希尔排序

三、交换排序

(一)冒泡排序

(二)双向冒泡排序

(三)快速排序

四、选择排序

(一)直接选择排序

(二)堆排序

五、归并排序

六、分配排序

(一)箱排序

(二)基数排序

---

快来一起学习呀~~~~ 

二、学习内容

一、排序相关的知识点

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

二、插入排序

(一)直接插入排序

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

(二)希尔排序

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

三、交换排序

(一)冒泡排序

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

(二)双向冒泡排序

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

(三)快速排序

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

四、选择排序

(一)直接选择排序

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

(二)堆排序

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

五、归并排序

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

六、分配排序

(一)箱排序

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

(二)基数排序

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

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