排序算法笔记,因为选择、冒泡、插入、希尔、归并、快速排序在复习的时候仅仅实现了而没记笔记,所以就从堆排序开始了?
一、Heap Sort(堆排序) 重点放在Heap 这种数据结构上,而非排序,排序只是堆的一个应用
1. 堆和优先队列,Heap and Priority Queue 普通队列:先进先出,后进后出,优先级按到来的时间顺序
优先队列:出队顺序和入队顺序无关,和优先级有关;操作系统执行任务的顺序就是一种优先队列 ,动态 选择优先级最高的任务来执行。 在优先队列中,任务会不断增加和减少,任务的优先级会实时变化。
在一些高级的优先队列中,除了随队列增减改变外,甚至已存在的任务的优先级也会随时变化,如操作系统的任务执行队列。
所以, 优先队列的执行顺序问题就是一个复杂的动态问题,靠一次排序无法解决,而实时的排序开销又很大。 那么我们为何不借用插入排序的思想,来维护一个本身就已经排好序的队列呢?这就涉及到了优先队列数据结构的选择: 对于总共的 N 个入队或出队请求:
使用普通数组 或顺序数组 ,最差情况的时间复杂度:O(n^2)
使用堆 :O(nlgn)
2. 堆的实现,The implement of Heap 二叉堆的两个性质:
必须是一颗完全二叉树(除了最后一层,其他层的节点个数必须达到最大,最后一层若没有填满,其节点需集中在左边)
任意一个节点的值总是不大于其父节点的值(最大堆,根是最大值)
这并不意味着上层节点的值一定大于下层节点,因为左子树 和右子树并未规定大小关系
二叉堆既然是一颗树的话,那么我们是不是应该用树来实现二叉堆呢?其实完全二叉树有一种经典的实现那就是数组,所以我们用数组来实现二叉堆。
用数组来实现二叉堆:
左节点的节点号是父节点的 2 倍
右节点的节点号是父节点的 2 倍加 1
节点编号除以 2 就是父节点(C++取整除法)
如果从 0 开始标号,上述规律会发生改变,如果想要使用原规律,我们可以从数组的 1 号位 开始存储根节点数据
Heap.h 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 #ifndef HEAPSORT_H #define HEAPSORT_H #include <iostream> #include <cassert> #include <algorithm> #include <cmath> template <typename Item>class MaxHeap { private : Item *data; int count; int capacity; void shiftUp (int ) ; void shiftDown (int ) ; public : MaxHeap (int capacity) : capacity (capacity), count (0 ) { data = new Item[capacity + 1 ]; } MaxHeap (const Item arr[], int n, int capacity) : capacity (capacity), count (n) { data = new Item[capacity + 1 ]; for (int i = 1 ; i <= n; i++) { data[i] = arr[i - 1 ]; } for (int i = count / 2 ; i >= 1 ; i--) { shiftDown (i); } } ~MaxHeap () { delete [] data; } bool isEmpty () const { return count == 0 ; } int size () const { return count; } void insert (Item item) { assert (count < capacity); data[++count] = item; shiftUp (count); } Item extractMax () { assert (!isEmpty ()); std::swap (data[1 ], data[count]); count--; shiftDown (1 ); return data[count + 1 ]; } std::ostream &show (std::ostream &os) const ; friend std::ostream &operator <<(std::ostream &os, const MaxHeap &maxHeap) { return maxHeap.show (os); } }; template <typename T>std::ostream &printNum (std::ostream &os, int n, T item) { for (int i = 0 ; i < n; i++) os << " " ; os << item; if (typeid (item).name () == "int" && item > 10 ) os << ' ' ; for (int i = 0 ; i < n; i++) os << " " ; os << " " ; return os; } template <typename Item>std::ostream &MaxHeap<Item>::show (std::ostream &os) const { int h = log2 (count); int lastFloor = pow (2 , h); int blankNum = lastFloor - 1 ; int rest = count; for (int i = 0 ; i <= h; i++) { int j; for (j = 0 ; j < fmin (rest, pow (2 , i)); j++) { printNum (os, blankNum, data[(int )pow (2 , i) + j]); } os << std::endl; blankNum /= 2 ; rest -= j; } return os; } template <typename Item>void MaxHeap<Item>::shiftUp (int k){ Item aux = data[k]; while (k / 2 >= 1 && data[k / 2 ] < aux) { data[k] = data[k / 2 ]; k /= 2 ; } data[k] = aux; } template <typename Item>void MaxHeap<Item>::shiftDown (int k){ Item aux = data[k]; while (2 * k <= count) { int j = 2 * k; if (j + 1 <= count && data[j + 1 ] > data[j]) j += 1 ; if (data[j] > aux) { data[k] = data[j]; k = j; } else break ; } data[k] = aux; } template <typename T>void heapSort (T array[], int n) { MaxHeap<T> maxHeap = MaxHeap<T>(array, n, n); for (int i = n - 1 ; i >= 0 ; i--) { array[i] = maxHeap.extractMax (); } } #endif
堆的关键操作:
void shiftUp(int k),O(logn)
void shiftDown(int k),O(logn)
根据数组生成堆(维护乱序堆),heapify
算法,从第一个非叶子节点 (从 1 开始编号的话,就是 count/2)开始按序号递减顺序依次进行 shiftDown ,O(n)
堆的维护就是靠shiftUp
和shiftDown
来实现:
当插入新的节点时,我们将节点置于二叉堆的最末尾,然后对该节点进行shiftUp
操作就可以完成插入;
当取出根节点时,我们将根节点与二叉堆的最后一个节点交换位置,然后对根节点进行shiftDown
操作就可以完成取出;shiftUp
操作只需要不断向父节点比较就可以了,但shiftDown
需要先选出子节点中较大的那一个 再进行比较;判断节点 k 是否有父节点if(k/2>=1)
,是否有子树if(2*k<=count)
3. 堆排序 通过构建上面的堆,我们可以很显然的得到一个排序的方法,使用 Heapify 算法构建一个 MaxHeap,然后依次取出根节点就行了,构建过程的时间复杂度是 O(n),依次取出 n 个根节点的排序过程是 O(nlogn)。这个排序可以在需要排序的原数组上完成,也可以新开辟一个二叉堆数组空间来完成。下面给出原地完成的算法:
heapSort.h 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 template <typename T>void shiftDownLocal (T array[], int k, int count) { T aux = array[k]; while (2 * k + 1 <= count - 1 ) { int j = 2 * k + 1 ; if (j + 1 <= count - 1 && array[j + 1 ] > array[j]) j += 1 ; if (aux < array[j]) { array[k] = array[j]; k = j; } else break ; } array[k] = aux; } template <typename T>void heapSortLocal (T array[], int n) { for (int i = n / 2 - 1 ; i >= 0 ; i--) { shiftDownLocal (array, i, n); } for (int i = 0 ; i < n; i++) { std::swap (array[0 ], array[n - 1 - i]); shiftDownLocal (array, 0 , n - 1 - i); } }
4. 更高级的索引堆 普通二叉堆的问题:
在使用 Heapify 算法来构建堆的过程,需要频繁进行元素交换,如果元素的构造比较复杂(比如每个元素都是十万字的文章),则会造成较大的开销
在建堆的过程中,元素的位置发生了改变,所以在建堆完成后,难以再索引到之前的元素,如果原始索引和数据之间存在特殊意义,那么建堆后这种特殊意义将会被破坏
比如操作系统的任务,数组索引是任务进程 id,而索引中的数据就是对应任务的优先级,在建堆后这种对应关系将会破坏
这些问题可以通过建立索引堆来解决:
索引堆的思想就是使用数据的索引来代替数据本身,用一个额外的数组来存储这些索引,然后对这些索引进行建堆,索引之间的大小比较就看索引指向的数据的大小
因为对索引进行建堆,所以为了方便的连接索引的父子节点,索引数组的计数可以从 1 开始,而数据数组不建堆,其数组的计数就可以从零开始
对用户而言,他们所看到的只是一个普通的数组
索引堆主要是为了解决索引带有特殊意义的优先队列问题,所以难免会遇到需要修改 data 数组特定编号下的内容的情况,当 data 数组某个编号下的值被修改后,索引堆需要对该值的索引进行一次shiftUp()
、shiftDown()
来维护堆,那么查找 data 数组的编号在索引堆的位置就是一个 O(n)时间级别的开销,我们可以用一个 rev 数组记录每个 data 数组编号在索引堆中的位置来将 O(n)时间上的开销转化为 O(n)空间上的开销
IndexMaxHeap.h 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 template <typename Item>class IndexMaxHeap { private : Item *data; int *index; int *rev; int count; int capacity; void changeIndex (int arrIndex, int arrData) { index[arrIndex] = arrData; rev[arrData] = arrIndex; } void shiftDown (int k) ; void shiftUp (int k) ; public : IndexMaxHeap (int capacity) : capacity (capacity), count (0 ) { data = new Item[capacity]; index = new int [capacity + 1 ]; rev = new int [capacity]; for (int i = 0 ; i < capacity; i++) { rev[i] = -1 ; index[i] = -1 ; } index[capacity] = -1 ; } IndexMaxHeap (Item array[], int n, int capacity) : capacity (capacity), count (n) { data = new Item[capacity]; index = new int [capacity + 1 ]; rev = new int [capacity]; for (int i = 0 ; i < capacity; i++) { rev[i] = -1 ; index[i] = -1 ; } index[capacity] = -1 ; for (int i = 0 ; i < count; i++) { data[i] = array[i]; changeIndex (i + 1 , i); } for (int i = count / 2 ; i >= 1 ; i--) { shiftDown (i); } } ~IndexMaxHeap () { delete [] data; delete [] index; delete [] rev; } bool isEmpty () const { return count == 0 ; } int size () const { return count; } Item extractMax () { assert (!isEmpty ()); int temp = index[1 ]; changeIndex (1 , index[count]); changeIndex (count, temp); count--; shiftDown (1 ); return data[index[count + 1 ]]; } void insert (int k, Item item) { assert (k < capacity); data[k] = item; count++; changeIndex (count, k); shiftUp (count); } void change (int k, Item item) { data[k] = item; shiftUp (rev[k]); shiftDown (rev[k]); } bool contain (int k) const { assert (k >= 1 && k <= capacity); return rev[k] >= 1 && rev[k] <= count; } }; template <typename Item>void IndexMaxHeap<Item>::shiftDown (int k){ Item aux = index[k]; while (2 * k <= count) { int j = 2 * k; if (j + 1 <= count && data[index[j + 1 ]] > data[index[j]]) j += 1 ; if (data[aux] >= data[index[j]]) break ; else { changeIndex (k, index[j]); k = j; } } changeIndex (k, aux); } template <typename Item>void IndexMaxHeap<Item>::shiftUp (int k){ Item aux = index[k]; while (k / 2 >= 1 && data[index[k / 2 ]] < data[aux]) { changeIndex (k, index[k / 2 ]); k /= 2 ; } changeIndex (k, aux); }
以上代码基本上实现了索引堆,但是还有一个小点没有实现,那就是extractMax()
中 data 数组数据没有删除,这个问题在普通二叉堆中不需要考虑,因为被取出的数据会移动到数组末尾,被排除在 count 之外; 而索引堆中,如果extractMax()
如果不将 data 数组数据删除,count 的意义在 data 数组上会失效,按上面的实现方法,在用户按规则insert(int k,Item item)
的情况下,data 数组的空间会无法有效利用; 这个问题有两种解决办法:
在extractMax()
过程中删除数组数据,然后 data 数组索引依次前移,对应索引堆中的数组编号依次减一,这个很简单实现,利用rev
快速查找到原编号所在的索引堆位置,利用changeIndex
函数将编号减一即可,但计算开销变大
在extractMax()
过程中删除数组数据,存储删除的位置到栈,下一次insert()
时,插入栈顶的位置,若栈空则插入到数组末尾,这样的做法计算开销小,但又需要一个数组的空间来作为栈
5. 和堆相关的问题
游戏中优先锁敌、操作系统中的优先任务调度、在 1,000,000 个元素中选出前 100 名
在 1,000,000(N)个元素中选出前 100(M)名,这个问题看似是O(MlogN)的时间复杂度, O(N)的空间复杂度,实际上可以做到 O(NlogM)的时间复杂度, O(M)的空间复杂度。 前者是 用 1,000,000 的数组构建最大堆 ,extraMax()
100 次; 后者是先用 100 的数组构建最小堆 ,然后遍历剩余的 999,900 个元素,每次insert()
一个新元素后都extraMin()
一个最小元素,最后就得到了最大的前 100 个元素
需要比较每一路中元素的大小,可以将每一路中开头的元素都放入最小堆中,每次extractMin()
一个元素后再insert()
该路的下一个元素
层数下降的代价是维护过程中需要更多次的比较,如shiftDown()
二、Sort Conclusion(排序总结) 1. 插入、归并、快速、堆排序比较
归并排序在合并时需要 O(n)大小的空间,快速排序因为有 O(logn)层的递归,每层递归都需要常数级别的空间来保存临时变量、返回地址等。
2. 排序算法的稳定性 插入排序,归并排序,冒泡排序 是稳定排序,其他常见排序都是不稳定的 :
快速排序随机选择标定点,如果后方的相等元素先被选择,且实现时,该元素最后被交换到了相等部分的前方,则稳定性被破坏。
选择排序涉及到大跨度的交换,例子:{10,10,7}
希尔排序也涉及到大跨度的交换,稳定性难以保障
插入排序和归并排序和冒泡排序的稳定性和等于号怎么处理关系很大,他们都可以实现成稳定排序
排序算法的稳定性问题可以通过重载<
来解决
三、 Every Implement of Sort(排序总表) 选择、冒泡、插入、希尔、归并、快速排序的实现代码比较多就不展开了,放上代码地址:
排序算法
时间复杂度(平均)
时间复杂度(最坏)
时间复杂度(最好)
空间复杂度
稳定性
选择排序
O(n2 )
O(n2 )
O(n2 )
O(1)
不稳定
冒泡排序
O(n2 )
O(n2 )
O(n)
O(1)
稳定
插入排序
O(n2 )
O(n2 )
O(n)
O(1)
稳定
希尔排序
O(nlog2 n)
O(n2 )
O(n1.3 )
O(1)
不稳定
归并排序
O(nlog2 n)
O(nlog2 n)
O(nlog2 n)
O(n)
稳定
快速排序
O(nlog2 n)
O(n2 )
O(nlog2 n)
O(log2 n)
不稳定
堆排序
O(nlog2 n)
O(nlog2 n)
O(nlog2 n)
O(1)
不稳定