7.堆排序
原理：堆排序就是利用堆进行排序的方法.基本思想是:将待排序的序列构造成一个大顶堆.此时,整个序列的最大值就是堆顶 的根结点.将它移走(其实就是将其与堆数组的末尾元素交换, 此时末尾元素就是最大值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素的次大值.如此反复执行,便能得到一个有序序列了
时间复杂度：平均情况：O(nlog2n) 最好情况：O（nlog2n） 最坏情况：O（nlog2n）
空间复杂度：O（1）
稳定性：不稳定
//JavaScript 堆排序 var array = [23,0,32,45,56,75,43,0,34]; function heapSort(array) { for (var i = Math.floor(array.length / 2); i >= 0; i--) { heapAdjust(array, i, array.length - 1); //将数组array构建成一个大顶堆 } for (i = array.length - 1; i >= 0; i--) { /*把根节点交换出去*/ var temp = array[i]; array[i] = array[0]; array[0] = temp; /*余下的数组继续构建成大顶堆*/ heapAdjust(array, 0, i - 1); } return array; } function heapAdjust(array, start, max) { var temp = array[start];//temp是根节点的值 for (var j = 2 * start; j < max; j *= 2) { if (j < max && array[j] < array[j + 1]) { //取得较大孩子的下标 ++j; } if (temp >= array[j]) break; array[start] = array[j]; start = j; } array[start] = temp; } var newArray = heapSort(array); console.log(newArray);
<?php //堆排序 function heapSort(&$arr) { #初始化大顶堆 initHeap($arr, 0, count($arr) - 1); #开始交换首尾节点,并每次减少一个末尾节点再调整堆,直到剩下一个元素 for($end = count($arr) - 1; $end > 0; $end--) { $temp = $arr[0]; $arr[0] = $arr[$end]; $arr[$end] = $temp; ajustNodes($arr, 0, $end - 1); } } #初始化最大堆,从最后一个非叶子节点开始,最后一个非叶子节点编号为 数组长度/2 向下取整 function initHeap(&$arr) { $len = count($arr); for($start = floor($len / 2) - 1; $start >= 0; $start--) { ajustNodes($arr, $start, $len - 1); } } #调整节点 #@param $arr 待调整数组 #@param $start 调整的父节点坐标 #@param $end 待调整数组结束节点坐标 function ajustNodes(&$arr, $start, $end) { $maxInx = $start; $len = $end + 1; #待调整部分长度 $leftChildInx = ($start + 1) * 2 - 1; #左孩子坐标 $rightChildInx = ($start + 1) * 2; #右孩子坐标 #如果待调整部分有左孩子 if($leftChildInx + 1 <= $len) { #获取最小节点坐标 if($arr[$maxInx] < $arr[$leftChildInx]) { $maxInx = $leftChildInx; } #如果待调整部分有右子节点 if($rightChildInx + 1 <= $len) { if($arr[$maxInx] < $arr[$rightChildInx]) { $maxInx = $rightChildInx; } } } #交换父节点和最大节点 if($start != $maxInx) { $temp = $arr[$start]; $arr[$start] = $arr[$maxInx]; $arr[$maxInx] = $temp; #如果交换后的子节点还有子节点,继续调整 if(($maxInx + 1) * 2 <= $len) { ajustNodes($arr, $maxInx, $end); } } } $arr = array(23,0,32,45,56,75,43,0,34); heapSort($arr); var_dump($arr); ?>
8.基数排序
原理：将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
时间复杂度：平均情况：O(d(r+n)) 最好情况：O（d(n+rd)） 最坏情况：O（d(r+n)） r:关键字的基数 d:长度 n:关键字个数
空间复杂度：O（rd+n）
稳定性：稳定