公用的数据

1

var nums = [4, 2, 16, 12, 32, 21, 33, 1];

array.sort

1
2
3
4
5
6
7
8
9

nums.sort(function(a, b) {
  if (a < b) {
    return -1;
  }
  if (a > b) {
    return 1;
  }
  return 0;
});

冒泡排序

依次交换相邻的两个数字的顺序（大的在后），这样交换一次之后，最大的就在后面了，再交换一变，最大的两个数在后面的…

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

选择排序

将剩余数据最小的放在开始，再奖剩余数据最小的放在第二位…

和冒泡排序的区别，冒泡：两两交换。选择：剩余最小的交换到剩余数的最前面

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

function selectSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    var min = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[min]) {
        [arr[min], arr[j]] = [arr[j], arr[min]];
      }
    }
  }
}

插入排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function insertSort(arr) {
  var len = arr.length;
  for (var i = 1; i < len; i++) {
    var key = arr[i];
    var j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

归并排序

是一种分治算法

假设数据有 n 个，先对 n/2 组数进行排序，再对 n/4 组书进行排序…直到 n/m 等于 1 的时候

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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, right);
}

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  var mid = Math.floor(arr.length / 2);
  var left = arr.slice(0, mid);
  var right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));
}

快速排序

以第一个数为基准值，大于基准值的放右边，小于基准值的放左边，然后递归处理左边的数据和右边的数据

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function quickSort(arr) {
  var len = arr.length;
  var basic = arr[0];
  var left = [];
  var right = [];
  for (var i = 1; i < len; i++) {
    var iv = arr[i];
    iv >= basic && right.push(iv); // to avoid repeatly element.
    iv < basic && left.push(iv);
  }
  return quickSort(left).concat(basic, quickSort(right));
}