输入数据的结构
在实际中, 待排序的数很少是孤立的值, 它们通常是一个称为记录的数据集的一部分每个记录有一个关键字 key, 它是待排序的值记录的其他数据称为卫星数据, 即它们通常以 key 为中心传送在一个排序的算法中, 当交换关键字时, 卫星数据也必须交换如果记录都很大, 我们可以交换一组指向各个记录的指针而不是记录本身, 以求将数据移动量减少到最小
在一定意义上, 正式这些实现细节才使得一个完整的程序不同于算法不管我们要排序的是单个的数值还是包含数据的大型记录, 就排序的方法来说它们都是一样的因为, 为了集中考虑排序问题, 我们一般都假设输入仅由数值构成将对数字的排序算法转换为对记录排序的程序是很直接的当然, 在具体的工程条件下, 实际的程序设计可能还会遇到其他难以捉摸的挑战
为什么要研究排序?
许多计算机科学家认为, 排序算法是算法学习中最基本的问题原因有以下几个:
有时候应用程序本身就需要对信息进行排序 e.g. 准本客户账目, 银行的支票号码
许多算法通常把排序作为关键子程序
现在已经有很多的排序算法, 它们采用各种技术事实上, 在算法设计中使用的很多重要技术在已经发展很多年的排序算法中早已用到了所以, 排序是一个具有历史意义的问题
在实现排序算法时很多工程问题即浮出水面对于某个特定的应用场景来说, 最快的排序算法可能与许多因素有关: 譬如关键字值和卫星数据的先验知识, 主机存储器层次结构 (高速缓存和虚拟存储) 以及软件环境
排序算法
插入排序: 最坏情况运行时间为(n^2), 但其算法的内循环时紧密的, 对小规模输入来说时一个快速的原地排序算法
合并排序: 有着较好的渐进运行时间(nlgn), 但其中的 Merge 程序不在原地操作
堆排序: 可以在 O(nlgn) 时间内对 n 个数进行原地排序这个算法用到了一种重要的称为堆的数据结构, 还要用它实现优先级队列
快速排序: 原地排序算法, 但最坏情况运行时间为 n^2, 平均运行时间是(nlgn), 在实际中常常优于堆排序算法对于大输入数组的排序来说, 这是一个很常用的算法
1-4 都是比较排序(comparison sort): 为研究比较排序算法的性能极限, 利用决策树模型, 证明对任何 n 个输入比较排序算法的最坏情况运行时间的下界为 nlgn, 说明堆排序和合并排序都是渐近最优的比较排序算法
第六章 堆排序
Heap Sort 将 Merge Sort 和 Insertion Sort 优点结合起来: 运行时间为 nlg(n)且 In place
6.1 堆
(二叉)堆数据结构是一种数组对象, 可以被视为一棵完全二叉树树中每个结点与数组中存放该结点值的那个元素对应树的每一层都是填满的, 最后一层可能除外(最后一层从一个结点的左子树开始填)
表示堆的数组 A 是一个具有两个属性的对象: length[A] 数组中的元素个数, heap-size[A]存放在 A 中的堆的元素个数
在树中, 给定了某个结点的下标 i, 则有:
- PARENT(i)
- return [i/2]
- LEFT(i)
- return 2i
- RIGHT(i)
- return 2i+1
在大多数计算机上,
LEFT 过程可以在一条指令内计算出 2i, 方法是将 i 的二进制表示左移 1 位
RIGHT 过程可以通过将 i 的二进制表示左移 1 位并在低位中加 1, 快速计算出 2i+1
PARENT 过程则可以通过把 i 右移 1 位而得到 i/2
在一个好的堆排序的实现中, 这三个过程通常是用宏过程或者是内联过程实现的
二叉堆有两种: 最大堆和最小堆 (小根堆) 在这两种堆中, 结点内的数值都要满足堆特性, 其细节则视堆的种类而定最大堆: 堆中的最大元素就存放在根结点中最小堆则反之
在堆排序算法中, 我们使用的是最大堆最小堆通常在构造优先队列时使用
MAX-HEAPIFY
- 运行时间为 O(lgn), 是保持最大堆性质的关键
BUILD-MAX-HEAP
- 线性时间运行, 可以在无序的输入数组基础上构造出最大堆
HEAPSORT
- 运行时间为 O(nlgn), 对一个数组原地进行排序
MAX-HEAP-INSERT,HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY, HEAP-MAXIMUM 过程的运行时间为 O(lgn), 可以让堆结构作为优先队列使用
6.2 保持堆的性质
MAX-HEAPIFY: 输入为一个数组 A 和下标 i, 当 MAX-HEAPIFY 被调用时, 我们假定以 LEFT(i)和 RIGHT(i)为根的两棵二叉树都是最大堆, 但这时 A[i]可能小于其子女, 这样就违反了最大堆的性质
- MAX-HEAPIFY(A, i)
- {
- var l = LEFT(i);
- var r = RIGHT(i);
- var largest = i;
- if l <= heap-size[A] and A[l]> A[i]
- then largest = l;
- if r <= heap-size[A] and A[r]> A[largest]
- then largest = r;
- if largest != i
- then swap(A[i], A[largest])
- MAX-HEAPIFY(A, largest)
- }
运行时间为 O(lgn), 或者说, MAX-HEAPIFY 作用于一个高度为 h 的结点所需的运行时间为 O(h)
6.3 建堆
我们可以自底向上地用 MAX-HEAPIFY 来将一个数组 A[1..n]变成一个最大堆
- BUILD-MAX-HEAP(A)
- {
- heap-size[A] = A.Length;
- for(int i = A.Length / 2; i>= 1; i)
- {
- MAX-HEAPIFY(A, i)
- }
- }
理想中, 我们每次调用 MAX-HEAPIFY 的时间为 O(lgn), 共有 O(n)次调用, 故运行时间是 O(nlgn), 这个界尽管是对的, 但从渐近意义上讲不够紧确
实际上, 我们可以得到一个更加紧确的界, 这是因为, 在树中不同高度的结点处运行 MAX-HEAPIFY 的时间不同, 而且大部分结点的高度都较小 O(n)
6.4 堆排序算法
开始时, 堆排序算法先用 BUILD-MAX-HEAP 将输入数组构造成一个最大堆; 因为数组中最大元素在根 A[1], 则可以通过把它与 A[n]互换来达到最终正确的位置现在, 如果从堆中去掉结点 n(通过减小 heap-size[A]), 可以很容易地将 A[1..n-1]建成最大堆
- HEAPSORT(A)
- {
- BUILD-MAX-HEAP(A)
- for(int i = A.Length; i> 2; i--)
- {
- swap(A[1], A[i]);
- heap-size[A] = heap-size[A]-1;
- MAX-HEAPIFY(A,1);
- }
- }
HEAPSORT 过程的时间代价为 O(nlgn)
6.5 优先级队列
虽然堆排序算法是一个很漂亮的算法, 但在实际中, 快速排序的一个好的实现往往优于堆排序
优先级队列是一种用来维护由一组元素构成的集合 S 的数据结构, 这一组元素中的每一个都有一个关键字 key 一个最大优先级队列支持以下操作:
- INSERT(S,x)
- MAXIMUM(S)
- EXTRACT-MAX(S)
- INCREASE-KEY(S,x,k)
最大优先级队列的一个应用是在一台分时计算机上进行作业调度这种队列对要执行的各作业及它们之间的相对优先关系加以记录当一个作业做完或被中断时, 用 EXTRACT-MAX 操作从所有等待的作业中, 选择出具有最高优先级的作业在任何时候, 一个新作业都可以用 INSERT 加入到队列中去
优先级队列可以用堆来实现在一个给定的, 诸如作业调度或事件驱动的模拟应用中, 优先级队列的元素对应着应用中的对象通常, 我们需要确定一个给定的队列中元素所对应的应用对象, 反之亦然当用堆来实现优先级队列时, 需要在堆中的每个元素里存储对应的应用对象的 Handle
HEAP-MAXIMUM 用 O(1)时间实现了 MAXIMUM 操作:
- HEAP-MAXIMUM(A)
- {
- return A[1];
- }
HEAP-EXTRACT-MAX 用 O(lgn)运行时间:(将最尾结点赋给首位, 将数组长度减一, 运行 MAX-HEAPIFY)
- HEAP-EXTRACT-MAX(A)
- {
- if heap-size[A] <1
- then error heap underflow;
- max = A[1];
- A[1] = A[heap-size[A]];
- heap-size[A] = heap-size[A] - 1;
- MAX-HEAPIFY(A, 1);
- return max;
- }
HEAP-INCREASE-KEY 运行时间 O(lgn):(从本结点往根结点移动的路径上, 不断与其父母相比, 若此元素关键字较大, 则交换它们的关键字并且继续移动; 若小于其父母, 则此时最大堆性质成立)
- HEAP-INCREASE-KEY(A,i,key)
- {
- if key < A[i]
- then error new key is smaller than current key;
- A[i] = key
- while i> 1 and A[PARENT(i)] <A[i]
- swap(A[i], A[PARENT(i)])
- i = PARENT(i)
- }
MAX-HEAP-INSERT 要实现 INSERT 操作, 可以加入一个关键值为负无穷的叶子结点来扩展最大堆, 然后调用 HEAP-INCREASE-KEY 来设置新结点的关键字的正确值, 并保持最大堆性质运行时间为 O(lgn)
- MAX-HEAP-INSERT(A,key)
- {
- heap-size[A] = heap-size[A] + 1;
- A[heap-size[A]] = -9999999999999999;
- HEAP-INCREASE-KEY(A, heap-size[A], key);
- }
第 7 章 快速排序
虽然最坏运行时间为 O(n^2), 但快速排序通常是用于排序的最佳实用选择, 这是因为其平均性能相当好: 期望的运行时间为 O(nlgn) , 另外它还能够进行就地排序, 在需存环境中也能很好地工作
- QUICKSORT(A, p, r)
- {
- if p> r
- then q = PARTITION(A, p, r);
- QUICKSORT(A, p, q-1);
- QUICKSORT(A, q+1, r);
- }
- PARTITION(A, p, r)
- {
- x = A[r];
- i = p - 1;
- for(var j = p; j < r-1; j++)
- {
- if(A[j] <= x)
- {
- i++;
- swap(A[i], A[j]);
- }
- }
- swap(A[i + 1], A[r]);
- return i + 1;
- }
第 8 章 线性时间排序
介绍了计数排序, 基数排序和桶排序这些算法都用非比较的一些操作来确定排序顺序因此下界 O(nlgn)对它们是不适用的
读书笔记 -- 算法导论(第二部分 排序和顺序统计学)
来源: http://www.bubuko.com/infodetail-2537910.html