JavaScript桶排序算法详解

、桶排序算法

桶排序（Bucket sort）箱排序，是一个排序算法，工作的原理是将数组分到几个桶里，桶的数量可由排序数组最大值与最小值关系决定，可以固定几个桶。每个桶内再通过插入、冒泡或简单方式进行排序。其算法复杂度接近于：O(N)

步骤是：

1. 找到待排序中最大和最小的元素；

2. 得到桶的数量，比如最大减去最小再除以最小值；

3. 新建一个桶列表，然后遍历数组，再将数组项除以桶的个数得到要存放的桶的下标，将数组项存入到对应桶中；

4. 存入到桶中时，按顺序插入，保持顺序；

5. 数据全部放入桶之后，再遍历桶列表，将二维数组按顺序展开取出即可。

二、计数排序算法执行过程分析：

三、桶排序代码JS简版

output: [3, 3, 3.2, 4.3, 10, 15]

四、桶排序标准版，支持负数

output: [-7, -2.1, 3, 3, 3.2, 4.3, 10, 15]

五、总结

计数排序(Counting sort)、基数排序(radix sorting)和桶排序（Bucket Sort）是很类似的排序方式，都是非比较型的排序算法。

计数排序从最最小到最大值建立全部长度数组，然后挨个放里面放入，这对于数据范围很大的数组，需要大量时间和内存，适用性不高。

基数排序是统一为同样的数字长度，数字较短的数前面补零，也就是将数字拆分为个位十位百位。然后从最低位开始，依次进行一次排序。基数排序是线性复杂度，即对n个数字处理了n次，代价较高。

桶排序将数组分到有限数量的桶子里，然后对每个桶子再分别进行排序，不需要过多的桶。对于大量数组，可以先采用桶排序分拆，再用其他排序算法来进行桶内排序。

择排序概述

选择排序(Selection Sort)是从待排序数列中取出最小(或最大)的1位，与第一个位置交换，再从待排序数列中找出最小的跟整个数列的第二个交换。以此类推遍历完待排序数列。平均算法复杂度：O(n^2)

步骤是：

先建立两个循环，外循环用于逐个交换数据，内循环用来遍历找到最小(或最大)值。
设第1项为最小值，在内循环中将其逐个与后项进行比较，如果遇到更小的值，则更新最小值，并记录下最小值的下标。
在外循环中将第1项与最小值进行交换，然后以第2项作为最小值，再重复执行步骤2，直到遍历完全部待排序区间。

选择排序执行过程分析

例如数列： 4, 1, 3, 5, 2

从待排序区间中每次找到最小的项目，将其与第一项交换。

选择排序过程

选择排序实现

标准实现

选择排序的标准实现

新建数组法与移除法，这种方式会多建立一个数组，但无需交换。

选择排序新建数组

. 冒泡排序

程序员启蒙排序算法基础中的基础

思想：

先建立一个外部循环为总比较次数再写一个内循环为两两比较的次数
第一个内循环结束应将数组中最大的数排在了数组的最右边
经过arr.length-1次循环数组中的元素按照从小到大的顺序排列

  var arr = [3, 4, 15,80,7, 2, 6, 5, 8, 9, 10, 16, 13]; // length = 13
       
        function bubbleSort(arr){
            //因为冒泡排序算法是两两比较 所以外层比较次数应为数组长度-1
            for(var i = 0; i<arr.length - 1; i++){
            //  内循环的比较不必全部执行完  因为每一轮的内循环都会将最大的数排在最右
            //  所以后面的次数不用比较 所以内循环的次数是递减的 需要减去一个i
                 for(var j = 0; j < arr.length -1 - i; j++){
                     if(arr[j] > arr[j+1]){
                         var t = arr[j];
                         arr[j] = arr[j+1];
                         arr[j+1] = t;
                     }
                    }
                     console.log(arr)
                }
                return arr;
        }
        console.log(bubbleSort(arr));

我自己是一名从事了多年开发的web前端老程序员，目前辞职在做自己的web前端私人定制课程，今年年初我花了一个月整理了一份最适合2019年学习的web前端学习干货，各种框架都有整理，送给每一位前端小伙伴，想要获取的可以关注我的头条号并在后台私信我：前端，即可免费获取。

2. 插入排序

思想：

1.从第一个元素开始，该元素可以认为已经被排序；

2.取出当前元素的后一个元素，在已经排序的元素序列中从后向前循环一遍；

3.如果该元素（已排序的元素）大于新元素，将该元素移到下一位置；

4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

5.将新元素插入到该位置后；

6.重复步骤2~5。

var arr = [3, 4, 15, 80, 2, 7, 6, 5, 8, 9, 10, 16, 13]; // length = 13

        function insertSort(arr) {
            var current, preIndex;
            var len = arr.length;
            for (var i = 1; i < len; i++) {
            //当前元素的前一个元素下标
                preIndex = i - 1;
            // 将需要排序的元素用current保存起来以免因下面下标变化而取错值
                current = arr[i];
            // 开始内部循环将第一个值开始排序 终止条件为当前元素下标大于数组的第0位并且当前元素大于前一个元素    否则的话将前一个元素赋值给当前元素（arr[preIndex+1]）
            //然后将前一个元素下标-1 继续向前比较
                while (preIndex >= 0 && current < arr[preIndex]) {
                    arr[preIndex + 1] = arr[preIndex];
                    preIndex--;
                }
            // 当current大于前一个元素时 把保存起来的current赋值给arr[preIndex] 
                arr[preIndex + 1] = current;

            }
            return arr;
        }
        console.log(insertSort(arr));

3.快速排序

思想：

创建两个数组left right
取一个基准值可以数组中任一元素下面取了数组的中间元素并且从数组中剥离出来
将数组中的元素与基准值比较小于基准值的放进左边 left数组大于基准值的放进右边right数组
重复步骤2 3

var arr = [3, 4, 2, 6, 5, 8, 9, 10, 16, 13]; // length = 10
        function quickSort(arr) {
            if (arr.length <= 1) { return arr; }
            //     基准值
            var pivot = arr[Math.floor(arr.length / 2)];
            arr.splice(arr.indexOf(pivot), 1);
            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]);
                }

            }
            return quickSort(left).concat([pivot], quickSort(right));

        }

        console.log(quickSort(arr));

4.选择排序

思想：
1.遍历数组，设置最小值的索引为 0，
2.如果取出的值比当前最小值小，就替换最小值索引，遍历完成后，将第一个元素和最小值索引上的值交换。
3.如上操作后，第一个元素就是数组中的最小值，下次遍历就可以从索引 1 开始重复上述操作。

function selectionSort(arr) {
　　var len = arr.length;
　　var minIndex, temp;
　　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;
　　}
　　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];