【软考】——排序算法

小鱼儿 2022-08-09 09:44 161阅读 0赞

**        所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。**

**![Center][]**

**排序包括两大类：内部排序和外部排序**

**内部排序：待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列，即元素个数少的排序中  
外部排序：指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的**

# **直接插入排序** #

**【是什么】：是一种简单的排序方法，基本思想是依次将记录插入到一个已排好序的有序表中，从而得到一个新的、记录数增加1的有序表  
例子：图书馆整理图书**

**![Center 1][]**

**【怎么用】**

![Center 2][]

** 【In  a word】将需要排序的数依次和已有表中的数据进行比较，按照从小到大的顺序插入到已有的表中**

# 直接选择排序 #

**【是什么】**

** 第一次从R\[0\]~R\[n-1\]中选取最小值，与R\[0\]交换，第二次从R\[1\]~R\[n-1\]中选取最小值，与R\[1\]交换，....，第i次从R\[i-1\]~R\[n-1\]中选取最小值，与R\[i-1\]交换，.....，第n-1次从R\[n-2\]~R\[n-1\]中选取最小值，与R\[n-2\]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列·**

**【怎么用】**

** 例如:给定n=8，数组R中的8个元素的排序码为(8,3,2,1,7,4,6,5),则直接选择排序的过程如下所示  
初始状态 \[ 8 3 21 7 4 6 5 \] 找到最小的值为 1  
第一次 \[ 1 3 2 8 7 4 6 5 \] 3和2交换位置  
第二次 \[ 1 2 38 7 4 6 5 \] 3 和3交换位置  
第三次 \[1 2 3 47 8 6 5\] 8 -- 4  
第四次 \[ 1 2 34 5 8 6 7 \] 7 -- 5  
第五次 \[ 1 2 34 5 6 8 7 \] 8 -- 6  
第六次 \[ 1 2 34 5 6 8 7 \] 8 -- 7  
第七次 \[ 1 2 34 5 6 7 8 \] 排序完成**

**【In  a word】**

**从需要排序的数中依次找到最小的数进行排序**。

# 冒泡排序 #

**【是什么】**

**它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。**

**【怎么用】**

![Center 3][]

**【In  a word】将第i-1个数和第i个数进行排序，如果第i-1个数大于第i个数，则两者进行交换位置**

# 快速排序 #

**【是什么】**

**通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。**

**【怎么用】**

**![Center 4][]**

**【In  a word】找到一个固定值（和别的数进行比较，一般选第一个数），得到的结果为左边比这个值小，右边的数比它大。**

# 堆排序 #

**【是什么】**

**堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A\[PARENT\[i\]\] >= A\[i\]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。**

**【怎么用】**

**![Center 5][]**

**【In  a word】分为最小堆和最大堆，其中最小堆为根为最小值，左右子树比根大，最大堆为根最大值，左右子树比根小**

# 归并排序 #

**【是什么】**

**将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。**

**【怎么用】**

**![Center 6][]**

**【In  a word】将要进行排序的数两两合并进行有序序列，再将序列两两合并，得到一个有序序列，依次反复，得到一个有序的序列为止。**

# **总结** #

**         一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范，要得到一个符合实际的优秀算法，得经过大量的推理和分析。这些只是最常用的几个算法，其中简单的介绍了各种算法的具体实现，随着接下来的学习，还会介绍其余算法的知识。**

[Center]: /images/20220731/af767cdde877419a8faeda09d92555ac.png
[Center 1]: /images/20220731/5431332394ea46eabec9ccbd941da062.png
[Center 2]: /images/20220731/aaeb3257228242eaae2a11da84589bc3.png
[Center 3]: /images/20220731/fe5870774bbe4d18b394b9533bcdd4a4.png
[Center 4]: /images/20220731/76981c74954f4e5e9082dac9a8e8d93b.png
[Center 5]: /images/20220731/bed696a143604e998225815477f74313.png
[Center 6]: /images/20220731/b1f8ba3b0ae0462b8b05220c0623a026.png