数组排序及去重方法总结

一、 数组排序

• Array.sort
  原理：首先，js中的sort会将排序的元素类型转化成字符串进行排序。不过它是一个高阶函数，可以接受一个函数作为参数。而我们可以通过传入内部的函数，来调整数组的升序或者降序。

//Array.sort 排序

const arr = [1,27,16,34,8,100,78,82,19,48,95,63];
console.log(arr.sort());
console.log( arr.sort( (item1,item2) => item1- item2 ) ) 

上例运行结果

• 冒泡排序
  思路：第一次循环，开始比较当前元素与下一个元素的大小，如果比下一个元素小或者相等，则不需要交换两个元素的值；若比下一个元素大的话，则交换两个元素的值。然后，遍历整个数组，第一次遍历完之后，相同操作遍历第二遍。

//冒泡排序

const arr = [1,20,24,2,33,51,77,18,100,88]
//定义比较的回数
const time = arr.length-1;
//外层for循环控制比较的回数
for( let i = 0; i < time; i++ ){
  //内层for循环控制每一回比较的次数
   for ( let j =  0; j < time - i; j++){
    //核心：比较，交换
    if( arr[j] - arr[j+1] > 0 ){
      const temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp;
    }
  }
}
console.log(arr);

上例输出结果

此方法可进行优化，增加一个标志位，如果没有进行交换，则将标志位置为false，表示排序完成。

//冒泡排序优化

//定义数组
const arr = [1,20,24,2,33,51,77,18,100,88]
//定义比较的回数
const time = arr.length-1;
//外层for循环控制比较的回数
for( let i = 0; i < time; i++ ){
  //加入标志位
   let flag = false;

  //内层for循环控制每一回比较的次数
   for ( let j =  0; j < time - i; j++){
    //核心：比较，交换
    if( arr[j] - arr[j+1] > 0 ){
      const temp = arr[j];
      arr[j] = arr[j+1];
      arr[j+1] = temp; 
      flag = true;
    }
  }

  //如果
   if(!flag){
    break;
   }
}
console.log(arr)

上例输出结果

• 快速排列
  思路：首先，我们需要找到一个基数，然后将比基数小的值放在基数的左边，将比基数大的值放在基数的右边，之后进行递归那两组已经归类好的数组。

快速排序

const arr = [30,32,6,24,37,32, 45, 21,38,23, 47];
function quickSort (arr) {
    if(arr.length <= 1){
        return arr;
    }
    let temp = arr[0];
    const left = [];
    const right = [];
    for (let i = 1; i < arr.length; i++) {
        if(arr[i] > temp){
            right.push(arr[i]);
        }else{
            left.push(arr[i]);
        }
    }
    return quickSort(left).concat([temp], quickSort(right));
}

console.log(quickSort(arr));

上例运行结果

二、数组去重

• 数组去重
  思路：通过Array构造函数的原型Array.prototype向所有Array对象添加数组去重的方法，new一个数组，然后遍历原数组，查找每个元素在新数组中是否存在，若不存在就将该元素push进新数组，最后新数组即为所求的原数组去重结果

//数组去重

var arr = [1,3,1,4,5,6,6,7,8,9,8,4,45,8,85,4,8,5,5];
Array.prototype.unique = function() {
    var newArr = [];
    for(var i = 0; i < this.length; i++) {
        //若查不到arr[i]元素就向新数组中存储arr[i]
        if(newArr.indexOf(this[i]) == -1) {
            newArr.push(this[i]);
        }
    }
    return newArr;
}
console.log(arr.unique());

上例运行结果

• 对象键值对法
  思路：有时我们不仅需要将数组去重，还需要显示出该数组中重复元素出现的次数，此时需要用一个对象来存储重复元素及其重复次数

//对象键值对法

var arr = [1, 2, 5, 6, 7, "f", "f", "h", "j", "c", "d", 5, 5, 5, 7, 1, 7, 4, 4, ];
//第二种,对象去重,统计重复次数
var obj = {};
for(var i = 0; i < arr.length; i++) {
    //将数组中每个元素作为键存入obj对象中
    var item = arr[i]; //第一次1
    //每次循环判断obj对象中是否存在键item对应的值，若不存在，将其赋值为1，若存在，将其值加1
    if(obj[item]) { //{1:}
        obj[item]++; //{1:2}
    } else {
        obj[item] = 1; //{1:1}   
    }
}
console.log(obj);
console.log(obj["f"]);

上例运行结果