JS 常用排序方法

1.数组 sort() 方法排序

var arr = [1, 4, 3, 11, 8, 23, 45, 96, 70, 31, 6, 57];

arr.sort();

console.log(arr);
// > [1, 11, 23, 3, 31, 4, 45, 57, 6, 70, 8, 96]

默认情况下，数组 sort() 方法将值作为字符串进行排序，即先对比第一个字符、第二个字符…。

传入比对函数，可以实现按数字值得大小进行比较。

升序：

arr.sort(function(a, b) {
  return a - b;
});

console.log(arr);
// > [1, 3, 4, 6, 8, 11, 23, 31, 45, 57, 70, 96]

降序：

arr.sort(function(a, b) {
  return b - a;
});

console.log(arr);
// > [96, 70, 57, 45, 31, 23, 11, 8, 6, 4, 3, 1]

2.冒泡排序

原理：依次比较相邻的两个元素，如果前一个比后一个大，则将他们交换位置。在第一轮对比完成时，最后一个元素的值是最大。以此类推，第二轮对比完成时，倒数第二个元素的值是第二大的；并且，已经计算出的排序的元素不再参与下一轮比较。

代码实现：

function bubbleSort(arr) {
  var i, j, temp;

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

        arr[j] = arr[j + 1];

        arr[j + 1] = temp;
      }
    }
  }
}

3.选择排序

原理：找到值最小的元素，放在第一位；在剩下的元素里，找到值第二小的元素，放在第二位；以此类推。

代码实现：

function chooseSort(arr) {
  var i, j, minIndex, temp;

  for (i = 0; i < arr.length - 1; i++) {
    minIndex = i;

    for (j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }

    temp = arr[i];

    arr[i] = arr[minIndex];

    arr[minIndex] = temp;
  }
}

4.插入排序

原理：将第一个元素认为已经排序，下一个元素与已经排好序的集合从后向前对比，插入到小于该元素的位置，其它元素依次向后移。

代码实现：

function insertSort(arr) {
  var i, j, temp;

  for (i = 1; i < arr.length; i++) {
    temp = arr[i];

    j = i - 1;

    while (j >= 0 && temp < arr[j]) {
      arr[j + 1] = arr[j];
      j--;
    }

    arr[j + 1] = temp
  }
}

5.快速排序

原理：取出索引在中间的一个值，比这个值小或相等的元素放到前面，大的元素放到后面，再拼接起来，如此递归执行。

代码实现：

function quickSort(arr) {
  var i, midIndex, midVal, leftArr, rightArr;

  if (arr.length <= 1) {
    return arr;
  }
  
  midIndex = Math.floor(arr.length / 2);

  midVal = arr.splice(midIndex, 1);

  leftArr = [];
  rightArr = [];

  for (i = 0; i < arr.length; i++){
      if (arr[i] <= midVal) {
        leftArr.push(arr[i]);
      }
      else {
        rightArr.push(arr[i]);
      }
  }

  return quickSort(leftArr).concat(midVal, quickSort(rightArr));
}