算法之排序

2018-06-24 01:58:01来源：未知阅读 ()

1. 时间复杂度就是while的次数，二分查找O(h)=O(log2n)

2. 冒泡排序（O(n^2) 、稳定）

它重复地走访过要排序的数列，依次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

function bubbleSort(arr){
  const len = arr.length;
  for(let i = 0; i < len; i++){
    for(let j = 0; j < len - 1 - i; j++){
      if(arr[j] > arr[j + 1]){
        [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
      }
    }
  }
  return arr;
}

3. 快排（O(nlogn)）

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

var quickSort = function(arr){
  if(arr.length <= 1) {return arr;}
  const midIndex = Math.floor(arr.length / 2);
  const mid = arr.splice(midIndex, 1)[0];
  const left = [], right = [];
  arr.forEach(function(item){
    if(item < mid){
      left.push(item);
    }else{
      right.push(item);
    }
  })
  return quickSort(left).concat([mid], quickSort(right));
}

4. 选择排序（O(n^2)）

每次从待排序的数据中选出最小（或最大）的一个元素，存放在序列的起始位置，第二次从第二个开始，后面依次类推，直到全部待排序的数据元素排完。

function selectionSort(arr){
  const first = arr[0];
  for(var i=0;i<arr.length-1;i++){
    let minIndex = i;
    for(var j=i+1;j<arr.length;j++){
      if(arr[minIndex]>arr[j]){
        minIndex = j;
      }
    }
    if(minIndex !== i){
      const tmp = arr[i];
      arr[i] = arr[minIndex];
      arr[minIndex] = tmp;
    }
  }
  return arr;
}

5. 归并排序（O(nlogn) 、稳定）

先分解再合并，将有序子序列进行合并。

function mergeSort(arr){  
  if(arr.length <= 1){
    return arr;
  }  
  const midIndex = Math.floor(arr.length/2);  
  const leftArr = arr.slice(0, midIndex);
  const rightArr = arr.slice(midIndex);  
  return merge(mergeSort(leftArr), mergeSort(rightArr));  
}
function merge(left, right) {  
    var result = [];  
    while(left.length > 0 && right.length > 0) {  
       if(left[0] < right[0]) {  
           result.push(left.shift());  
       }else{  
           result.push(right.shift());  
       }  
   }   
   return result.concat(left).concat(right);  
}

6. 堆排序（O(nlogn)）

堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值。

7. 直接插入排序（O(n^2) 、稳定）

每次将一个待排序的记录，按照其关键字的大小插入到有序队列的合适位置里，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。

function insertionSort(arr) {
  let len = arr.length, preIndex, current;
  for (var i = 1; i < len; i++) {
    preIndex = i - 1;
    current = arr[i];
    while(preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex+1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex+1] = current;
  }
  return arr;
}

8. 希尔排序（O(n^2)）

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组。

function shellSort(arr) {
  let len = arr.length, temp, gap = 1;
  while(gap < len / 3) { 
    gap = gap * 3 + 1;
  }
  for (gap; gap > 0; gap = Math.floor(gap/3)) {
    for (var i = gap; i < len; i++) {
      temp = arr[i];
      for (var j = i-gap; j > 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = temp;
    }
  }
  return arr;
}