计算机二级公共基础知识总结|2017年计算机二级公共基础知识学习教程：排序技术

　　（八）排序技术

　　排序即是将一个无序的序列整理成按值非递减顺序排列的有序序列。在这里，我们讨论的是顺序存储的线性表的排序操作。

　　1．交换类排序法

　　交换类排序法，即是借助于数据元素之间的互相交换进行排序的方法。

　　1）冒泡排序法

　　冒泡排序法即是利用相邻数据元素之间的交换逐步将线性表变成有序序列的操作方法。

　　操作过程如下：

　　从表头开始扫描线性表，在扫描过程中逐次比较相邻两个元素的大小，若相邻两个元素中前一个元素的值比后一个元素的值大，将两个元素位置进行交换，当扫描完成一遍时，则序列中的元素被放置到序列的最后。

　　再继续对序列从头进行扫描，这一次扫描的长度是序列长度减1，因为的元素已经就位了，采用与前相同的方法，两两之间进行比较，将次大数移到子序列的末尾。

　　按相同的方法继续扫描，每次扫描的子序列的长度均比上一次减1，直至子序列的长度为1时，排序结束。

　　例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。

　　采用冒泡排序法，具体操作步骤如下：

　　序列长度n=7

　　扫描的次数，最多需要扫描n-1次，如果序列已经就位，则扫描结束。测试是否已经就位，可设置一个标志，如果该次扫描没有数据交换，则说明数据排序结束。

　　2）快速排序法

　　冒泡排序方法每次交换只能改变相邻两个元素之间的逆序，速度相对较慢。如果将两个不相邻的元素之间进行交换，可以消除多个逆序。

　　快速排序的方法是：

　　从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果将线性表分成两个部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。对过对线性表的一次分割，就以T为分界线，将线性表分成前后两个子表，且前面子表中的所有元素均不大于T，而后面的所有元素均不小于T。

　　再将前后两个子表再进行相同的快速排序，将子表再进行分割，直到所有的子表均为空，则完成快速排序操作。

　　在快速排序过程中，随着对各子表不断的进行分割，划分出的子表会越来越多，但一次又只能对一个子表进行分割处理，需要将暂时不用的子表记忆起来，这里可用栈来实现。

　　对某个子表进行分割后，可以将分割出的后一个子表的第一个元素与最后一个元素的位置压入栈中，而继续对前一个子表进行再分割；当分割出的子表为空时，可以从栈中退出一个子表进行分割。

　　这个过程直到栈为空为止，说明所有子表为空，没有子表再需分割，排序就完成。

　　2．插入类排序法

　　1）简单插入排序

　　插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。

　　插入排序操作的思路：在线性表中，只包含第1个元素的子表，作为该有序表。从线性表的第2个元素开始直到最后一个元素，逐次将其中的每一个元素插入到前面的有序的子表中。

　　该方法与冒泡排序方法的效率相同，最坏的情况下需要n(n-1)/2次比较。

　　例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。

　　采用简单插入排序法，具体操作步骤如下：

　　序列长度n=7

　　2）希尔排序法

　　希尔排序法的基本思想：

　　将整个无序序列分割成若干小的子序列分别进行插入排序。

　　子序列的分割方法：将相隔某个增量h的元素构成一个子序列，在排序的过程中，逐次减小这个增量，最后当h减小到1时，再进行一次插入排序操作，即完成排序。

　　增量序列一般取ht=n/2k(k=1,2,…,[log2n])，其中n为待排序序列的长度。

　　3．选择类排序法

　　1）简单选择排序法

　　基本思路：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对后面的子表采用相同的方法，直到子表为空为止。

　　对于长度为n的序列，需要扫描n-1次，每一次扫描均找出剩余的子表中最小的元素，然后将该最小元素与子表的第一个元素进行交换。

　　例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。

　　采用简单选择排序法，具体操作步骤如下：

　　2）堆排序法

　　堆排序法属于选择类排序方法。

　　堆的定义：具有n个元素的序列（h1,h2,…,hn），当且仅当满足时称之为堆。

　　本节只讨论满足前者条件的堆。

　　由堆的定义看，堆顶元素（即第一个元素）必为项。

　　可以用一维数组或完全二叉树来表示堆的结构。

　　用完全二叉树表示堆时，树中所有非叶子结点值均不小于其左右子树的根结点的值，因此堆顶（完全二叉树的根结点）元素必须为序列的n个元素中的项。

　　例如，有序列5、2、9、4、1、7、6，将该序列从小到大进行排列。

　　利用堆排序法将该序列进行排序。

　　操作方式即：先将无序堆的根结点5与左右子树的根结点2、9进行比较，5<9，将5与9进行交换；整后，对左右子树进行堆调整，左子树的根结点2小于其左叶子结点5，调整；右子树的根结点5小于其左右子结点7和6，根据堆的要求，将5与7进行调整。

　　根据堆的定义，可以得到堆排序的方法：

　　（1）首先将一个无序序列建成堆

　　（2）然后将堆顶元素（序列中的项）与堆中最后一个元素交换（项应该在序列的最后）。

　　二、本章应考点拨

　　本章内容在笔试中会出现5-6个题目，是公共基础知识部分出题量比较多的一章，所占分值也比较大，约10分。

本文来源：https://www.wddqw.com/TZUO.html