Ryan Shang

生死看淡，不服就干

0%

数组排序

发表于 分类于

数组排序的几种方法。

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function bubbleSort(ary) {
  var flag = false;
  var temp = null;
  for (var i = 0; i < ary.length - 1; i++) {
    for (var j = 0; j < ary.length - 1 - i; j++) {
      if (ary[j] > ary[j + 1]) {
        temp = ary[j];
        ary[j] = ary[j + 1];
        ary[j + 1] = temp;
        flag = true;
      }
    }
    // 一轮过后没有变化，则已经是结果
    if (flag) {
      flag = false;
    } else {
      break;
    }
  }
  return ary;
}

插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function insertSort(ary) {
  var newAry = [];
  newAry.push(ary[0]);
  for (var i = 1; i < ary.length; i++) {
    var cur = ary[i];
    for (var j = newAry.length - 1; j >= 0;) {
      if (cur < newAry[j]) {
        j--;
        if (j === -1) {
          newAry.unshift(cur);
        }
      } else {
        newAry.splice(j + 1, 0, cur);
        j = -1;
      }
    }
  }
  return newAry;
}

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function quickSort(ary) {
  if (ary.length <= 1) {
    return ary;
  }
  var pointIndex = Math.floor(ary.length / 2);
  var pointValue = ary.splice(pointIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < ary.length; i++) {
    var cur = ary[i];
    cur < pointValue ? left.push(cur) : right.push(cur);
  }
  return quickSort(left).concat([pointValue], quickSort(right));
}