JavaScript实现经典排序算法

使用JavaScript实现的经典排序算法

util

function swap(arr,i,j) {
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

冒泡

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

简单选择

function selectionSort(arr) {
  var min;
  for (var i = 0; i < arr.length; i++) {
    min = i;
    for (var j = i + 1; j < arr.length; j++) {
      if(arr[j] < arr[min]) {
        min = j;
      }
    }
    if(arr[i] !== arr[min]) {
      swap(arr,i,min)
    }
  }
}

直接插入

function insertionSort(arr) {
  for (var i = 1; i < arr.length; i++) {
    if(arr[i] < arr[i-1]) {
      var temp = arr[i];
      for (var j = i - 1; arr[j] > temp; j--) {
        arr[j + 1] = arr[j]
      }
      arr[j + 1] = temp;
    }
  }
}

快速排序

function quickSort(arr) {
  if(arr.length <= 1) return arr;
  var pivotIndex = (0 + arr.length) >> 1;
  var left = [];
  var right = [];
  var pivot = arr.splice(pivotIndex,1)[0];
  for (var i = 0; i < arr.length; i++) {
    if(arr[i] >= pivot) {
      right.push(arr[i])
    }else {
      left.push(arr[i])
    }
  }
  return quickSort(left).concat(pivot,quickSort(right));
}

堆排序

function heapSort(array) {
  arr.unshift(0);

  var i,j;
  for (i = array.length - 1 >> 1 ; i > 0; i--) {
    heapAdjust(array,i,array.length - 1);
  }

  for (j = array.length - 1; j > 2; j--) {
    swap(array,j,1);
    heapAdjust(array,1,j-1)
  }
  array.shift(0);
}


function heapAdjust(arr,start,len) {
  var temp = arr[start];
  for (var i = start * 2; i < len; i *= 2) {
    if(i < len && arr[i] < arr[i+1]) {
      ++i;
    }
    if(temp > arr[i]) {
      break;
    }
    swap(arr,start,i);
    start = i;
  }
}

归并排序

function mergeSort(array) {
    function sort(array, first, last) {
        first = (first === undefined) ? 0 : first
        last = (last === undefined) ? array.length - 1 : last
        if (last - first < 1) {
            return;
        }
        var middle = Math.floor((first + last) / 2);
        sort(array, first, middle);
        sort(array, middle + 1, last);
        var f = first,
            m = middle,
            i,
            temp;
        while (f <= m && m + 1 <= last) {
            if (array[f] >= array[m + 1]) { // 这里使用了插入排序的思想
                temp = array[m + 1];
                for (i = m; i >= f; i--) {
                    array[i + 1] = array[i];
                }
                array[f] = temp;
                m++
            } else {
                f++
            }
        }
        return array;
    }
    return sort(array);
}