今天来整理下Javascript中的数组排序和去重：

排序

• 时间复杂度指的是一个算法执行所耗费的时间
• 空间复杂度指运行完一个程序所需内存的大小
• 稳定指，如果a=b,a在b的前面，排序后a仍然在b的前面
• 不稳定指，如果a=b，a在b的前面，排序后可能会交换位置

1. 冒泡排序

原理：每次依次比较相邻的两个值，如果后面的数小于前面的数，则交换位置，每次遍历可以得到数组最大的值，要进行arr.length-1次遍历

代码实现：

var arr = [8,2,4,6,5,9];
function sort(arr){
for(var i =0;iarr[j+1]){
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}

  }
}
return arr;
  }
  alert(sort(arr)); 

• 平均时间复杂度O(n*n)
• 最好情况O(n)
• 最差情况O(n*n)
• 空间复杂度O(1)
• 稳定性：稳定

  2. 选择排序

原理：首先认为数组的第一个元素是最小的，然后从剩下的元素里找到比第一个元素还小的，如果存在则交换位置，依次循环后确定最小的元素，排在数组的首位；第二次遍历，认为数组的第二个元素是在剩余数组里最小的，再从剩余的元素里找比第二个小的元素，依次类推…

代码实现：
var arr = [8,2,4,6,5,9];
function selectionSort(arr){
var minindex,temp;
var len = arr.length;
for(var i = 0 ;i<len-1;i++){
minindex = i;
for(var j=i+1;j<len;j++){
if(arr[j]<arr[minindex]){
minindex = j;
}
}
temp = arr[i];
arr[i] = arr[minindex];
arr[minindex] = temp;
}
return arr;
}
alert(selectionSort(arr));

• 平均时间复杂度O(n*n)
• 最好情况O(n*n)
• 最差情况O(n*n)
• 空间复杂度O(1)
• 稳定性：不稳定

  3. 快速排序

  原理：从数组中选定一个基数，然后对数组进行遍历，每一项与基数相比，小于基数的放入一个数组，大于基数的放入另外一个数组，然后对两个数组执行相同的操作，直到最后剩下一个元素 ，排序完成。

代码实现：

var arr = [8,2,4,6,5,9,1];
  function quickSort(arr){
 if(arr.length<=1){
  return arr;
 }
 var left = [];
 var right = [];
 var pivotIndex = Math.floor(arr.length/2);
 var pivot = arr.splice(pivotIndex,1)[0];
 for(var i=0;i<arr.length;i++){
  if(arr[i]<pivot){
    left.push(arr[i]);
  }else if(arr[i]>pivot){
    right.push(arr[i]);
  }
 }
 return quickSort(left).concat([pivot],quickSort(right));
  }

  alert(quickSort(arr));  

• 平均时间复杂度O(nlogn)
• 最好情况O(nlogn)
• 最差情况O(n*n)
• 空间复杂度O(logn)
• 稳定性：不稳定

  去重

1. ES6提供了一种新的数据结构——Set，类似于数组，但是成员的值都是唯一的，没有重复的值，所以可以用来去重。
   2.

   function dedupe(arr){
   return Array.from(new Set(arr));  //转换成数组
   }
   alert(dedupe([8,2,4,6,5,9,1]))    
   

2. 利用indexOf属性

   function dedupe(arr) {
   var n = []; //一个新的临时数组
   for (var i = 0; i < arr.length; i++){
   if (n.indexOf(arr[i]) == -1){
         n.push(arr[i])
    } ;
    }
     return n;
     }    
     alert(dedupe([8,2,4,2,5,5,1]));
   

3. 继续使用indexOf属性

   function dedupe(arr) {
   var n = []; //一个新的临时数组
   for (var i = 0; i < arr.length; i++){
   if (arr.indexOf(arr[i]) == i){
       n.push(arr[i]) //如果当前数组的第i项在当前数组中第一次出现的位置不是i，
    //那么表示第i项是重复的，忽略掉。否则存入结果数组
    } ;
    }
    return n;
     }    
    alert(dedupe([8,2,4,2,5,5,1]));