江苏龙网

  1. 首页 > 人文 > >

十大经典排序算法（动图演示）( 四 )

< len 17}1819if(right < len 21}2223if(largest != i) {24swap(arr, i, largest);25heapify(arr, largest);26}27 }2829 function swap(arr, i, j) {30vartemp = arr[i];31arr[i] = arr[j];32arr[j] = temp;33 }3435 function heapSort(arr) {36buildMaxHeap(arr);3738for(vari = arr.length - 1; i > 0; i--) {39swap(arr, 0, i);40len--;41heapify(arr, 0);42}43returnarr;44 }8.4 算法分析计数排序是一个稳定的排序算法 。 当输入的元素是 n 个 0到 k 之间的整数时 ， 时间复杂度是O(n+k) ， 空间复杂度也是O(n+k) ， 其排序速度快于任何比较排序算法 。 当k不是很大并且序列比较集中时 ， 计数排序是一个很有效的排序算法 。 9、桶排序（Bucket Sort）桶排序是计数排序的升级版 。 它利用了函数的映射关系 ， 高效与否的关键就在于这个映射函数的确定 。 桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布 ， 将数据分到有限数量的桶里 ， 每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排） 。 9.1 算法描述

  • 设置一个定量的数组当作空桶；
  • 遍历输入数据 ， 并且把数据一个一个放到对应的桶里去；
  • 对每个不是空的桶进行排序；
  • 从不是空的桶里把排好序的数据拼接起来 。
9.2 图片演示9.3 代码实现 1 function countingSort(arr, maxValue) { 2varbucket = newArray(maxValue + 1), 3sortedIndex = 0; 4arrLen = arr.length, 5bucketLen = maxValue + 1; 67for(vari = 0; i < arrLen; i++) { 8if(!bucket[arr[i]]) { 9bucket[arr[i]] = 0;10}11bucket[arr[i]]++;12}1314for(varj = 0; j < bucketLen; j++) {15while(bucket[j] > 0) {16arr[sortedIndex++] = j;17bucket[j]--;18}19}2021returnarr;22 }9.4 算法分析桶排序最好情况下使用线性时间O(n) ， 桶排序的时间复杂度 ， 取决与对各个桶之间数据进行排序的时间复杂度 ， 因为其它部分的时间复杂度都为O(n) 。 很显然 ， 桶划分的越小 ， 各个桶之间的数据越少 ， 排序所用的时间也会越少 。 但相应的空间消耗就会增大 。10、基数排序（Radix Sort）基数排序是按照低位先排序 ， 然后收集；再按照高位排序 ， 然后再收集；依次类推 ， 直到最高位 。 有时候有些属性是有优先级顺序的 ， 先按低优先级排序 ， 再按高优先级排序 。 最后的次序就是高优先级高的在前 ， 高优先级相同的低优先级高的在前 。 10.1 算法描述
  • 取得数组中的最大数 ， 并取得位数；
  • arr为原始数组 ， 从最低位开始取每个位组成radix数组；
  • 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
10.2 动图演示 10.3 代码实现 1 function bucketSort(arr, bucketSize) { 2if(arr.length === 0) { 3returnarr; 4} 56vari; 7varminValue = http://kandian.youth.cn/index/arr[0]; 8varmaxValue = arr[0]; 9for(i = 1; i < arr.length; i++) {10if(arr[i] < minValue) {11minValue = arr[i];// 输入数据的最小值12} elseif(arr[i]> maxValue) {13maxValue = http://kandian.youth.cn/index/arr[i];// 输入数据的最大值14}15}1617// 桶的初始化18varDEFAULT_BUCKET_SIZE = 5;// 设置桶的默认数量为519bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;20varbucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;21varbuckets = newArray(bucketCount);22for(i = 0; i < buckets.length; i++) {23buckets[i] = [];24}2526// 利用映射函数将数据分配到各个桶中27for(i = 0; i < arr.length; i++) {28buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);29}3031arr.length = 0;32for(i = 0; i


推荐阅读


上一篇：SpringBoot整合JWT+Shiro

下一篇：厉害的何止华为！中兴突然“亮剑”，国产芯片再传捷报