十大经典排序算法

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

// TypeScript实现
export function bubbleSort(arr: number[]) {
  const len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let sorted = true;
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        sorted = false;
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
    if (sorted) break;
  }
  return arr;
}

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

// TypeScript实现
export function selectionSort(arr: number[]) {
  const len = arr.length;
  let minIndex: number;
  for (let i = 0; i < len - 1; i++) {
    minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  return arr;
}

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

// TypeScript实现
export function insertionSort(arr: number[]) {
  const len = arr.length;
  let j: number;
  let temp: number;
  for (let i = 1; i < len; i++) {
    temp = arr[i];
    j = i - 1;
    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
  return arr;
}

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

// TypeScript实现
export function shellSort(arr: number[]) {
  const len = arr.length;
  // 步长序列 = n / 2^i
  for (let gap = len >> 1; gap > 0; gap >>= 1) {
    // 执行插入排序
    // i = 0 默认已排序，所以从 0 + gap 的位置开始执行插入
    for (let i = gap; i < len; i++) {
      const temp = arr[i];
      let j = i - gap;
      while (j >= 0 && arr[j] > temp) {
        arr[j + gap] = arr[j];
        j -= gap;
      }
      arr[j + gap] = temp;
    }
  }

  return arr;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

var i = 0;
function inc() {
  i++;
  inc();
}

try {
  inc();
} catch (e) {
  console.log("Maximum stack size is", i, "in your current browser");
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

// TypeScript实现（迭代实现）
export function mergeSort(arr: number[]) {
  const len = arr.length;

  if (len < 2) return arr;

  const _helperArr = new Array(len);

  /**
   * 用于合并相邻的两组序列。
   * 说明：
   * 左侧边界为左侧序列的起始元素位置
   * 中间点是左侧序列最后元素的位置+1，也是右侧序列的起始元素位置
   * 右侧边界为右侧序列的右边界，也是右侧序列的最后元素位置+1
   * @param leftIdx 左侧边界
   * @param midIdx 中间点
   * @param rightIdx 右侧边界
   * @param originArr 原始数组
   * @param helperArr 辅助数组
   */
  function merge(
    leftIdx: number,
    midIdx: number,
    rightIdx: number,
    originArr: number[],
    helperArr: number[]
  ) {
    let i = leftIdx;
    let j = midIdx;
    let helperArrIndex = leftIdx;

    // 先将归并后的数组填充到辅助数组中
    while (i < midIdx && j < rightIdx) {
      if (originArr[i] < originArr[j]) {
        helperArr[helperArrIndex] = originArr[i];
        i++;
      } else {
        helperArr[helperArrIndex] = originArr[j];
        j++;
      }
      helperArrIndex++;
    }

    while (i < midIdx) {
      helperArr[helperArrIndex] = originArr[i];
      i++;
      helperArrIndex++;
    }

    while (j < rightIdx) {
      helperArr[helperArrIndex] = originArr[j];
      j++;
      helperArrIndex++;
    }

    // 将序列从辅助数组中复制到原数组
    for (
      helperArrIndex = leftIdx;
      helperArrIndex < rightIdx;
      helperArrIndex++
    ) {
      originArr[helperArrIndex] = helperArr[helperArrIndex];
    }
  }

  let groupSize = 1;
  while (Math.ceil(len / groupSize) > 1) {
    for (let i = 0; i < len; i += groupSize * 2) {
      // 合并每相邻两组，得到新的有序组
      let midIdx: number, rightIdx: number;
      midIdx = (midIdx = i + groupSize) > len ? len : midIdx;
      rightIdx = (rightIdx = i + groupSize * 2) > len ? len : rightIdx;
      merge(i, midIdx, rightIdx, arr, _helperArr);
    }

    // 分组大小翻倍
    groupSize <<= 1;
  }

  return arr;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

// TypeScript实现
export function quickSort(
  arr: number[],
  left: number = 0,
  right: number = arr.length - 1
) {
  if (left >= right) return arr;

  const partitionIdx = partition(arr, left, right);
  quickSort(arr, left, partitionIdx - 1);
  quickSort(arr, partitionIdx + 1, right);

  return arr;
}

// 对于序列的左、中、右三个值，取中值作为基准值
function getPivotIndex(arr: number[], left: number, right: number) {
  const mid = left + ((right - left) >> 1);
  const midValue = arr[mid];
  const leftValue = arr[left];
  const rightValue = arr[right];
  if (leftValue <= rightValue) {
    if (midValue < leftValue) {
      return left;
    } else if (midValue > rightValue) {
      return right;
    } else {
      return mid;
    }
  } else {
    if (midValue < rightValue) {
      return right;
    } else if (midValue > leftValue) {
      return left;
    } else {
      return mid;
    }
  }
}

/**
 * 对于给定的子序列，取一个基准值，并根据基准值分成左右区间
 * 返回最后基准值所在的位置
 */
function partition(arr: number[], left: number, right: number) {
  const pivotIdx = getPivotIndex(arr, left, right);
  // 先将基准值放在最左侧
  [arr[pivotIdx], arr[left]] = [arr[left], arr[pivotIdx]];
  let i = left + 1;
  let leftPartIdx = left;

  // 前后指针法分区
  // leftPartIdx 代表了左侧序列最后一个元素的位置
  // 搜索指针会一直向前移动
  while (i <= right) {
    // 如果搜索指针找到的元素小于等于基准值
    // 则表示该元素应该纳入左侧序列
    if (arr[i] < arr[left]) {
      // 存在距离，说明 leftPartIdx 右侧元素是大于 pivot 的
      // 则交换两个元素，将较小元素放置到左侧序列的右侧
      if (i - leftPartIdx > 1) {
        [arr[leftPartIdx + 1], arr[i]] = [arr[i], arr[leftPartIdx + 1]];
      }
      // 左侧序列的长度+1
      leftPartIdx++;
    }
    i++;
  }

  // 将基准值与左侧序列最后一位元素交换
  [arr[leftPartIdx], arr[left]] = [arr[left], arr[leftPartIdx]];

  return leftPartIdx;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// TypeScript实现
export function heapSort(arr: number[]) {
  let len = arr.length;

  // build max heap
  for (let i = Math.floor((len - 1) / 2); i >= 0; i--) {
    maxHeapify(arr, i, len);
  }

  // sort loop
  while (len) {
    [arr[0], arr[len - 1]] = [arr[len - 1], arr[0]];
    len--;
    maxHeapify(arr, 0, len);
  }

  return arr;
}

function maxHeapify(arr: number[], index: number, heapSize: number) {
  let maxIdx: number;
  let leftIdx: number;
  let rightIdx: number;

  while (true) {
    maxIdx = index;
    leftIdx = 2 * maxIdx + 1;
    rightIdx = 2 * maxIdx + 2;

    if (leftIdx < heapSize && arr[leftIdx] > arr[maxIdx]) {
      maxIdx = leftIdx;
    }

    if (rightIdx < heapSize && arr[rightIdx] > arr[maxIdx]) {
      maxIdx = rightIdx;
    }

    if (maxIdx !== index) {
      [arr[maxIdx], arr[index]] = [arr[index], arr[maxIdx]];
      index = maxIdx;
    } else {
      break;
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// TypeScript实现
export function countingSort(arr: number[]) {
  let max = arr[0];
  let min = arr[0];

  // 找出最大值、最小值
  for (const n of arr) {
    if (n > max) {
      max = n;
    }
    if (n < min) {
      min = n;
    }
  }

  // 根据最大值、最小值初始化计数数组
  const count_arr: number[] = new Array(max - min + 1);
  // 计数
  for (const n of arr) {
    count_arr[n - min] = count_arr[n - min] ? count_arr[n - min] + 1 : 1;
  }

  // 累加
  for (let i = 1; i < count_arr.length; i++) {
    if (!count_arr[i]) count_arr[i] = 0;
    count_arr[i] += count_arr[i - 1];
  }

  const res = new Array(arr.length);
  // 根据位置信息重新排列数组
  // 将 arr[i] 元素放置到 res 数组中正确的排序位置
  // 为了保持稳定性，需要采用倒序
  for (let i = arr.length - 1; i >= 0; i--) {
    res[--count_arr[arr[i] - min]] = arr[i];
  }

  return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

// TypeScript实现
export function bucketSort(arr: number[], bucketNums = 5) {
  let max = arr[0];
  let min = arr[0];

  // 找出最大值、最小值
  for (const n of arr) {
    if (n > max) {
      max = n;
    }
    if (n < min) {
      min = n;
    }
  }

  const bucketSize = Math.floor((max - min) / bucketNums) + 1;
  const buckets: number[][] = [];

  for (let i = 0; i < arr.length; i++) {
    // 将元素放入桶中
    const bIdx = Math.floor((arr[i] - min) / bucketSize);
    const bucketArr = buckets[bIdx] || (buckets[bIdx] = []);
    bucketArr.push(arr[i]);
    // 用冒泡排序保持桶内元素有序
    for (let j = bucketArr.length - 1; j > 0; j--) {
      if (bucketArr[j - 1] > bucketArr[j]) {
        [bucketArr[j - 1], bucketArr[j]] = [bucketArr[j], bucketArr[j - 1]];
      }
    }
  }

  let res: number[] = [];
  buckets.forEach((bucketArr) => {
    res = res.concat(bucketArr);
  });

  return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

// TypeScript实现
export function radixSortLSD(arr: number[]) {
  let max = arr[0];

  // 找出最大值
  for (const n of arr) {
    if (n > max) {
      max = n;
    }
  }

  // 确定最大位数
  let maxDigit = 0;
  while (max) {
    maxDigit++;
    max = Math.floor(max / 10);
  }

  const buckets: number[][] = [];
  let mod = 10;
  // 根据最大位数进行 maxDigit 轮排序
  // 由低位至高位排序
  for (let k = 0; k < maxDigit; k++, mod *= 10) {
    // 根据当前位数字放入对应桶中
    for (let i = 0; i < arr.length; i++) {
      const bucketIdx = Math.floor((arr[i] % mod) / (mod / 10));
      const bucketArr = buckets[bucketIdx] || (buckets[bucketIdx] = []);
      bucketArr.push(arr[i]);
    }
    // 从桶中依次取出元素排序
    let idx = 0;
    for (let j = 0; j < buckets.length; j++) {
      if (!buckets[j]) continue;
      while (buckets[j].length) {
        arr[idx] = buckets[j].shift();
        idx++;
      }
    }
  }

  return arr;
}