BubbleSort

  • 冒泡排序
/**
* 冒泡排序
*
* @param {Array<number>} array
* @returns {Array<number>}
*/
function BubbleSort(array: Array<number>) : Array<number> {
let retArray = [].concat(array)
for (let i = 0, n = retArray.length; i < n; i++) {
for (let j = 0; j < n - i - 1; j++) {
if (retArray[j] > retArray[j + 1]) {
let temp = retArray[j]
retArray[j] = retArray[j + 1]
retArray[j + 1] = temp
}
}
}
return retArray
}

ChooseSort

  • 选择排序
/**
* 选择排序
*
* @param {Array<number>} array
* @returns {Array<number>}
*/
function ChooseSort(array: Array<number>) : Array<number> {
let retArray = [].concat(array)
let min = 0, key = 0
for (let i = 0, n = retArray.length; i < n; i++) {
min = retArray[i]
key = i
for (let j = i + 1; j < n; j++) {
if (min > retArray[j]) {
key = j
min = retArray[j]
}
}
if (key != i) {
let temp = retArray[i]
retArray[i] = retArray[key]
retArray[key] = temp
}
}
return retArray
}

时间测试

  • 使用含1w个随机整数的数组测试排序效率
// 测试数据
let testArr = []
let len = 10000
let time = Date.now()
for (let i = 0; i < len; i++) {
testArr.push(~~(Math.random() * len))
}
// 答案
let resultArr = testArr.sort((a: number, b: number) => a - b)

// 冒泡排序
time = Date.now()
let ans1 = BubbleSort(testArr)
if (JSON.stringify(resultArr) === JSON.stringify(ans1)) {
console.log('BubbleSort Cost', Date.now() - time, 'ms')
}

// 选择排序
time = Date.now()
let ans2 = ChooseSort(testArr)
if (JSON.stringify(resultArr) === JSON.stringify(ans2)) {
console.log('ChooseSort Cost', Date.now() - time, 'ms')
}
  • 结果
BubbleSort Cost 112 ms
ChooseSort Cost 80 ms