数组排序

JS数组排序及数组去重

一、 数组排序

  • Array.sort
    原理:首先,js中的sort会将排序的元素类型转化成字符串进行排序。不过它是一个高阶函数,可以接受一个函数作为参数。而我们可以通过传入内部的函数,来调整数组的升序或者降序。
1
2
3
4
5
//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 ) )

上例运行结果

  • 冒泡排序
    思路:第一次循环,开始比较当前元素与下一个元素的大小,如果比下一个元素小或者相等,则不需要交换两个元素的值;若比下一个元素大的话,则交换两个元素的值。然后,遍历整个数组,第一次遍历完之后,相同操作遍历第二遍。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //冒泡排序

    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,表示排序完成。

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
//冒泡排序优化

//定义数组
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)

上例输出结果

  • 快速排列
    思路:首先,我们需要找到一个基数,然后将比基数小的值放在基数的左边,将比基数大的值放在基数的右边,之后进行递归那两组已经归类好的数组。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    快速排序

    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进新数组,最后新数组即为所求的原数组去重结果
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    //数组去重

    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());

上例运行结果

  • 对象键值对法
    思路:有时我们不仅需要将数组去重,还需要显示出该数组中重复元素出现的次数,此时需要用一个对象来存储重复元素及其重复次数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//对象键值对法

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"]);

上例运行结果

本文结束啦感谢您的阅读

版权声明

Aurora's Notes by Xiao Peng is licensed under a Creative Commons BY-NC-ND 4.0 International License.
筱鹏创作并维护的Aurora's Notes博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证
本文首发于Aurora's Notes 博客( http://wplll.com ),版权所有,侵权必究。

如果我的文章对你有很大帮助 那么不妨?