排序算法

1type SortRule = 'descend' | 'ascend';
2
3// 冒泡排序（默认升序）
4export function bubbleSort(list: number[], rule: SortRule = 'ascend') {
5  let i = list.length - 1;
6  while (i > 0) {
7    let position = 0; // 记录最后一次发生交换的位置，大于position的部分说明无需排序
8    for (let j = 0; j < i; j += 1) {
9      const condition = rule === 'ascend' ? (list[j] > list[j + 1]) : (list[j] < list[j + 1]);
10      if (condition) {
11        position = j;
12        const temp = list[j];
13        list[j] = list[j + 1];
14        list[j + 1] = temp;
15      }
16    }
17    i = position;
18  }
19  return list;
20}
21
22// 选择排序
23export function selectionSort(list: number[], rule: SortRule = 'ascend') {
24  let i = list.length - 1;
25  while (i > 0) {
26    let index = i;
27    let target = list[i];
28    for (let j = 0; j < i; j += 1) {
29      if (rule === 'ascend' ? (list[j] > target) : (list[j] < target)) {
30        index = j;
31        target = list[j];
32      }
33    }
34    // 每次循环都把最大/最小的值放到末尾
35    list[index] = list[i];
36    list[i] = target;
37    i -= 1;
38  }
39  return list;
40}
41
42// 插入排序
43export function insertionSort(list: number[], rule: SortRule = 'ascend') {
44  for (let i = 0; i < list.length; i += 1) {
45    const value = list[i];
46    let j = i - 1;
47    for (; j > -1 && (rule === 'ascend' ? (list[j] > value) : (list[j] < value)); j -= 1) {
48      // 把 index < i 中大于/小于value的元素向前移一位
49      list[j + 1] = list[j];
50    }
51    // 插入value
52    list[j + 1] = value;
53  }
54  return list;
55}