排序技术概述.pptVIP

第8章 排 序 8.1 排序技术概述 从操作角度看，排序是线性结构的一种操作。 为了提高排序效率，人们已对排序进行了许多研究，提出了许多方法。 8.2 插入排序 插入排序 将待排序的序列分成两部分：前面为已经排好序的部分，后面为仍未排好序的部分。 每一轮都从没有排好序部分取出首元素按照大小将其插到前面已经排好序部分中的合适位置上。 这样前面已排序部分就多了一个元素，后面未排序部分同时少了一个元素。该排序过程不断进行，直到未排序部分的元素数目为零。 8.2.1 直接插入排序 8.2.2 折半插入排序 8.2.3 2_路插入排序 8.2.4 表插入排序 8.2.5 希尔排序 8.3 选择排序 选择排序是指在排序过程中的每一轮，按照某种方法选择出当前未排序部分中的最小值，把它放在已排序部分的首部，随着排序过程的进行，已排序部分变大，未排序部分变小。直到比较N-1轮之后，所有元素都在有序部分内，排序过程结束。 8.3.1 直接选择排序 (Straight selection sort) 直接选择排序，又称简单选择排序 N个元素进行直接选择排序的过程如下： 在第一轮，从下标为1的数组元素开始选出最小的元素，把它与数组下标为1的元素互换，这时已排序部分长度为1； 第二轮，从下标为2的数组元素开始在剩余的N-1个元素中选出最小的元素，让它与数组下标为2的元素互换，这时已排序部分长度为2； …… 8.3.2 堆排序 (Heap Sort) 最大堆与最小堆 如果完全二叉树各节点的关键字之间满足以下的关系，我们就称其为最大堆。 K≥Kleft和K≥Kright 其中K为某节点的关键字，Kleft为该节点左子（如果左子存在）的关键字，Kright为该节点右子（如果右子存在）的关键字。 8.4 交换排序  交换排序的基本方法是： 两两比较待排序元素，并交换不满足顺序要求的那些偶对，直到全部满足为止。 这里介绍两种交换排序，一种是最简单的冒泡排序(Bubble Sort)，另一种是效率很高的快速排序(Quick Sort)。 8.5 归并排序 8.6 基数排序 基数排序(Radix Sort)是我们最后讨论的一种内部排序算法，它与其他的内部排序算法思想有着很大的不同。前面几节我们介绍的各种排序方法都是以关键字的比较与数据的移动为主，但基数排序却主要借助“分配”和“收集”两种操作来完成排序任务。 8.7 外部排序概述 8.8 本章小结 如果换一种角度：在解决问题时，从较小的规模向较大的规模转换，即，先有两个已经排好序的子序列前后放置，然后再集中精力将它们归并成一个大的有序序列，用这种思路也同样可以完成排序的任务。 显然，这种归并排序(Merging Sort)仍旧是分治与递归思想的应用。 八个元素不断归并的过程: 图中第一轮准备归并的初始状态则是将原序列不断进行分解的结果:由8个元素一组分成4个元素一组，再分成2个元素一组，直到分成每个元素自己一组时，停止分解。 因为此时每组元素本身已经是有序的。在此基础上，才开始进行归并。 归并过程的具体实现思想在例2.2中已经介绍过，这里不再重复。 //归并排序。数组rec为待排序的序列，//count为排序元素的个数 void mergeSort(int rec[], int count) { sortMerging(rec,1,count); //调用递归函数完成归并排序,结 //果存在temp数组中 } //递归函数，完成归并排序 void sortMerging(int rec[], int 1ow , int high) { if(lowhigh) { int mid=(low+high)/2; sortMerging(rec,low,mid); sortMerging(rec,mid+1,high); merge(rec,low,mid,high); } } //实现两个有序序列的归并操作， //归并后的序列仍然保持有序 //rec中第一个序列的下标是从low到mid, //第二个序列的下标从mid+1到high void merge(int rec[], int low, int mid, int high) { int curr1,curr2,curr; //分别指向第一个序列