排序算法重构

这本来是我2017年写的排序算法汇总。想着工作了几年攒了一点经验，趁着有空重新撸一次。要求：1，尽量精简代码；2，用TypeScript；3，采用SOLID设计模式原则。

资源

• 原文链接：排序算法——BAT必考

• 排序方法动态图解

• github仓库地址

共有方法提取：

import { IMinInfo } from "../interface";
// 换位置处理函数
export const switchPosition = (
  minInfo: IMinInfo,
  targetIndex: number,
  targetList: number[]
): number[] => {
  // 防止污染源数据，进行深拷贝
  const copyArr = JSON.parse(JSON.stringify(targetList));
  const temp = copyArr[targetIndex];
  copyArr[targetIndex] = copyArr[minInfo.index];
  copyArr[minInfo.index] = temp;
  return copyArr;
};

// 移动位置处理函数
export const insertPosition = (
  fromDataIndex: number,
  toDataIndex: number,
  targetList: number[]
) => {
  // 防止污染源数据，进行深拷贝
  const copyArr = JSON.parse(JSON.stringify(targetList));
  const deleteItem = copyArr.splice(fromDataIndex, 1);
  copyArr.splice(toDataIndex, 0, deleteItem[0]);
  return copyArr;
};

八种思路：

1. 冒泡法

import { switchPosition } from "../utils";
// 源数据
const dataSource: number[] = [4, 7, 29, 1, 3, 23, 25, 26, 43, 55, 2];
const bubble = (data: number[]) => {
  // 防止污染源数据，进行深拷贝
  let copyArr: number[] = JSON.parse(JSON.stringify(data));
  for (let i = 0; i < copyArr.length; i++) {
    for (let j = 0; j < copyArr.length - i; j++) {
      const leftItem: number = copyArr[j],
        rightItem: number = copyArr[j + 1];
      if (leftItem > rightItem) {
        copyArr = switchPosition({ value: NaN, index: j + 1 }, j, copyArr);
      }
    }
  }
  return copyArr;
};
bubble(dataSource);

2. 选择排序法

import { switchPosition } from "../utils";
import { IMinInfo } from "../interface";
// 源数据
const dataSource: number[] = [4, 7, 29, 1, 3, 23, 25, 26, 43, 55, 2];
const select = (data: number[]) => {
  // 防止污染源数据，进行深拷贝
  let copyArr: number[] = JSON.parse(JSON.stringify(data));
  for (let i = 0; i < copyArr.length; i++) {
    let minInfo: IMinInfo = { value: copyArr[i], index: i };
    for (let j = i; j < copyArr.length; j++) {
      if (minInfo["value"] > copyArr[j]) {
        minInfo["value"] = copyArr[j];
        minInfo["index"] = j;
      }
    }
    copyArr = switchPosition(minInfo, i, copyArr);
    return copyArr;
  }
};
select(dataSource);

3. 插入排序

import { insertPosition } from "../utils";
import { ITargetInfo } from "../interface";
// 源数据
const dataSource: number[] = [4, 7, 29, 1, 3, 23, 25, 26, 43, 55, 2];
const insertion = (data: number[]) => {
  // 防止污染源数据，进行深拷贝
  let copyArr: number[] = JSON.parse(JSON.stringify(data));
  for (let i = 0; i < copyArr.length; i++) {
    let targetInfo: ITargetInfo = { value: copyArr[i], index: i };
    for (let j = i - 1; j >= 0; j--) {
      if (targetInfo["value"] < copyArr[j]) {
        copyArr = insertPosition(targetInfo["index"], j, copyArr);
        targetInfo["index"] = j;
        targetInfo["value"] = copyArr[j];
        continue;
      }
    }
  }
  return copyArr;
};
insertion(dataSource);

4. 归并排序

// 源数据
const dataSource: number[] = [4, 7, 29, 1, 3, 23, 25, 26, 43, 55, 2];
const recursion = (data: number[]): number[] => {
  // 防止污染源数据，进行深拷贝
  let copyArr: number[] = JSON.parse(JSON.stringify(data));
  return handleSplit(copyArr);
};
// 分隔递归
const handleSplit = (targetList: number[]) => {
  if (targetList.length < 2) return targetList;
  const halfLength: number = Math.ceil(targetList.length / 2);
  let leftList = targetList.slice(0, halfLength);
  let rightList = targetList.slice(halfLength);
  return handleRecursion(handleSplit(leftList), handleSplit(rightList));
};
// 排序处理函数
const handleRecursion = (leftList: number[], rightList: number[]) => {
  let result: number[] = [];
  while (leftList.length && rightList.length) {
    if (leftList[0] <= rightList[0]) {
      result.push(leftList.shift());
    } else {
      result.push(rightList.shift());
    }
  }
  while (leftList.length) {
    result.push(leftList.shift());
  }
  while (rightList.length) {
    result.push(rightList.shift());
  }
  return result;
};
recursion(dataSource);

5. 快速排序

6. 随机快速排法

7. 计数排序

8. 基数排法