数组排序

JS数组排序及数组去重

数组排序

使用Array.sort

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

Array.sort排序
1
2
3
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
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
//定义数组
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
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进新数组,最后新数组即为所求的原数组去重结果

cript 数组去重
1
2
3
4
5
6
7
8
9
10
11
12
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
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"]);
0%