JS基础算法总结

2019年12月07日 阅读数:100
这篇文章主要向大家介绍JS基础算法总结,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

排序算法说明

(1)排序的定义:对一序列对象根据某个关键字进行排序;html

输入:n个数:a1,a2,a3,…,an
输出:n个数的排列:a1’,a2’,a3’,…,an’,使得a1’<=a2’<=a3’<=…<=an’。git

再讲的形象点就是排排坐,调座位,高的站在后面,矮的站在前面咯。github

(3)对于评述算法优劣术语的说明算法

稳定:若是a本来在b前面,而a=b,排序以后a仍然在b的前面;
不稳定:若是a本来在b的前面,而a=b,排序以后a可能会出如今b的后面;sql

内排序:全部排序操做都在内存中完成;
外排序:因为数据太大,所以把数据放在磁盘中,而排序经过磁盘和内存的数据传输才能进行;shell

时间复杂度: 一个算法执行所耗费的时间。
空间复杂度: 运行完一个程序所需内存的大小。api

关于时间空间复杂度的更多了解请戳这里,或是看书程杰大大编写的《大话数据结构》仍是很赞的,通俗易懂。数组

(4)排序算法图片总结(图片来源于网络):网络

排序对比:数据结构

这里写图片描述

图片名词解释:
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存,不占用额外内存
Out-place: 占用额外内存

排序分类:

这里写图片描述

1.冒泡排序(Bubble Sort)

好的,开始总结第一个排序算法,冒泡排序。我想对于它每一个学过C语言的都会了解的吧,这多是不少人接触的第一个排序算法。

(1)算法描述

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,若是它们的顺序错误就把它们交换过来。走访数列的工做是重复地进行直到没有再须要交换,也就是说该数列已经排序完成。这个算法的名字由来是由于越小的元素会经由交换慢慢“浮”到数列的顶端。

(2)算法描述和实现

具体算法描述以下:

<1>.比较相邻的元素。若是第一个比第二个大,就交换它们两个; <2>.对每一对相邻元素做一样的工做,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数; <3>.针对全部的元素重复以上的步骤,除了最后一个; <4>.重复步骤1~3,直到排序完成。

