选择排序
原理解析
第一轮:从数组中找到最小的数字,和第一个数字交换位置
第二轮:从第二个数字开始,找到最小的数字,和第二个数字交换位置
...
范例演示
以下表格里,红色表示选中的待排序的数字,蓝色表示最终排好的数字。
第一轮:
- 数组中找到最小值 3, 和数组第一个数10交换位置
第二轮:
- 从第二个数开始,数组中找到最小值 10, 和数组第二个数34交换位置
第三轮:
- 从第三个数开始,数组中找到最小值 21, 和数组第三个数21交换位置(自己不用交换)
...
第一轮 | 10 | 34 | 21 | 47 | 3 | 28 |
3 | 34 | 21 | 47 | 10 | 28 | |
第二轮 | 3 | 34 | 21 | 47 | 10 | 28 |
3 | 10 | 21 | 47 | 34 | 28 | |
第三轮 | 3 | 10 | 21 | 47 | 34 | 28 |
3 | 10 | 21 | 47 | 34 | 28 | |
第四轮 | 3 | 10 | 21 | 47 | 34 | 28 |
3 | 10 | 21 | 28 | 34 | 47 | |
第五轮 | 3 | 10 | 21 | 28 | 34 | 47 |
3 | 10 | 21 | 28 | 34 | 47 |
实现方式
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] ] //把每轮的第一个和当前轮的最小值交换位置
}
}
经浏览器测试,数组长度增加10倍,排序时间约增加100倍
复杂度分析
时间复杂度为 O(n^2) ,和上面的测试基本一致