saas建站没有网站源代码么,威县做网站哪儿便宜,南宁外贸网络营销,100个详情页设计图第十章内部排序
10.1 概述
排序就是把一组数据按关键字的大小有规律地排列。经过排序的数据更易于查找。 排序前KiKj#xff0c;且Ki在前:
排序方法是稳定的#xff0c;若排序后Ki在前#xff1b;
排序方法是不稳定的#xff0c;如排序后Kj在前。 分类#xff1a;
内…第十章内部排序
10.1 概述
排序就是把一组数据按关键字的大小有规律地排列。经过排序的数据更易于查找。 排序前KiKj且Ki在前:
排序方法是稳定的若排序后Ki在前
排序方法是不稳定的如排序后Kj在前。 分类
内部排序排序过程在内存中进行
外部排序待排序记录的数量很大内存一次不能容纳全部记录需要对外存进行访问。 内部排序每一种方法都有各自的优缺点适合在不同的环境下使用。 按不同原则进行分类
插入排序 直接插入排序 其他插入排序 希尔排序
交换排序 冒泡 快速排序
选择排序 简单选择排序 树形选择排序 堆排序
归并排序
基数排序 按时间复杂度划分
简单排序方法 n^2
先进排序方法 nlogn
基数排序方法 d*n 10.2 插入排序
10.2.1 直接插入排序
直接插入排序Straight Insertion Sort n^2
基本操作是将一个记录插入到已排好序的有序表中从而得到一个新的、记录数增一的有序表。 哨兵在0号位置值为待插入数据。 10.2.2 其他插入排序
当待排序记录的数量n很小时插入排序是一种很好的排序方法。
插入排序的改进从减少“比较”和“移动”这两种操作的次数出发。
1. 折半插入排序Binary Insertion Sort n^2
由于插入排序的基本操作是在一个有序表中进行查找和插入这个查找操作可利用折半查找来实现。
减少了比较次数移动次数不变。
2. 2-路插入排序
在折半插入的基础上再改进之其目的是减少排序过程中移动记录的次数但需要n个记录的辅助空间。
移动次数约为(n^2)/8。
若L.r[1]是最小或最大则2-路插入排序就失去其优越性。
循环数组1 mod length -1 plus length mod length 10.2.3 希尔排序 n^1.3
希尔排序Shell’s Sort又称“缩小增量排序”Diminishing Increment Sort
一种插入排序类方法但在时间效率上较前述排序方法有较大的改进。
基本思想
先将整个待排记录序列分割成若干子序列分别进行直接插入排序待整个序列中的记录“基本有序”时再对全体记录进行一次直接插入排序。
子序列的构成不是简单的“逐段分割”而是将相隔某个“增量”的记录组成一个子序列。 由于在前几趟的插入排序中记录的关键字是和同一子序列中的前一个记录的关键字进行比较因此关键字较小的记录不是一步一步地向前挪动而是跳跃式地往前移从而使得在最后一趟增量为1的插入排序时序列已基本有序只要作记录的少量比较和移动即可完成排序因此希尔排序的时间复杂度较直接插入排序低。
增量序列中的值只有公因子1并且最后一个增量值必须等于1。 10.3 快速排序
基于交换
起泡排序Bubble Sort
快速排序Quick Sort
基本思想
通过一趟排序将待排序记录分割成独立的两部分其中一部分记录的关键字均比另一部分记录的关键字小然后分别对这两部分记录继续进行排序已达到整个序列有序。
快速排序被认为是在所有同数量级nlogn的排序方法中其平均性能最好。 10.4 选择排序Selection Sort
10.4.1 简单选择排序Simple Selection Sort
10.4.2 树形选择排序Tree Selection Sort
又称锦标赛排序Tournament Sort
完全二叉树的层数
n个叶子结点的完全二叉树叶子结点表示关键字非叶子结点中的关键字等于左右孩子结点中较小的关键字根结点为最小关键字。
将最小关键字置为“最大值”然后从该叶子结点开始和其兄弟结点进行比较可选出次最小关键字。
依此类推。
缺点辅助存储空间较多和“最大值”进行多余比较。 10.4.3 堆排序Heap Sort
只需要一个记录大小的辅助空间每个待排序的记录仅占有一个存储空间。
堆n个元素的序列{K1, K2, ..., Kn}当且仅当满足以下关系时称之为堆。 若将和此序列对应的一维数组看成是一个完全二叉树则堆的含义表明完全二叉树中所有非终端结点的值均不小于其左右孩子结点的值大顶堆。由此堆顶元素必为序列中n个元素的最大值。 若在输出堆顶的最大值后使得剩余n-1个元素的序列又建成一个堆则得到n个元素的次大值。如此反复执行便能能得到一个有序序列这个过程称之为堆排序。 问题一如何在输出堆顶元素之后调整剩余元素成为一个新堆
输出堆顶元素后以堆中最后一个元素代替之。
此时根结点的左右子树均为堆则仅需自上而下进行调整即可。
称自堆顶至叶子的调整过程为“筛选”。
问题二如何由一个无序序列建成一个堆
从一个无序序列建堆的过程就是一个反复“筛选”的过程。
若将此序列看成一个完全二叉树则最后一个非终端结点是第个元素由此“筛选”只需从第个元素开始。 堆排序方法对记录数较少的文件并不值得提倡但对n较大的文件还是很有效的。
其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。 堆排序在最坏的情况下其时间复杂度也为nlogn。相对于快速排序来说这是堆排序的最大优点。此外堆排序仅需一个记录大小供交换用的辅助存储空间。 10.5 归并排序Merging Sort
“归并”的含义是将两个或两个以上的有序表组成一个新的有序表。
实现归并排序需和待排记录等数量的辅助空间其时间复杂度为nlogn。
递归形式的算法在形式上较简洁但实用性很差。
与快速排序和堆排序相比归并排序最大的特点是它是一种稳定的排序算法。
但在一般情况下很少使用二路归并排序法进行内部排序。 10.6 基数排序Radix Sorting
基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
最高位优先Most Significant Digit firstMSD
最低位优先Least Significant Digit firstLSD
链式基数排序
借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。 首先以静态链表存储n个待排记录并令表头指针指向第一个记录。
第一趟分配对最低位数的关键字进行将链表中的记录分配至Radix个链队列中去f[i] e[i]分别指向第i个队列的头指针和尾指针。
第一趟收集是将Radix个链队列串为一个链队列。
然后进行第二趟分配、第二趟收集、第三趟分配、第三趟收集、... 10.7 各种内部排序方法的比较 排序方法 平均时间 最坏情况 辅助存储 简单排序 n^2 n^2 1 快速排序 nlogn n^2 logn 堆排序 nlogn nlogn 1 归并排序 nlogn nlogn n 基数排序 d*n d*n rd 1从平均性能而言快速排序最佳其所需时间最省但快速排序在最坏情况下的时间性能不如堆排序和归并排序。
2在n较大时归并排序所需时间较堆排序少但它所需的辅助存储变量最多。
3直接插入排序最简单当基本有序或n值较小时它是最佳的排序方法因此常将其和其他排序方法诸如快速排序、归并排序等结合在一起使用。
4基数排序适用于n很大而关键字“位数”较小的序列。
5基数排序是稳定的内排方法。所有时间复杂度为O(n^2)的简单排序法也是稳定的。
快速排序、堆排序、希尔排序是不稳定的。 综上所述没有哪一种排序方法是绝对最优的在实际应用时根据不同情况适当选用甚至可将多种方法结合起来使用。 “地址排序”另设一个地址向量指示相应记录同时在排序过程中不移动记录而移动地址向量中相应分量的内容。
