掌握常见的几种排序-选择排序

[maicFir]

选择排序是一种简单的排序，时间复杂度是 O(n^2)，在未排序的数组中找到最小的那个数字，然后将其放到起始位置，从剩下未排序的数据中继续寻找最小的元素，将其放到已排序的末尾，以次类推，直到所有元素排序结束为止。

我们先看下选择排序的一段代码

function selectSort(arr) {
  const len = arr.length;
  var minIndex, temp;
  for (let i = 0; i < len; i++) {
    minIndex = i; //假设当前循环索引是最小元素
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j; // 寻找最小的值
      }
    }
    // 交换minIndex与i元素的值
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}
selectSort([6, 12, 80, 91, 8, 0]);

我们画个图还原排序所有过程，具体如下

从每次循环中我们可以知道选择排序，实际上就是先确认起始位置的索引，假设第一个是最小位置，从剩余元素中找到比第一个位置小的值，如果剩余的元素有比它小，那么确认当前索引为最小索引值，并交换两个元素的位置。

然后再从第二元素开始，假设第二元素是最小值，然后从剩余元素中找最小的元素，如果剩余元素有比它小就交换位置，如果没有，就正常不交换位置，直到循环到最后一个元素为止。

再言简意赅点，选择排序就是

1、假设第一个元素是最小值

2、从剩余元素中选择与第一个元素比较元素大小，确认最小索引值，然后交换位置

3、从剩余位置依次循环，假设剩余位置为最小值，然后从剩余元素中选择与之进行比较，然后确认是否交换位置

4、直到循环到最后一个索引为止

最后看一张图

总结

1、选择排序时间复制度是 O(n^2)

2、假设首个元素是最小的元素，在剩余未排序的元素中与之进行比较，如果比它小，就确认最小位置索引，与之交换位置

3、在剩余未排序的所有的元素中，假设首个元素是最小值，然后与剩余元素进行依次比较，确认元素当前最小最小索引，交换位置，依次循环，直到最后循环结束为止