选择排序

一、原理解析

第一轮：从数组中找到最小的数字，和第一个数字交换位置

第二轮：从第二个数字开始，找到最小的数字，和第二个数字交换位置

...

就像排队一样，每次从未排好的队伍中“选择”一个最矮的，依次放到队伍的第一位、第二位...

二、范例演示

以下表格里，红色表示选中的待排序的数字，蓝色表示最终排好的数字。

第一轮：

1. 数组中找到最小值 3， 和数组第一个数10交换位置

第二轮：

1. 从第二个数开始，数组中找到最小值 10， 和数组第二个数34交换位置

第三轮：

1. 从第三个数开始，数组中找到最小值 21， 和数组第三个数21交换位置(自己不用交换)

...

三、实现方式

function sectionSort(arr) {
  for(let min = i = 0; i < arr.length /*i代表轮数*/; i++) {
    min = i
    for(let j = i + 1; j < arr.length; j++) {
      if(arr[min] > arr[j]) {
        min = j
      }
    }
    [ arr[i], arr[min] ] = [ arr[min], arr[i] ] //把每轮的第一个和当前轮的最小值交换位置
  }
}
 
var arr = [10, 34, 21, 47, 3, 28]
sectionSort(arr)
console.log(arr)

四、效率测试

下面我们测试排序性能。以下的代码中，randomArr 函数会生成一个随机数组， 数组长度默认是100， 最大值默认值是1000。 console.time 和 console.end 用来记录排序时间。

let arr = randomArr(10000, 100)
console.time('sectionSort')
sectionSort(arr)
console.timeEnd('sectionSort')
 
 
function randomArr( arrLen = 100, maxValue = 1000 ) {
  let arr = []
  for(let i = 0; i < arrLen; i++) {
    arr[i] = Math.floor((maxValue+1)*Math.random())
  }
  return arr
}
 
function sectionSort(arr) {
  for(let min = i = 0; i < arr.length /*i代表轮数*/; i++) {
    min = i
    for(let j = i + 1; j < arr.length; j++) {
      if(arr[min] > arr[j]) {
        min = j
      }
    }
    [ arr[i], arr[min] ] = [ arr[min], arr[i] ] //把每轮的第一个和当前轮的最小值交换位置
  }
}

经1000次测试，可以得出结论，数组长度增加10倍，排序时间约增加100倍

五、复杂度分析

时间复杂度为 O(n\^2) ，和上面的测试基本一致。

饥人谷一直致力于培养有灵魂的编程者，打造专业有爱的国内前端技术圈子。如造梦师一般帮助近千名不甘寂寞的追梦人把编程梦变为现实，他们以饥人谷为起点，足迹遍布包括facebook、阿里巴巴、百度、网易、京东、今日头条、大众美团、饿了么、ofo在内的国内外大小企业。 了解培训课程：加微信 xiedaimala03，官网:https://jirengu.com

本文作者：饥人谷若愚老师