Published on

选择排序笔记以及实现

Authors
  • avatar
    Name
    Et cetera
    Twitter

介绍选择排序

  • 首先在未排序的数列中找到最小(大)元素,然后存放到数列对应的起始位置

  • 然后继续在未排序的元素中继续寻找最小(大)元素,然后放到已排序序列的末尾(头部)

  • 一直递归到所有元素排序完成

优点

  • 如果某个元素处于正确的最终位置,那么不会移动

  • 选择排序每次交换一对元素,至少会有一个会移动到该元素最终位置,所以 n 个元素总共会进行最多 n-1 次交换

  • 在完全依靠交换去移动元素的方法中,选择排序属于很好的方法

实现思路

  • 遍历数组找到为排序部分最小值

    • 将未排序部分的第一个元素标记为最小值

    • 然后从未排序部分第二个元素开始遍历,每个后面的值和标记的最小值进行比较

    • 如果有小于最小值的元素,则重新标记该值为最小值

  • 将未排序部分最小值放知道已排序部分的后面

    • 交换最小值和已排序部分末尾元素的位置

    • 已排序部分加一,未排序部分减一

  • 重复步骤到变为有序数列

selectionSort.ts
function selectionSort(arr: number[]): number[] {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }

  return arr;
}

时间复杂度:

  • 最好情况: O(n^2)

所以大规模数据下选择排序的效率也偏低,相同场景下更多会选用快速排序、归并排序等...

View on GitHub