Tips: 同选择排序相似, 快速排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序. 因此, 快速排序并不稳定.
堆排序1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd) 和威廉姆斯(J．Williams) 在1964年共同发明了著名的堆排序算法(Heap Sort).
堆排序是利用堆这种数据结构所设计的一种排序算法. 它是选择排序的一种. 堆分为大根堆和小根堆. 大根堆要求每个子节点的值都不大于其父节点的值, 即array[childIndex] <= array[parentIndex], 最大的值一定在堆顶. 小根堆与之相反, 即每个子节点的值都不小于其父节点的值, 最小的值一定在堆顶. 因此我们可使用大根堆进行升序排序, 使用小根堆进行降序排序.
并非所有的序列都是堆, 对于序列k1, k2,…kn, 需要满足如下条件才行:
ki <= k(2i) 且 ki<=k(2i+1)(1≤i≤ n/2), 即为小根堆, 将<=换成>=, 那么则是大根堆. 我们可以将这里的堆看作完全二叉树, k(i) 相当于是二叉树的非叶子节点, k(2i) 则是左子节点, k(2i+1)是右子节点.
算法的基本思想(以大根堆为例):
先将初始序列K[1..n]建成一个大根堆, 此堆为初始的无序区.
再将关键字最大的记录K (即堆顶)和无序区的最后一个记录K[n]交换, 由此得到新的无序区K[1..n-1]和有序区K[n], 且满足K[1..n-1].keys≤K[n].key
交换K 和 K[n] 后, 堆顶可能违反堆性质, 因此需将K[1..n-1]调整为堆. 然后重复步骤2, 直到无序区只有一个元素时停止.
如下是动图效果:
如下是算法实现:
function heapAdjust(array, i, length) {//堆调整 var left = 2 * i + 1, right = 2 * i + 2, largest = i; if (left < length && array[largest] < array[left]) { largest = left; } if (right < length && array[largest] < array[right]) { largest = right; } if (largest != i) { swap(i, largest, array); heapAdjust(array, largest, length); } } function heapSort(array) { //建立大顶堆 length = array.length; for (var i = length>>1; i >= 0; i--) { heapAdjust(array, i, length); } //调换第一个与最后一个元素,重新调整为大顶堆 for (var i = length - 1; i > 0; i--) { swap(0, i, array); heapAdjust(array, 0, --length); } return array; }
以上, ①建立堆的过程, 从length/2 一直处理到0, 时间复杂度为O(n);
②调整堆的过程是沿着堆的父子节点进行调整, 执行次数为堆的深度, 时间复杂度为O(lgn);
③堆排序的过程由n次第②步完成, 时间复杂度为O(nlgn).
Tips: 由于堆排序中初始化堆的过程比较次数较多, 因此它不太适用于小序列. 同时由于多次任意下标相互交换位置, 相同元素之间原本相对的顺序被破坏了, 因此, 它是不稳定的排序.
计数排序计数排序几乎是唯一一个不基于比较的排序算法, 该算法于1954年由 Harold H. Seward 提出. 使用它处理一定范围内的整数排序时, 时间复杂度为O(n+k), 其中k是整数的范围, 它几乎比任何基于比较的排序算法都要快( 只有当O(k)>O(n*log(n))的时候其效率反而不如基于比较的排序, 如归并排序和堆排序).
使用计数排序需要满足如下条件:
待排序的序列全部为整数
排序需要额外的存储空间
算法的基本思想:
计数排序利用了一个特性, 对于数组的某个元素, 一旦知道了有多少个其它元素比它小(假设为m个), 那么就可以确定出该元素的正确位置(第m+1位)
获取待排序数组A的最大值, 最小值.
将最大值与最小值的差值+1作为长度新建计数数组B，并将相同元素的数量作为值存入计数数组.
对计数数组B累加计数, 存储不同值的初始下标.
从原数组A挨个取值, 赋值给一个新的数组C相应的下标, 最终返回数组C.
注意: 如果原数组A是包含若干个对象的数组，需要基于对象的某个属性进行排序，那么算法开始时，需要将原数组A处理为一个只包含对象属性值的简单数组simpleA, 接下来便基于simpleA进行计数、累加计数, 其它同上.
如下是动图效果:
如下是算法实现: