js十大经典算法（下）

2021-03-18

排序算法的作用：
如果你做数据处理，这个数据有恰好是有序的，这时候排序的功底就能帮你快速合并多个有序数据；如果这个数据量太大，你需要画图展现，那么你就需要建立一个索引来处理；如果在你的图像需要和鼠标交互，那么你二维的点需要一个状态管理起来，这时候就要用到多边形包含点的判断……这些场景都是需要手动排序的，sort()不一定能解决

快速排序（Quick Sort）

快速排序须知：
又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。
快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高! 它是处理大数据最快的排序算法之一了。虽然Worst Case的时间复杂度达到了O(n²)，但是人家就是优秀，在大多数情况下都比平均时间复杂度为O(n log n) 的排序算法表现要更好，可是这是为什么呢，我也不知道。。。好在我的强迫症又犯了，查了N多资料终于在《算法艺术与信息学竞赛》上找到了满意的答案：

快速排序的最坏运行情况是O(n²)，比如说顺序数列的快排。但它的平摊期望时间是O(n log n) ，且O(n log n)记号中隐含的常数因子很小，比复杂度稳定等于O(n log n)的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

更新：
《算法第四版》里对于快速排序的优缺点进行了更加明确的解释：

快速排序的内循环比大多数排序算法都要短小，这意味着它无论是在理论上还是在实际中都要更快。它的主要缺点是非常脆弱，在实现时要非常小心才能避免低劣的性能。

快速排序JavaScript代码实现：

 1 function quickSort(arr, left, right) {
 2     var len = arr.length,
 3         partitionIndex,
 4         left = typeof left != 'number' ? 0 : left,
 5         right = typeof right != 'number' ? len - 1 : right;
 6 
 7     if (left < right) {
 8         partitionIndex = partition(arr, left, right);
 9         quickSort(arr, left, partitionIndex-1);
10         quickSort(arr, partitionIndex+1, right);
11     }
12     return arr;
13 }
14 
15 function partition(arr, left ,right) {     //分区操作
16     var pivot = left,                      //设定基准值（pivot）
17         index = pivot + 1;
18     for (var i = index; i <= right; i++) {
19         if (arr[i] < arr[pivot]) {
20             swap(arr, i, index);
21             index++;
22         }        
23     }
24     swap(arr, pivot, index - 1);
25     return index-1;
26 }
27 
28 function swap(arr, i, j) {
29     var temp = arr[i];
30     arr[i] = arr[j];
31     arr[j] = temp;
32 }

堆排序（Heap Sort）
堆排序须知：堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列

小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列

堆排序JavaScript代码实现：

 1 var len;    //因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
 2 
 3 function buildMaxHeap(arr) {   //建立大顶堆
 4     len = arr.length;
 5     for (var i = Math.floor(len/2); i &gt;= 0; i--) {
 6         heapify(arr, i);
 7     }
 8 }
 9 
10 function heapify(arr, i) {     //堆调整
11     var left = 2 * i + 1,
12         right = 2 * i + 2,
13         largest = i;
14 
15     if (left < len && arr[left] > arr[largest]) {
16         largest = left;
17     }
18 
19     if (right < len && arr[right] > arr[largest]) {
20         largest = right;
21     }
22 
23     if (largest != i) {
24         swap(arr, i, largest);
25         heapify(arr, largest);
26     }
27 }
28 
29 function swap(arr, i, j) {
30     var temp = arr[i];
31     arr[i] = arr[j];
32     arr[j] = temp;
33 }
34 
35 function heapSort(arr) {
36     buildMaxHeap(arr);
37 
38     for (var i = arr.length-1; i > 0; i--) {
39         swap(arr, 0, i);
40         len--;
41         heapify(arr, 0);
42     }
43     return arr;
44 }

计数排序（Counting Sort）
计数排序须知：计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

计数排序JavaScript代码实现：

 1 function countingSort(arr, maxValue) {
 2     var bucket = new Array(maxValue+1),
 3         sortedIndex = 0;
 4         arrLen = arr.length,
 5         bucketLen = maxValue + 1;
 6 
 7     for (var i = 0; i < arrLen; i++) {
 8         if (!bucket[arr[i]]) {
 9             bucket[arr[i]] = 0;
10         }
11         bucket[arr[i]]++;
12     }
13 
14     for (var j = 0; j < bucketLen; j++) {
15         while(bucket[j] > 0) {
16             arr[sortedIndex++] = j;
17             bucket[j]--;
18         }
19     }
20 
21     return arr;
22 }

桶排序（Bucket Sort）
桶排序须知：桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

在额外空间充足的情况下，尽量增大桶的数量
使用的映射函数能够将输入的N个数据均匀的分配到K个桶中
同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

什么时候最快（Best Cases）：
当输入的数据可以均匀的分配到每一个桶中

什么时候最慢（Worst Cases）：
当输入的数据被分配到了同一个桶中

桶排序JavaScript代码实现：

 1 function bucketSort(arr, bucketSize) {
 2     if (arr.length === 0) {
 3       return arr;
 4     }
 5 
 6     var i;
 7     var minValue = arr[0];
 8     var maxValue = arr[0];
 9     for (i = 1; i < arr.length; i++) {
10       if (arr[i] < minValue) {
11           minValue = arr[i];                //输入数据的最小值
12       } else if (arr[i] > maxValue) {
13           maxValue = arr[i];                //输入数据的最大值
14       }
15     }
16 
17     //桶的初始化
18     var DEFAULT_BUCKET_SIZE = 5;            //设置桶的默认数量为5
19     bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
20     var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;   
21     var buckets = new Array(bucketCount);
22     for (i = 0; i < buckets.length; i++) {
23         buckets[i] = [];
24     }
25 
26     //利用映射函数将数据分配到各个桶中
27     for (i = 0; i < arr.length; i++) {
28         buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
29     }
30 
31     arr.length = 0;
32     for (i = 0; i < buckets.length; i++) {
33         insertionSort(buckets[i]);                      //对每个桶进行排序，这里使用了插入排序
34         for (var j = 0; j < buckets[i].length; j++) {
35             arr.push(buckets[i][j]);                      
36         }
37     }
38 
39     return arr;
40 }

基数排序（Radix Sort）
基数排序须知：基数排序有两种方法：

MSD 从高位开始进行排序
LSD 从低位开始进行排序
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值

基数排序JavaScript代码实现：

 1 //LSD Radix Sort
 2 var counter = [];
 3 function radixSort(arr, maxDigit) {
 4     var mod = 10;
 5     var dev = 1;
 6     for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
 7         for(var j = 0; j < arr.length; j++) {
 8             var bucket = parseInt((arr[j] % mod) / dev);
 9             if(counter[bucket]==null) {
10                 counter[bucket] = [];
11             }
12             counter[bucket].push(arr[j]);
13         }
14         var pos = 0;
15         for(var j = 0; j < counter.length; j++) {
16             var value = null;
17             if(counter[j]!=null) {
18                 while ((value = counter[j].shift()) != null) {
19                       arr[pos++] = value;
20                 }
21           }
22         }
23     }
24     return arr;
25 }