Selection Sort

选择排序，是一种从 0 索引开始循环遍历数组，每一次遍历就找到索引后方最小的数值，将它们交换位置，来实现从小到大排序的算法。

实现

简单来说，执行过程是以下几步：

n 是数组长度

• 处理索引 0 位置，遍历剩余数据[1,...,n-1]找到最小值的选项的索引，将它与 0 索引数据交换
• 处理索引 1 位置，遍历剩余数据[2,...,n-1]找到最小值的选项的索引，将它与 1 索引数据交换
• ...
• 处理索引 n-2 位置，遍历剩余数据找到最小值的选项的索引，将它与 n-2 索引数据交换
• 最后一个数据 n-1，一定是最大数，无需处理

TypeScript 实现代码：

const selectionSort = (data: number[]) => {
  const len = data.length;
  for (let i = 0; i < len - 1; i += 1) {
    let minIndex = i;
    for (let j = i + 1; j < len; j += 1) {
      if (data[j] < data[minIndex]) {
        minIndex = j;
      }
    }
    const temp = data[i];
    data[i] = data[minIndex];
    data[minIndex] = temp;
  }
  return data;
};

const testData = [5, 3, 2, 4, 1];
// output: [1, 2, 3, 4, 5]
console.log(selectionSort(testData));

复杂度

时间上由于每一个元素都会进行剩余数组的遍历，意味着执行了 n² 次，而空间上只是在数值索引之间的交换，并没有额外的内存申请，因此算法时间复杂度是 O(n²), 空间复杂度是 O(1).

改进

但是现实中不会这么简单，往往需要排序的数据是一个复杂的数据结构，需要配备额外的比较函数来实现大小的比较，比如需要针对 task 列表的优先级来排序：

const selectionSort = <T>(data: T[], compareFn: (a: T, b: T) => number) => {
  const len = data.length;
  for (let i = 0; i < len - 1; i += 1) {
    let minIndex = i;
    for (let j = i + 1; j < len; j += 1) {
      if (compareFn(data[j], data[minIndex]) < 0) {
        minIndex = j;
      }
    }
    const temp = data[i];
    data[i] = data[minIndex];
    data[minIndex] = temp;
  }
  return data;
};

const taskData = [
  { id: '1', name: 'task1', priority: 2 },
  { id: '2', name: 'task2', priority: 3 },
  { id: '3', name: 'task3', priority: 1 },
  { id: '4', name: 'task4', priority: 1 },
  { id: '5', name: 'task5', priority: 5 },
];
const sortedTaskData = selectionSort(
  taskData,
  (a, b) => a.priority - b.priority
);
// output :
// [
//     {
//         "id": "3",
//         "name": "task3",
//         "priority": 1
//     },
//     {
//         "id": "4",
//         "name": "task4",
//         "priority": 1
//     },
//     {
//         "id": "1",
//         "name": "task1",
//         "priority": 2
//     },
//     {
//         "id": "2",
//         "name": "task2",
//         "priority": 3
//     },
//     {
//         "id": "5",
//         "name": "task5",
//         "priority": 5
//     }
// ]
console.log(sortedTaskData);