选择排序

2021-02-22 算法

介绍

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法

冒泡排序和选择排序的区别:

  1. 冒泡排序是比较相邻位置的两个数，而选择排序是按顺序比较，找最大值或者最小值;
  2. 冒泡排序每一轮比较后，位置不对都需要换位置，选择排序每一轮比较都只需要换一次位置;
  3. 冒泡排序是通过数去找位置，选择排序是给定位置去找数;

冒泡排序优缺点:

  1. 优点:比较简单,空间复杂度较低，是稳定的;
  2. 缺点:时间复杂度太高，效率慢;

选择排序优缺点:

  1. 优点:一轮比较只需要换一次位置;
  2. 缺点:效率慢，不稳定（举个例子 5，8，5，2，9 我们知道第一遍选择第一个元素 5 会和 2 交换，那么原序列中 2 个 5 的相对位置前后顺序就破坏了）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function selectionSort(arr) {
  var len = arr.length;
  var minIndex, temp;
  for (var i = 0; i < len - 1; i++) {
    minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        // 寻找最小的数
        minIndex = j; // 将最小数的索引保存
      }
    }
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

动图展示

#排序