JavaScript代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function bubbleSort(arr) {
     var len = arr.length;
     for (var i = 0; i < len; i++) {
         for (var j = 0; j < len - 1 - i; j++) {
             if (arr[j] > arr[j+1]) {        //相邻元素两两对比
                 var temp = arr[j+1];        //元素交换
                 arr[j+1] = arr[j];
                 arr[j] = temp ;
             }
         }
     }
     return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

改进冒泡排序: 设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。因为pos位置以后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置便可。

改进后算法以下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function bubbleSort2(arr) {
     console. time ( '改进后冒泡排序耗时' );
     var i = arr.length-1;  //初始时,最后位置保持不变
     while ( i> 0) {
         var pos= 0; //每趟开始时,无记录交换
         for (var j= 0; j< i; j++)
             if (arr[j]> arr[j+1]) {
                 pos= j; //记录交换的位置
                 var tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
             }
         i= pos; //为下一趟排序做准备
      }
      console.timeEnd( '改进后冒泡排序耗时' );
      return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

传统冒泡排序中每一趟排序操做只能找到一个最大值或最小值,咱们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次能够获得两个最终值(最大者和最小者) , 从而使排序趟数几乎减小了一半。

改进后的算法实现为:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort3(arr3) {
     var low = 0;
     var high= arr.length-1; //设置变量的初始值
     var tmp,j;
     console. time ( '2.改进后冒泡排序耗时' );
     while (low < high) {
         for (j= low; j< high; ++j) //正向冒泡,找到最大者
             if (arr[j]> arr[j+1]) {
                 tmp = arr[j]; arr[j]=arr[j+1];arr[j+1]=tmp;
             }
         --high;                 //修改high值, 前移一位
         for (j=high; j>low; --j) //反向冒泡,找到最小者
             if (arr[j]<arr[j-1]) arr= "[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];" pre= "" return = "" tmp= "arr[j];" var= "" >

三种方法耗时对比:

这里写图片描述

由图能够看出改进后的冒泡排序明显的时间复杂度更低,耗时更短了。读者自行尝试能够戳这,博主在github建了个库,读者能够Clone下来本地尝试。此博文配合源码体验更棒哦~~~

冒泡排序动图演示:<喎�"/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjwvcD4NCjxwPjxpbWcgYWx0PQ=="这里写图片描述" src="/uploadfile/Collfiles/20160918/20160918092143582.gif" title="\" />

(3)算法分析

最佳状况:T(n) = O(n)

当输入的数据已是正序时(都已是正序了,为毛何须还排序呢….)

最差状况:T(n) = O(n2)

当输入的数据是反序时(卧槽,我直接反序不就完了….)

平均状况:T(n) = O(n2)

2.选择排序(Selection Sort)

表现最稳定的排序算法之一(这个稳定不是指算法层面上的稳定哈,相信聪明的你能明白我说的意思2333),由于不管什么数据进去都是O(n2)的时间复杂度…..因此用到它的时候,数据规模越小越好。惟一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序通常人想到的最多的排序方法了吧。

(1)算法简介

选择排序(Selection-sort)是一种简单直观的排序算法。它的工做原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,而后,再从剩余未排序元素中继续寻找最小(大)元素,而后放到已排序序列的末尾。以此类推,直到全部元素均排序完毕。

(2)算法描述和实现

n个记录的直接选择排序可通过n-1趟直接选择排序获得有序结果。具体算法描述以下:

<1>.初始状态:无序区为R[1..n],有序区为空; <2>.第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增长1个的新有序区和记录个数减小1个的新无序区; <3>.n-1趟结束,数组有序化了。

Javascript代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function selectionSort(arr) {
     var len = arr.length;
     var minIndex, temp ;
     console. time ( '选择排序耗时' );
     for (var i = 0; i < len - 1; i++) {
         minIndex = i;
         for (var j = i + 1; j < len; j++) {
             if (arr[j] < arr[minIndex]) {     //寻找最小的数
                 minIndex = j;                 //将最小数的索引保存
             }
         }
         temp = arr[i];
         arr[i] = arr[minIndex];
         arr[minIndex] = temp ;
     }
     console.timeEnd( '选择排序耗时' );
     return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

选择排序动图演示:

这里写图片描述

(3)算法分析

最佳状况:T(n) = O(n2) 最差状况:T(n) = O(n2) 平均状况:T(n) = O(n2)

3.插入排序(Insertion Sort)

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,由于只要打过扑克牌的人都应该可以秒懂。固然,若是你说你打扑克牌摸牌的时候历来不按牌的大小整理牌,那估计这辈子你对插入排序的算法都不会产生任何兴趣了…..

(1)算法简介

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工做原理是经过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,一般采用in-place排序(即只需用到O(1)的额外空间的排序),于是在从后向前扫描过程当中,须要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

(2)算法描述和实现

通常来讲,插入排序都采用in-place在数组上实现。具体算法描述以下:

<1>.从第一个元素开始,该元素能够认为已经被排序; <2>.取出下一个元素,在已经排序的元素序列中从后向前扫描; <3>.若是该元素(已排序)大于新元素,将该元素移到下一位置; <4>.重复步骤3,直到找到已排序的元素小于或者等于新元素的位置; <5>.将新元素插入到该位置后; <6>.重复步骤2~5。

Javascript代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function insertionSort(array) {
     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' ) {
         console. time ( '插入排序耗时:' );
         for (var i = 1; i < array.length; i++) {
             var key = array[i];
             var j = i - 1;
             while (j >= 0 && array[j] > key ) {
                 array[j + 1] = array[j];
                 j --;
             }
             array[j + 1] = key ;
         }
         console.timeEnd( '插入排序耗时:' );
         return array;
     } else {
         return 'array is not an Array!' ;
     }
}

改进插入排序: 查找插入位置时使用二分查找的方式

?
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
function binaryInsertionSort(array) {
     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' ) {
         console. time ( '二分插入排序耗时:' );
 
         for (var i = 1; i < array.length; i++) {
             var key = array[i], left = 0, right = i - 1;
             while ( left <= right ) {
                 var middle = parseInt(( left + right ) / 2);
                 if ( key < array[middle]) {
                     right = middle - 1;
                 } else {
                     left = middle + 1;
                 }
             }
             for (var j = i - 1; j >= left ; j --) {
                 array[j + 1] = array[j];
             }
             array[ left ] = key ;
         }
         console.timeEnd( '二分插入排序耗时:' );
 
         return array;
     } else {
         return 'array is not an Array!' ;
     }
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(binaryInsertionSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

改进先后对比:

这里写图片描述

插入排序动图演示:

这里写图片描述

(3)算法分析

最佳状况:输入数组按升序排列。T(n) = O(n) 最坏状况:输入数组按降序排列。T(n) = O(n2) 平均状况:T(n) = O(n2)

4.希尔排序(Shell Sort)

1959年Shell发明; 第一个突破O(n^2)的排序算法;是简单插入排序的改进版;它与插入排序的不一样之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

(1)算法简介

希尔排序的核心在于间隔序列的设定。既能够提早设定好间隔序列,也能够动态的定义间隔序列。动态定义间隔序列的算法是《算法(第4版》的合著者Robert Sedgewick提出的。

(2)算法描述和实现

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:

<1>. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1; <2>.按增量序列个数k,对序列进行k 趟排序; <3>.每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列做为一个表来处理,表长度即为整个序列的长度。

Javascript代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function shellSort(arr) {
     var len = arr.length,
         temp ,
         gap = 1;
     console. time ( '希尔排序耗时:' );
     while(gap < len/5) {          //动态定义间隔序列
         gap =gap*5+1;
     }
     for (gap; gap > 0; gap = Math.floor(gap/5)) {
         for (var i = gap; i < len; i++) {
             temp = arr[i];
             for (var j = i-gap; j >= 0 && arr[j] > temp ; j-=gap) {
                 arr[j+gap] = arr[j];
             }
             arr[j+gap] = temp ;
         }
     }
     console.timeEnd( '希尔排序耗时:' );
     return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

希尔排序图示(图片来源网络):

这里写图片描述

(3)算法分析

最佳状况:T(n) = O(nlog2 n) 最坏状况:T(n) = O(nlog2 n) 平均状况:T(n) =O(nlog n)

5.归并排序(Merge Sort)

和选择排序同样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,由于始终都是O(n log n)的时间复杂度。代价是须要额外的内存空间。

(1)算法简介

 归并排序是创建在归并操做上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个很是典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,获得彻底有序的序列;即先使每一个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

(2)算法描述和实现

具体算法描述以下:

<1>.把长度为n的输入序列分红两个长度为n/2的子序列; <2>.对这两个子序列分别采用归并排序; <3>.将两个排序好的子序列合并成一个最终的排序序列。

Javscript代码实现:

?
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
function mergeSort(arr) {  //采用自上而下的递归方法
     var len = arr.length;
     if(len < 2) {
         return arr;
     }
     var middle = Math.floor(len / 2),
         left = arr.slice(0, middle),
         right = arr.slice(middle);
     return merge(mergeSort( left ), mergeSort( right ));
}
 
function merge( left , right )
{
     var result = [];
     console. time ( '归并排序耗时' );
     while ( left .length && right .length) {
         if ( left [0] <= right [0]) {
             result.push( left .shift());
         } else {
             result.push( right .shift());
         }
     }
 
     while ( left .length)
         result.push( left .shift());
 
     while ( right .length)
         result.push( right .shift());
     console.timeEnd( '归并排序耗时' );
     return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));

归并排序动图演示:

这里写图片描述

(3)算法分析

最佳状况:T(n) = O(n) 最差状况:T(n) = O(nlogn) 平均状况:T(n) = O(nlogn)

6.快速排序(Quick Sort)

快速排序的名字起的是简单粗暴,由于一听到这个名字你就知道它存在的意义,就是快,并且效率高! 它是处理大数据最快的排序算法之一了。

(1)算法简介

快速排序的基本思想:经过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另外一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

(2)算法描述和实现

快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述以下:

<1>.从数列中挑出一个元素,称为 “基准”(pivot); <2>.从新排序数列,全部元素比基准值小的摆放在基准前面,全部元素比基准值大的摆在基准的后面(相同的数能够到任一边)。在这个分区退出以后,该基准就处于数列的中间位置。这个称为分区(partition)操做; <3>.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

Javascript代码实现:

?
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
/*方法说明:快速排序
@param  array 待排序数组*/
//方法一
function quickSort(array, left , right ) {
     console. time ( '1.快速排序耗时' );
     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number' ) {
         if ( left < right ) {
             var x = array[ right ], i = left - 1, temp ;
             for (var j = left ; j <= right ; j++) {
                 if (array[j] <= x) {
                     i++;
                     temp = array[i];
                     array[i] = array[j];
                     array[j] = temp ;
                 }
             }
             quickSort(array, left , i - 1);
             quickSort(array, i + 1, right );
         }
         console.timeEnd( '1.快速排序耗时' );
         return array;
     } else {
         return 'array is not an Array or left or right is not a number!' ;
     }
}
 
//方法二
var quickSort2 = function (arr) {
     console. time ( '2.快速排序耗时' );
  if (arr.length <= 1) { return arr; }
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
   for (var i = 0; i < arr.length; i++){
    if (arr[i] < pivot) {
       left .push(arr[i]);
    } else {
       right .push(arr[i]);
    }
  }
console.timeEnd( '2.快速排序耗时' );
   return quickSort2( left ).concat([pivot], quickSort2( right ));
};
 
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr,0,arr.length-1));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
console.log(quickSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

快速排序动图演示:

快速排序

(3)算法分析

最佳状况:T(n) = O(nlogn) 最差状况:T(n) = O(n2) 平均状况:T(n) = O(nlogn)

7.堆排序(Heap Sort)

堆排序能够说是一种利用堆的概念来排序的选择排序。

(1)算法简介

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似彻底二叉树的结构,并同时知足堆积的性质:即子结点的键值或索引老是小于(或者大于)它的父节点。

(2)算法描述和实现

具体算法描述以下:

<1>.将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区; <2>.将堆顶元素R[1]与最后一个元素R[n]交换,此时获得新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且知足R[1,2…n-1]<=R[n]; <3>.因为交换后新的堆顶R[1]可能违反堆的性质,所以须要对当前无序区(R1,R2,……Rn-1)调整为新堆,而后再次将R[1]与无序区最后一个元素交换,获得新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

Javascript代码实现:

?
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
/*方法说明:堆排序
@param  array 待排序数组*/
function heapSort(array) {
     console. time ( '堆排序耗时' );
     if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' ) {
         //建堆
         var heapSize = array.length, temp ;
         for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i --) {
             heapify(array, i, heapSize);
         }
 
         //堆排序
         for (var j = heapSize - 1; j >= 1; j --) {
             temp = array[0];
             array[0] = array[j];
             array[j] = temp ;
             heapify(array, 0, --heapSize);
         }
         console.timeEnd( '堆排序耗时' );
         return array;
     } else {
         return 'array is not an Array!' ;
     }
}
/*方法说明:维护堆的性质
@param  arr 数组
@param  x   数组下标
@param  len 堆大小*/
function heapify(arr, x, len) {
     if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number' ) {
         var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp ;
         if (l < len && arr[l] > arr[largest]) {
             largest = l;
         }
         if (r < len && arr[r] > arr[largest]) {
             largest = r;
         }
         if (largest != x) {
             temp = arr[x];
             arr[x] = arr[largest];
             arr[largest] = temp ;
             heapify(arr, largest, len);
         }
     } else {
         return 'arr is not an Array or x is not a number!' ;
     }
}
var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
console.log(heapSort(arr));//[10, 13, 20, 22, 30, 31, 35, 46, 60, 65, 65, 77, 81, 91, 96]

堆排序动图演示:

这里写图片描述

(3)算法分析

最佳状况:T(n) = O(nlogn) 最差状况:T(n) = O(nlogn) 平均状况:T(n) = O(nlogn)

8.计数排序(Counting Sort)

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 做为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有肯定范围的整数。

(1)算法简介

计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。而后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

(2)算法描述和实现

具体算法描述以下:

<1>. 找出待排序的数组中最大和最小的元素; <2>. 统计数组中每一个值为i的元素出现的次数,存入数组C的第i项; <3>. 对全部的计数累加(从C中的第一个元素开始,每一项和前一项相加); <4>. 反向填充目标数组:将每一个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

Javascript代码实现:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function countingSort(array) {
     var len = array.length,
         B = [],
         C = [],
         min = max = array[0];
     console. time ( '计数排序耗时' );
     for (var i = 0; i < len; i++) {
         min = min <= array[i] ? min : array[i];
         max = max >= array[i] ? max : array[i];
         C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;
     }
     for (var j = min ; j < max ; j++) {
         C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
     }
     for (var k = len - 1; k >= 0; k --) {
         B[C[array[k]] - 1] = array[k];
         C[array[k]] --;
     }
     console.timeEnd( '计数排序耗时' );
     return B;
}
var arr = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log(countingSort(arr)); //[1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 4, 4, 6, 7, 7, 8, 8, 9, 9]

JavaScript动图演示:

这里写图片描述

(3)算法分析

当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。因为用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,须要大量时间和内存。

最佳状况:T(n) = O(n+k) 最差状况:T(n) = O(n+k) 平均状况:T(n) = O(n+k)

9.桶排序(Bucket Sort)

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的肯定。

(1)算法简介

桶排序 (Bucket sort)的工做的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每一个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排

(2)算法描述和实现

具体算法描述以下:

<1>.设置一个定量的数组看成空桶; <2>.遍历输入数据,而且把数据一个一个放到对应的桶里去; <3>.对每一个不是空的桶进行排序; <4>.从不是空的桶里把排好序的数据拼接起来。

Javascript代码实现:

?
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
/*方法说明:桶排序
@param  array 数组
@param  num   桶的数量*/
function bucketSort(array, num) {
     if (array.length <= 1) {
         return array;
     }
     var len = array.length, buckets = [], result = [], min = max = array[0], regex = '/^[1-9]+[0-9]*$/' , space , n = 0;
     num = num || ((num > 1 && regex.test(num)) ? num : 10);
     console. time ( '桶排序耗时' );
     for (var i = 1; i < len; i++) {
         min = min <= array[i] ? min : array[i];
         max = max >= array[i] ? max : array[i];
     }
     space = ( max - min + 1) / num;
     for (var j = 0; j < len; j++) {
         var index = Math.floor((array[j] - min ) / space );
         if (buckets[ index ]) {   //  非空桶,插入排序
             var k = buckets[ index ].length - 1;
             while (k >= 0 && buckets[ index ][k] > array[j]) {
                 buckets[ index ][k + 1] = buckets[ index ][k];
                 k --;
             }
             buckets[ index ][k + 1] = array[j];
         } else {    //空桶,初始化
             buckets[ index ] = [];