JS实现排序算法

总结下用js实现排序的几种普遍方法：

1. 冒泡排序

原理：

依次比较相邻的两个元素，如果后一个小于前一个，则交换，这样从头到尾一次，就将最大的放到了末尾。

平均时间复杂度：O(n^2)。

function bubbleSort(arr) {
    var temp;
    if(arr.length == 0 || arr == null) {
        return arr;
    }
// [1, 545, 55, 33, 23, 21, 3]
    for(var i = 0; i < arr.length - 1; i++ ) {
        for(j = 0; j < arr.length - i - 1; j++) {
            if(arr[j] > arr[j+1]) {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}
//bubbleSort([1,34,23,34543,12,544,2])
//[1, 2, 12, 23, 34, 544, 34543]

2. 选择排序

原理：

每次找一个最大或者最小的数排在最开始，让其他数与之比较，进而选择是否交换位置。

平均时间复杂度：O(n^2)。

function selectSort (arr) {
  var length = arr.length,
      i,
      j,
      k,
      temp;

  if( length === 0 || arr === null ) {
        return arr;
  }

  for(i = 0; i < length - 1; i++) {
    k = i; //标记最小数
    for(j = i + 1; j < length; j++) {
      if(arr[k] > arr[j]) {
        k = j;
      }
      temp = arr[k];
      arr[k] = arr[i];
      arr[i] = temp;
    }
  }
  return arr;
}
//selectSort([1,43,2,324,23,534,2])
//[1, 2, 2, 23, 43, 324, 534]

3. 插入排序

原理：

将元素插入到有序序列中，一般将第一个元素视为有序序列，插入元素视为待排序列，与第一个元素进行比较插入。

平均时间复杂度：O(n^2)。

function insertionSort (arr) {
    var length = arr.length,
      i,
      j,
      k,
      preIndex, //当前元素的前一个元素的下标
      current; //当前待排元素

  if( length === 0 || arr === null ) {
        return;
  }

  for(i = 1; i < length; i++) {
    preIndex = i - 1;
    current = arr[i];
    while(preIndex >= 0 && current < arr[preIndex]) {
      arr[preIndex+1] = arr[preIndex]; // 比current大的元素后移
      preIndex--;
    }
    arr[preIndex+1] = current;//将current插入到数组中
  }
  return arr;
}
//insertionSort([23,34,2,43,3423,23,1123,3])
//[2, 3, 23, 23, 34, 43, 1123, 3423]

4. 快速排序

原理：

选择一个基准，将比基准小的，放在基准左边，将比基准大的，放在基准右边；一般选择中间的作为基准，之后两边再用递归的方法不断重复上述过程。

平均时间复杂度：O(nlog(n))。

function quickSort (arr) {
  if( arr.length <= 1 ) {
        return arr;
  }

  var left = [],
      right = [],
      i,
      j,
      k,
      pivotIndex, // 参考点下标
      pivot; //参考点

  pivotIndex = Math.floor(arr.length / 2);
  pivot = arr.splice(pivotIndex, 1)[0];//截取参考点

  for(i = 0; i < arr.length; i++) {
    if(arr[i] < pivot) {
      left.push(arr[i]);
    }else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right)); //递归进行上述规则排序 最后返回数组
}
//quickSort([12,3,2,434,21,32,23,11])
//[2, 3, 11, 12, 21, 23, 32, 434]

未完待续