第一部分：数组排序
图片名词解释：
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存，不占用额外内存
Out-place: 占用额外内存
1. sort排序法
（1）简单数组的简单排序
var arrSimple=new Array(1,8,7,6);
arrSimple.sort();
console.log(arrSimple.join()) ;复制代码
（2）简单数组的自定义排序
var arrSimple2=new Array(1,8,7,6);
arrSimple2.sort(function(a,b){
return a-b
});
console.log(arrSimple2.join())复制代码
解释：a,b表示数组中的任意两个元素，a-b输出从小到大排序，b-a输出从大到小排序。
（3）简单对象List自定义属性排序
var objectList = new Array();
function Persion(name,age){
this.name=name;
this.age=age;
}
objectList.push(new Persion('jack',20));
objectList.push(new Persion('tony',25));
objectList.push(new Persion('stone',26));
objectList.push(new Persion('mandy',23));
//按年龄从小到大排序
objectList.sort(function(a,b){
return a.age-b.age
});
for(var i=0;i<objectList.length;i++){
document.writeln('<br />age:'+objectList[i].age+' name:'+objectList[i].name);
}复制代码
（4）简单对象List对可编辑属性的排序
var objectList2 = new Array();
function WorkMate(name,age){
this.name=name;
var _age=age;
this.age=function(){
if(!arguments){
_age=arguments[0];
}else{
return _age;
}
}
}
objectList2.push(new WorkMate('jack',20));
objectList2.push(new WorkMate('tony',25));
objectList2.push(new WorkMate('stone',26));
objectList2.push(new WorkMate('mandy',23));
//按年龄从小到大排序
objectList2.sort(function(a,b){
return a.age()-b.age();
});
for(var i=0;i<objectList2.length;i++){
document.writeln('<br />age:'+objectList2[i].age()+' name:'+objectList2[i].name);
}复制代码
2. 冒泡排序法
解析：1.比较相邻的两个元素，如果前一个比后一个大，则交换位置。
2.第一轮的时候最后一个元素应该是最大的一个。
3.按照步骤一的方法进行相邻两个元素的比较，这个时候由于最后一个元素已经是最大的了，所以最后一个元素不用比较)（所以减 i ）。
var arr=[7,20,3,8,4,9,4,0,-4,1]
function sort(elements){
for(var i=0;i<elements.length-1;i++){
for(var j=0;j<elements.length-i-1;j++){
if(elements[j]>elements[j+1]){
var swap=elements[j];
elements[j]=elements[j+1];
elements[j+1]=swap;
}
}
}
}
console.log("before:"+arr)//before:[7,20,3,8,4,9,4,0,-4,1]
sort(arr);
console.log("after:"+arr) //after:-4,0,1,3,4,4,7,8,9,20复制代码
二维数组使用冒泡排序
方法1：
var arr=[["北京",80],["上海",50],["福州",10],["广州",50],["成都",70],["西安",100]];
var t;
for(var i=0;i<arr.length;i++){
for(var j=0;j<arr.length-1;j++){
if(arr[j][1]>arr[j+1][1]){
t=arr[j][1];
arr[j][1]=arr[j+1][1];
arr[j+1][1]=t;
}
}
}
console.log(arr);
//["福州",10],["上海",50],["广州",50],["成都",70],["北京",80],["西安",100]复制代码
方法2：（选择排序法）
var arr=[["北京",80],["上海",50],["福州",10],["广州",50],["成都",70],["西安",100]];
for(var i=0;i<arr.length;i++){
for(var j=i+1;j<arr.length;j++){
if(arr[i][1]>arr[j][1]){
var t=arr[j][1];
arr[j][1]=arr[i][1];
arr[i][1]=t;
}
}
}
console.log(arr); 复制代码
3. 选择排序法
相对于冒泡排序还有一种类似的方法就是选择排序，顾名思义就是选择性排序，什么意思呢？
这么来理解，假设在三伏天有一趟室内游泳课，教练说了先在露天场地等着，从你们当中先选取最大个先进去，然后再从剩余的人中选择最大个进去，依次类推。那么小个的就在想了，教练你TMD的脑子是不是被驴踢了。但是如果是冒泡排序那更有意思了，所有的人先排好队再进去，这样还好一点最起码每个人的心理能平衡一点。简单理解选择排序就是从一个未知数据空间，选取数据之最放到一个新的空间。
废话不多说，看例子：
var array = [1,4,-8,-3,6,12,9,8];
function selectSort(arr){
for(var i=0;i<arr.length;i++){
//设置当前范围最小值和索引
var min = arr[i];
var minIndex = i;
//在该范围选出最小值
for(var j=i+1;j<arr.length;j++){
if(min>arr[j]){
min = arr[j];
minIndex = j;
}
}
//将最小值插入,并将原来位置的最小值删除
arr.splice(i,0,min);
arr.splice(minIndex+1,1);
}
}
selectSort(array);
document.write(array);复制代码
- （1）在未排序序列中找到最小（大）元素
- （2）并存放到排序序列的起始位置
- （3）然后，再从剩余未排序元素中继续寻找最小（大）元素
- （4）然后放到已排序序列的末尾。
- （5）以此类推
选择排序动图
4. 插入排序法
（1） 从第一个元素开始，该元素可以认为已经被排序
（2） 取出下一个元素，在已经排序的元素序列中从后向前扫描
（3） 如果该元素（已排序）大于新元素，将该元素移到下一位置
（4） 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
（5）将新元素插入到下一位置中
（6） 重复步骤2
var array = [1,4,-8,-3,6,12,9,8];
function insertSort(arr){
//假设第0元素是有序序列，第1元素之后是无序的序列。从第1元素开始依次将无序序列的元素插入到有序序列中
for(var i=1; i<arr.length;i++){
if(arr[i]<arr[i-1]){
//取出无序序列中需要插入的第i个元素
var temp = arr[i];
//定义有序中的最后一个位置
var j = i-1;
arr[i] = arr[j];
while(j>=0 && temp<arr[j]){ //比较大小，找到插入的位置
arr[j+1] = arr[j];
j--;
};
arr[j+1] = temp; //插入
}
}
}
insertSort(array)
console.log(array);复制代码插入排序动图
5. 希尔排序法
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]；复制代码
当读到while循环时，我类个去，什么鬼？什么意思？再往下读，好了，放弃吧！看起来云里雾里，变量附来附去，什么意思？
抽象看不明白那就实例化，以arr为例代进去一看究竟，len/5 以五步为增量，这好像是说的通，但是gap = gap *5 +1 ；这是什么鬼？
别着急慢慢读，len = 15 ,gap = 6 ;while循环结束。再往下读，var i = gap ；也就是说从i = 6开始循环一直到数组末尾，然后从i=6开始记录元素，而对于下标为 j 的for循环，则是从0开始，然后以步长为6开始比较，接下来就会发现一个问题，j-=gap ？ 又是什么鬼？ j=0,j-=gap ,那 j 不就是负的了么？编者这么写是有他的理由的，对，在下标为6之前的元素之循环了一次，那下边如果超过6呢，所以小编觉得这个地方也算是个亮点吧！
还没结束，这层内层循环结束了，跳了出来，gap = Math.floor(gap/5) 又是什么玩意？只是常规的思想局限了创新，这个不就是与while循环的gap = gap *5+1 ；与之相应么？这么做有什么好处呢，也就是说无论数据有多大，最终肯定会走到每隔6步为已增量的循环中，这就是希尔排序的亮点所在，而且前面定义的gap=1；还有gap = gap*5+1 ；这个1不是随便定义的，因为最终回归到的就是增量为1的循环当中！
6. 归并排序法
归并排序其实可以类比二分法，二分法其实就是二等分的意思，简而言之就是不断和新序列的中间值进行比较。归并排序似乎有异曲同工之妙，什么意思呢，就是将一个原始序对等分为两部分，然后不断地对等分新的序列，直至序列的长度为1或者2，那么想，如果一个序列为1，那就没有比较的意义了，它本身就是之最，如果是两个呢，那直接比较不就完了，把比较之后的值推送到一个新的数组。就这样不断地细分，不断的产生子序列，然后把穿产生的新序列作为新的父序列，然后同等级的父序列再比较产生新的祖序列，依次类推。
有点抽象了，那就具体化，比如现在有个十万人的司令部，习大大是首长，习大大跟司令说了，把所有的人按年龄排序，司令想了，让我一个人也忙活不过来啊，这怎么办，然后就把任务下达给军长，军长下达给师长，依次类推，排长再把一个排分成两个小队，小队再分成两个小组，最后分成两个人一组或一人一组，接下来就是组员之间进行比较，完了小队与小队比较，排与排之间比较，依次类推，最后军团和军团比较，形成最后的序列。
废话不多说，看代码：
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));复制代码
7. 快速排序法
对冒泡排序的一种改进，第一趟排序时将数据分成两部分，一部分比另一部分的所有数据都要小。然后递归调用，在两边都实行快速排序。
var array = [1,4,-8,-3,6,12,9,8];
function quickSort(arr){
//如果数组长度小于等于1，则返回数组本身
if(arr.length<=1){
return arr;
}
var index = Math.floor(arr.length/2); //定义中间值的索引
var temp = arr.splice(index,1); //取到中间值
//定义左右部分数组
var left = [];
var right = [];
for(var i=0;i<arr.length;i++){
//如果元素比中间值小，那么放在左边，否则放右边
if(arr[i]<temp){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return quickSort(left).concat(temp,quickSort(right));
}
console.log(quickSort(array));复制代码
Math.floor(x)方法是向下取整，返回小于或等于x的最接近的整数。
splice(index,num,item)方法是向数组中添加项目，或是从数组中删除项目，并返回被删除的项目。
- index是整数，被操作项目所在的位置（必须）
- num是整数，要删除的项目的数量，如果为0，表示不删除（必须）
- item是向数组中添加的新项目，可以是多个（可选）
push()方法是向数组末尾添加一个或多个新项目并返回新数组的长度
concat()方法连接两个或多个数组，不会改变原有数组，返回一个新数组
快速排序动图
8. 堆排序
这种排序方式呢，理论性太强，看动图的时候满脸写着懵逼，多看几遍似乎明白了编者的意图，但是要把这种理论的概念写成代码却不容易，且看代码：
function heapSort(array) {
console.time('堆排序耗时');
//建堆
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;
}
function heapify(arr, x, len) {
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);
}
}
var arr = [-26, 54, 25, 7, -21, 24, 68, 29, 16, 41, 87];
console.log(heapSort(arr));复制代码
9. 计数排序法
计数排序就是遍历数组记录数组下的元素出现过多次，然后把这个元素找个位置先安置下来，简单点说就是以原数组每个元素的值作为新数组的下标，而对应小标的新数组元素的值作为出现的次数，相当于是通过下标进行排序。
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 = [-26, 54, 25, 7, -21, 24, 68, 29, 16, 41, 87];
console.log(countingSort(arr)); 复制代码
10. 桶排序
一看到这个名字就会觉得奇特，几个意思，我排序还要再准备几个桶不成？还真别说，想用桶排序还得真准备几个桶，但是此桶非彼桶，这个桶是用来装数据用的。其实桶排序和计数排序还有点类似，计数排序是找一个空数组把值作为下标找到其位置，再把出现的次数给存起来，这似乎看似很完美，但也有局限性，不用小编说相信读者也能明白，既然计数是把原数组的值当做下标来看待，那么该值必然是整数，那假如出现小数怎么办？这时候就出现了一种通用版的计数排序——桶排序。
我得桶排序可以这么理解，它是以步长为分隔，将最相近数据分隔在一起，然后再在一个桶里排序。好了，现在有个概念，步长是什么玩意？这么来说吧，比如在知道十位的情况下48和36有比较的必要吗？显然没有，十位就把你干下去了，还比什么？那在这里可以简单的把步长理解为10，桶排序就是这样，先把同一级别的分到一组，由同一级别的元素进行排序。
代码实现：
@param array 数组
@param num 桶的数量
function bucketSort(array, num) {
if (array.length <= 1) {
return array;
}
var len = array.length, buckets = [], result = [], min = max = array[0], space, n = 0;
var index = Math.floor(len / num) ;
while(index<2){
num--;
index = Math.floor(len / num) ;
}
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] = [];
buckets[index].push(array[j]);
}
}
while (n < num) {
result = result.concat(buckets[n]);
n++;
}
console.timeEnd('桶排序耗时');
return result;
}
var arr = [-26, 54, 25, 7, -21, 24, 68, 29, 16, 41, 87];
console.log(bucketSort(arr,4));复制代码
但是这边有个坑点，就是桶的数量不能过多，也就说说至少两个桶！为什么？你试下就知道了！
附图理解：
第二部分：数组去重
数组去重，一般都是在面试的时候才会碰到，一般是要求手写数组去重方法的代码。如果是被提问到，数组去重的方法有哪些？你能答出其中的10种，面试官很有可能对你刮目相看。
在真实的项目中碰到的数组去重，一般都是后台去处理，很少让前端处理数组去重。虽然日常项目用到的概率比较低，但还是需要了解一下，以防面试的时候可能回被问到。
一、建立一个空的数组
var arr=[11,22,33,44,55,22,22,33,54];//拿到数组中不重复的元素
var x=[]; //定义一个空数组
for(var n=0;n<arr.length;n++){
if (x.indexOf(arr[n])==-1){
x.push(arr[n]);//怎么判断新的数组中是否有arr[n]这个元素呢；
}
}
console.log(x.sort());复制代码
二、用 indexOf( )
var arr=[11,22,33,44,55,22,33,54];
for(var n=0;n<arr.length;n++){
for(var j=n+1;j<arr.length;j++){
if (arr[n]==arr[j]) {
arr.splice(arr.indexOf(arr[j]),1);
j--;
}
}
}
console.log(arr)复制代码
var arr=[11,22,33,44,55,22,33,54];
for(var n=0;n<arr.length;n++){
if (arr.indexOf(arr[n])!=arr.lastIndexOf(arr[n])){
//判断arr[n]出现的次数，如果次数不是一次，那么删除后边的元素
arr.splice(arr.lastIndexOf(arr[n]),1);
n--;//没有这个n--，相当于执行了8次，
}
}
console.log(arr);复制代码
三、利用ES6 Set去重（ES6中最常用）
function unique (arr) {
return Array.from(new Set(arr))
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
//[1, "true", true, 15, false, undefined, null, NaN, "NaN", 0, "a", {}, {}]复制代码不考虑兼容性，这种去重的方法代码最少。这种方法还无法去掉“{}”空对象，后面的高阶方法会添加去掉重复“{}”的方法。
四、利用for嵌套for，然后splice去重（ES5中最常用）
function unique(arr){
for(var i=0; i<arr.length; i++){
for(var j=i+1; j<arr.length; j++){
if(arr[i]==arr[j]){ //第一个等同于第二个，splice方法删除第二个
arr.splice(j,1);
j--;
}
}
}
return arr;
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
//[1, "true", 15, false, undefined, NaN, NaN, "NaN", "a", {…}, {…}]
//NaN和{}没有去重，两个null直接消失了复制代码
双层循环，外层循环元素，内层循环时比较值。值相同时，则删去这个值。
五、利用indexOf去重
function unique(arr) {
if (!Array.isArray(arr)) {
console.log('type error!')
return
}
var array = [];
for (var i = 0; i < arr.length; i++) {
if (array .indexOf(arr[i]) === -1) {
array .push(arr[i])
}
}
return array;
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
// [1, "true", true, 15, false, undefined, null, NaN, NaN, "NaN", 0, "a", {…}, {…}] //NaN、{}没有去重复制代码新建一个空的结果数组，for 循环原数组，判断结果数组是否存在当前元素，如果有相同的值则跳过，不相同则push进数组。
六、利用sort()
function unique(arr) {
if (!Array.isArray(arr)) {
console.log('type error!')
return;
}
arr = arr.sort()
var arrry= [arr[0]];
for (var i = 1; i < arr.length; i++) {
if (arr[i] !== arr[i-1]) {
arrry.push(arr[i]);
}
}
return arrry;
}
var arr = [1,1,'true','true',true,true,15,15,false,false, undefined,undefined, null,null, NaN, NaN,'NaN', 0, 0, 'a', 'a',{},{}];
console.log(unique(arr))
// [0, 1, 15, "NaN", NaN, NaN, {…}, {…}, "a", false, null, true, "true", undefined]
//NaN、{}没有去重复制代码利用sort()排序方法，然后根据排序后的结果进行遍历及相邻元素比对。
七、利用对象的属性不能相同的特点进行去重（这种数组去重的方法有问题，不建议用，有待改进）
function unique(arr) {
if (!Array.isArray(arr)) {
console.log('type error!')
return
}
var arrry= [];
var obj = {};
for (var i = 0; i < arr.length; i++) {
if (!obj[arr[i]]) {
arrry.push(arr[i])
obj[arr[i]] = 1
} else {
obj[arr[i]]++
}
}
return arrry;
}
var arr = [1,1
