JS随写：数组排序去重

发表于 | 本文总阅读量 次

最近公司事情巨多，整日折腾公司的上古backbone框架，让我头疼不已，说好的最少1周1次blog的更新也多次delay，再努力吧，毕竟开头难，养成习惯也难。

数组对象

按照数组中对象的某一属性大小进行排序

1
2
3
4
5
6
7
array.sort(function(a,b){   //升序
	if(a.id === b.id){
		return 0;
	}else{
		return a.id < b.id ? -1 : 1;
	}
})

按照数组中对象的某一属性是否重复进行去重

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//使用数组的reduce方法
var hash = {};
arr = arr.reduce(function(item, next) {
    hash[next.name] ? '' : hash[next.name] = true && item.push(next);
    return item
}, []);
// 拆解
var hash = {};
arr = arr.reduce(function(item,next){
	if(!hash[next.name]){
		hash[next.name] = true;
		item.push(next);
	}
	return item;
},[]);

//例子
var arr = [
	{
	    "name": "aaa",
	    "age": "16"
	}, 
	{
	    "name": "bbb",
	    "age": "20"
	}, 
	{
	    "name": "ccc",
	    "age": "15"
	}, 
	{
	    "name": "bbb",
	    "age": "30"
	}, 
	{
	    "name": "eee",
	    "age": "28"
	}];
var hash = {};
arr = arr.reduce(function(item, next) {
    hash[next.name] ? '' : hash[next.name] = true && item.push(next);
    return item
}, []);
console.log(arr);
// [{"name": "aaa","age": "16"},
//	{"name": "bbb","age": "20"},
//	{"name": "ccc","age": "15"},
//	{"name": "eee","age": "28"},
//]

纯数组

排序

  • js自带sort排序
1
2
3
4
5
var arr = [1,8,3,4,5,9,3,6,];
arr.sort(function(a,b){
	return a - b;    //a-b升序，b-a降序
});
arr; //[1, 3, 3, 4, 5, 6, 8, 9]
对于数值类型或者其valueOf()方法会返回数值类型的对象类型，可以使用以上方法 –《javascript高级程序设计》
  • 冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
var arr = [1,8,3,4,5,9,3,6,];
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j+1]) {
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  return arr;
}
bubbleSort(arr);  // [1, 3, 3, 4, 5, 6, 8, 9]
  • 选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 内层循环获取这轮循环的最小值，与arr[i]交换
var arr = [1,8,3,4,5,9,3,6,];
function chooseSort(arr){
	for(var i=0;i<arr.length-1;i++){
		for(var j=i+1;j<arr.length;j++){
			if(arr[i]>arr[j]){
				var temp = arr[j];
				arr[j] = arr[i];
				arr[i] = temp;
			}
		}
	}
	return arr;
}
chooseSort(arr);  // [1, 3, 3, 4, 5, 6, 8, 9]
  • 插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var arr = [8,2,3,4,5,9,3,6];
function insersort(arr){
	for(i=1;i<arr.length;i++){
		temp = arr[i];
		j = i;
		while(j > 0 && arr[j-1] > temp){
			arr[j] = arr[j-1];
			j--;
		}
		arr[j] = temp;
	}
	return arr;
}
insersort(arr)
  • 归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var arr = [1,8,3,4,5,9,3,6,7];
function mergeSort(arr) {
  if (arr.length === 1) return arr;
  let mid = Math.floor(arr.length / 2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
  let result = [], li = 0, ri = 0;
  while(li < left.length && ri < right.length) {
    left[li] < right[ri] ? result.push(left[li++]) : result.push(right[ri++]);
  }
  while(li < left.length) {
    result.push(left[li++]);
  }
  while(ri < right.length) {
    result.push(right[ri++]);
  }
  return result;
}

mergeSort(arr)
  • 快速排序

快速排序是最优的排序方法，基于“分治思想”，选取一个“基准数”pivot，将小于pivot的数放左边，大约pivot的放右边，然后对左右分别再次“分治”。根据pivot选取的不同，排序的复杂度从O(n2)->O(nlogn)，这个算法的重点在于是在本地对数组进行排序，不需要引入额外空间。参看链接：Quick Sort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var arr = [1,8,3,4,5,9,3,6,7];
function quickSort(arr, start, end) {
  if (start < end) {
    let piv_pos = partition(arr, start, end);
    quickSort(arr, start, piv_pos - 1);
    quickSort(arr, piv_pos + 1, end);
  }
  return arr;
}
function partition(arr, start, end) {
  let i = start + 1, pivot = arr[start];
  for (let j = start + 1; j <= end; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[start], arr[i-1]] = [arr[i-1], arr[start]];
  return i - 1;
}
quickSort(arr, 0, arr.length - 1);

去重

1
2
3
4
5
6
7
8
9
10
11
var arr = [8,2,3,4,5,4,3,6,8];
function removeDup(arr){
	var newarr = [];
	for(var i = 0; i<arr.length; i++){
		if(newarr.indexOf(arr[i]) === -1){
			newarr.push(arr[i]);
		}
	}
	return newarr;
}
removeDup(arr);