Detailed explanation of javascript array deduplication and quick sort algorithm examples

Array deduplication

Principle: Define an object obj, and then use the array element as the attribute name of obj, and use whether the attribute name is repeated to determine the duplication

var unique = function(arr){
  let obj = {};
  let newArr = [];
  arr.forEach(function(x){
    if(!obj[x]){ //如果对象中没有该元素对应的属性
      obj[x] = true;
      newArr.push(x);
    }
  });
  return newArr;
}

Use the quick sort algorithm to sort the array

This includes two effects. One is to use the characteristics of quick sort to achieve deduplication and quick sort. , the other is quick sorting without deduplication.

Principle: Obtain the target array, select an element as the flag, traverse the remaining elements, put them on the right if they are larger than the flag, and put them on the left if they are smaller than the flag.

Special note: There are elements equal to the flag bit. If you store equal elements, deduplication will be achieved. If you store them, they will not be deduplicated.

var quickSort = function(arr){
  if(arr.length <= 1){
    return arr;
  }
  //定义一个左数组，定义一个右数组
  let leftArr = [];
  let rightArr = [];
  //选定一个参照值
  let tag = arr[0];
  /*
   * 使用如下方式判断，会把重复元素去掉，就实现了快排的同时去重
   */
  for(let i = 0; i < arr.length; i++){
    if(arr[i] < tag){ //将比tag小的元素放在左数组中
      leftArr.push(arr[i]);
    }
    if(arr[i] > tag){ //将比tag大的元素放在右数组中
      rightArr.push(arr[i]);
    }
  }
  /*
   * 使用如下方式就是使用快排进行排序，不去重
   */
  for(let i = 1; i < arr.length; i++){
    if(arr[i] < tag){ //将比tag小的元素放在左数组中
      leftArr.push(arr[i]);
    }else{ //将比tag大的元素放在右数组中
      rightArr.push(arr[i]);
    }
  }
  //递归调用
  return [].concat(quickSort(leftArr),[tag],quickSort(rightArr));
}

The above is the detailed content of Detailed explanation of javascript array deduplication and quick sort algorithm examples. For more information, please follow other related articles on the PHP Chinese website!