image.png

1. 冒泡排序

对一个数组进行从小到大的排序。冒泡排序的特点是，每一轮循环后，最大的一个数被交换到末尾，因此，下一轮循环就可以“刨除”最后的数，每一轮循环都比上一轮循环的结束位置靠前一位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const array = [28, 12, 89, 73, 65, 18, 96, 50, 8, 36];

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const a = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = a;
      }
    }
  }
  return arr;
}

const res = bubbleSort(array); // [8, 12, 18, 28, 36,50, 65, 73, 89, 96]

2. 插入排序

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

思路： 1.默认从 i = 1 开始判断，这样 preIndex 自然是内部循环的游标；
2.current 保存 arr[i]，通过循环来确定 current 的最终位置； 3.每个内循环开始的时候，arr[i] === current === arr[preIndex + 1]，所以在内循环首次时 arr[preIndex + 1] = arr[preIndex] 的时候不必担心 arr[i] 的值丢失； 4.总体思路是，需要排位的元素先额外缓存起来，然后套用内循环，使得需要调整的元素赋值给它后面的一个位置上，形成依次挪位，最后因为内循环在判断条件不生效的时候停止意味着找到了需要排位的元素的正确位置，然后赋值上去，完成排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function Insertion(arr) {
  let len = arr.length;
  let preIndex, current;
  for (let i = 1; i < len; i++) {
    preIndex = i - 1;
    current = arr[i];
    while (preIndex >= 0 && current < arr[preIndex]) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = current;
  }
  return arr;
}

var arr = [3, 5, 7, 1, 4, 56, 12, 78, 25, 0, 9, 8, 42, 37];
Insertion(arr);

3. 快速排序

思路：

  • 先从数列中取出一个数作为“基准”。
  • 分区过程：将比这个“基准”大的数全放到“基准”的右边，小于或等于“基准”的数全放到“基准”的左边。
  • 再对左右区间重复第二步，直到各区间只有一个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var quickSort = function (arr) {
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2); //基准位置（理论上可任意选取）
  var pivot = arr.splice(pivotIndex, 1)[0]; //基准数
  var left = [];
  var right = [];
  for (var 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)); //链接左数组、基准数构成的数组、右数组
};