vlambda博客
学习文章列表

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

选择排序是一种简单的排序,时间复杂度是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、在剩余未排序的所有的元素中,假设首个元素是最小值,然后与剩余元素进行依次比较,确认元素当前最小最小索引,交换位置,依次循环,直到最后循环结束为止


最后,喜欢的点个赞,在看,转发,收藏等于学会,欢迎关注Web技术学苑,好好学习,天天向上!

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



长按二维码识别关注

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



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

点个在看你最好看