关于程序员:TypeScript实现十大排序算法二-选择排序

一. 抉择排序的定义

抉择排序（Selection Sort）是一种简略的排序算法。

它的根本思维是：

• 首先在未排序的数列中找到最小（大）元素，而后将其寄存到数列的起始地位；
• 接着，再从残余未排序的元素中持续寻找最小（大）元素，而后放到已排序序列的开端。
• 以此类推，直到所有元素均排序结束。

抉择排序的次要长处与数据挪动无关。

• 如果某个元素位于正确的最终地位，则它不会被挪动。
• 抉择排序每次替换一对元素，它们当中至多有一个将被移到其最终地位上，因而对 n 个元素的表进行排序总共进行至少 n - 1 次替换。
• 在所有的齐全依附替换去挪动元素的排序办法中，抉择排序属于十分好的一种。

抉择排序的实现形式很简略，并且容易了解，因而它是学习排序算法的很好的入门路径。

二. 抉择排序的流程

抉择排序流程具体步骤：

1. 首先将要排序的数组复制到一个新数组中，这样原数组不会被扭转。
2. 初始化最小数字的索引值为 0，而后在数组中循环，在以后索引前面的元素中找到最小的数字的索引。
3. 如果以后索引地位的数字不是最小数字，那么将这两个数字调换。
4. 持续寻找下一个数字，直到索引到最初一个元素，此时整个数组曾经是从小到大排序的了。
5. 反复下面的步骤，每次排序的范畴都会缩小一个，直到整个数组排序结束。

三. 抉择排序的图解

四. 抉择排序的代码

以下是 TypeScript 实现的抉择排序代码：

function selectionSort(arr: number[]): number[] {
  // 循环遍历整个数组
  for (let i = 0; i < arr.length; i++) {
    // 预设最小数的索引为以后循环的索引
    let minIndex = i;
    // 在前面的数中寻找更小的数
    for (let j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {
        // 如果找到更小的数，记录它的索引
        minIndex = j;
      }
    }
    // 如果以后循环的索引不是最小数的索引，替换它们
    if (i !== minIndex) {[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
  // 返回排序后的数组
  return arr;
}

// 测试数据
const testArr = [5, 2, 9, 1, 5, 6];
// 调用插入排序函数
const sortedArr = selectionSort(testArr);
// 打印后果
console.log(sortedArr);

以下是代码的具体阐明：

1. 首先循环遍历整个数组。
2. 在每一次循环中，预设最小数的索引为以后循环的索引。
3. 在前面的数中寻找更小的数，如果找到更小的数，记录它的索引。
4. 如果以后循环的索引不是最小数的索引，替换它们。
5. 反复步骤 2 -4，直到遍历残缺个数组。
6. 返回排序后的数组。

五. 抉择排序的工夫复杂度

计算抉择排序算法的工夫复杂度，通常是通过剖析算法中每一步的执行次数来确定的。

咱们剖析抉择排序中的每一步，再将每一步的工夫复杂度加起来，最初失去的就是抉择排序的工夫复杂度。

• 在抉择排序中，最多的操作是内层循环，其执行了 N - 1 次，并且每次执行内层循环都要花费 O(N) 的工夫。

  • 因而，内层循环的工夫复杂度是 O(N^2)。

• 外层循环也要执行 N - 1 次，因而，它的工夫复杂度也是 O(N^2)。

  • 所以，整个抉择排序算法的工夫复杂度是 O(N^2)。

六. 抉择排序的总结

• 抉择排序是一种简略易懂的排序算法。
• 它的根本思维是遍历整个列表，每次找出最小的元素，并且将它移到列表的最右边，反复这个过程直到整个列表都有序排列。
• 在均匀状况下，抉择排序的工夫复杂度为 O(n^2)，在最坏状况下与最好状况下都为 O(n^2)。
• 抉择排序在数据规模较小时十分实用，在数据规模较大时不够高效。

本文由 mdnice 多平台公布