[算法] - 排序

js实现了一下几种基于比较的排序(常数时间的排序还没看!阿西吧!)

插排和冒泡平均时间复杂度o(n^2),最优o(n),前两种稳定。选择都是n^2不稳定。

提一下冒泡,一直以为它最坏最好都是n^2复杂度,不过写的时候发现每次冒泡可以检查本次是否交换过元素,如果没有直接退出,最优情况排好序的数组,一趟遍历退出。

通常小数据量选择和插排比较快。基本排好序,小数据量用插排.

1. 直接插入

function insertSort(arr) {
    console.time("insert sort: ");
    for (var i = 0; i < arr.length; i++) {
      var j = i;
      var value = arr[i];
      while(j>0 && value < arr[j-1]) {
        arr[j] = arr[j-1];
        j--;
      }
      arr[j] = value;
    }
    console.timeEnd("insert sort: ");
    return arr;
  }

 

2. 冒泡

function bubbleSort(arr) {
    console.time("bubble sort: ");
    for(var i = 0; i < arr.length; ++i){  //n次遍历
      var change = false;
      for(var j = arr.length-1; j > i; --j) { //从最后冒泡至i,一次冒泡i最小
        if(arr[j] < arr[j-1]) {
          var temp = arr[j-1]
          arr[j-1] = arr[j];
          arr[j] = temp;
          change = true;
        }
      }
      if(!change) {
        console.timeEnd("bubble sort: "); //0.074
        return arr;
      }
    }
    console.timeEnd("bubble sort: "); //0.095
    return arr;
  }

 

3. 选择

function selectSort(arr) {
    console.time("select sort: ");
    for(var i = 0; i < arr.length-1; ++i) {
      var min = i;
      for(var j = i; j < arr.length; ++j) {
        if(arr[j] < arr[min]) {
          min = j;
        }
      }
      var temp = arr[min];
      arr[min] = arr[i];
      arr[i] = temp;
    }
    console.timeEnd("select sort: ");
    return arr;
  }

4. 快排

然后是快排,平均o(nlogn),最差o(n^2)在原数据正序或逆序时。快排复杂度能到nlogn主要是每次选取pivot可以把元素划分为两段更小元素处理从而实现divide-conquer的目的,但是如果数据正序或逆序,每次划分后子问题规模是n-1就退化成了n^2复杂度。不稳定。

function qS(arr) {
    var partition = function(a, l, h) {
      var p = l;
      l++;
      while(l<h) {
        while(l<h && a[h] > a[p]) {
          h--;
        }
        while(l<h && a[l] <= a[p]) {
          l++;
        }
        if(l < h) {
          var temp = a[l];
          a[l] = a[h];
          a[h] = temp;
          // h--;
          // l++; //交换之后继续从当前位置扫
        }
      }
      // console.log(h);
      // console.log(l);
      var temp = a[p];
      a[p] = a[h];
      a[h] = temp;
      // console.log(a);
      return h;
    }

    var sort = function(a, l, h) {
      if(l<h) {
        var pivot = partition(a, l, h);
        // console.log(pivot);
        sort(a, l, pivot-1);
        sort(a, pivot+1, h);
      }
    }

    return {sa:arr, sort:sort}
  }

5. 堆排序

利用大顶堆或小顶堆性质排序,复杂度最优平均都是o(nlogn),不稳定。核心是构建大顶堆,和每次取元素之后对堆的maxheapify——递归的方法调整堆,使得其满足根大于子节点的特性,注意停止条件。

[codesyntax lang=”php”]

function heapSort(arr) {
    function maxHeapify(arr, index, size) {
      var max = index;
      var left = 2*index+1;
      var right = 2*index+2
      if(left < size && arr[left] > arr[max]) {
        max = left;
      }
      if(right < size && arr[right] > arr[max]) {
        max = right;
      }
      if(index != max){
        swap(arr, index, max);
        maxHeapify(arr, max, size);
      }
    }

    function buildHeap(arr) {
      for(var i = Math.floor((arr.length-1)/2); i >= 0; --i) {
        maxHeapify(arr, i, arr.length);
      }
    }

    function sort(arr) {
      buildHeap(arr);
      for(var i = 0; i < arr.length; ++i) {
        swap(arr, 0, arr.length-i-1);
        //console.log(arr);
        maxHeapify(arr, 0, arr.length-i-1);
      }
      return arr;
    }

    function swap(arr, a, b) {
      var temp = arr[a];
      arr[a] = arr[b];
      arr[b] = temp;
    }

    return{arr:arr, sort:sort};

  }

6. 希尔排序

基于插排的改进,通过调整步长减少元素移动的次数(插排中相当于每次只能移动1位,如果调整2341中1的位置就需要比较3次移动3次)o(nlogn)

function shellSort(arr) {
    var gap = 1;
    while(gap < arr.length) {
      gap = gap*3 + 1;
    }

    for(; gap > 0; gap=Math.floor(gap/3)) {
      for(var j = gap; j < arr.length; ++j) {
        var value = arr[j]
        while(j>=0 && arr[j-gap] > value) {
          arr[j] = arr[j-gap];
          j = j-gap;
        }
        arr[j] = value;
        var value = arr[j];

      }
    }

    return arr;
  }

7. 归并排序

典型分治思想,复杂度o(nlogn),递归,空间需求大。(外排)

function mergeSort(arr) {
    if(arr.length == 1) {
      return arr;
    }else {
      var m = Math.floor(arr.length/2);
      return merge(mergeSort(arr.slice(0,m)), mergeSort(arr.slice(m,arr.lenth)));
    }
  }

  function merge(arr1, arr2) {
    var i = 0;
    var j = 0;
    var result = [];
    while(i + j < arr1.length + arr2.length) {
      if(arr1[i] <= arr2[j] || j == arr2.length) {
        result[i+j] = arr1[i];
        i++;
      }else if(i < arr1.length || i == arr1.length){
        result[i+j] = arr2[j];
        j++;
      }
    }
    return result;
  }