Appearance

Return to top
On this page

TypeScript实现十大排序算法(二) - 选择排序 ​

选择排序 （Selection Sort) 是一种简单的排序算法 ​

它的基本思想是

  • 首先在未排序的数列中找到最小或者最大的元素, 然后将其放到数组起始的位置
  • 接着再从剩余未排序的元素中找到最小或者最大的元素 放到已排序数列的末尾
  • 以此类推知道所有元素排序完毕

选择排序的流程 ​

  1. 首先将要排序的数组复制到一个新数组中，这样原数组不会被改变。
  2. 初始化最小数字的索引值为0，然后在数组中循环，在当前索引后面的元素中找到最小的数字的索引。
  3. 如果当前索引位置的数字不是最小数字，那么将这两个数字互换。
  4. 继续寻找下一个数字，直到索引到最后一个元素，此时整个数组已经是从小到大排序的了。
  5. 重复上面的步骤，每次排序的范围都会减少一个，直到整个数组排序完毕。

代码实现 ​

ts
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);
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);

以下是代码的详细说明：

首先循环遍历整个数组。

在每一次循环中，预设最小数的索引为当前循环的索引。

在后面的数中寻找更小的数，如果找到更小的数，记录它的索引。

如果当前循环的索引不是最小数的索引，交换它们。

重复步骤2-4，直到遍历完整个数组。

返回排序后的数组。

选择排序时间复杂度 ​

  • 计算选择排序算法的时间复杂度，通常是通过分析算法中每一步的执行次数来确定的。

  • 我们分析选择排序中的每一步，再将每一步的时间复杂度加起来，最后得到的就是选择排序的时间复杂度。

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

  • 因此，内层循环的时间复杂度是O(N^2)。 外层循环也要执行N-1次，因此，它的时间复杂度也是O(N^2)。 所以，整个选择排序算法的时间复杂度是O(N^2)。

  • 选择排序是一种简单易懂的排序算法。

  • 它的基本思想是遍历整个列表，每次找出最小的元素，并且将它移到列表的最左边，重复这个过程直到整个列表都有序排列。 在平均情况下，选择排序的时间复杂度为 O(n^2)，在最坏情况下与最好情况下都为 O(n^2)。

  • 选择排序在数据规模较小时非常适用，在数据规模较大时不够高效。

在github 上编辑文档