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
}

InsertSort

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

ShellSort

  • 希尔排序
/**
* 希尔排序
*
* @param {Array<number>} array
* @returns {Array<number>}
*/
function ShellSort(array: Array<number>) : Array<number> {
let retArray = [].concat(array)
let n = retArray.length
let gap = ~~(n / 2)
while (gap >= 1) {
for (let i = gap; i < n; i++) {
let temp = retArray[i]
let j = i
while(j > gap - 1 && retArray[j - gap] > temp) {
retArray[j] = retArray[j - gap]
j -= gap
}
retArray[j] = temp
}
gap = ~~(gap / 2)
}
return retArray
}

QuickSort

  • 快速排序
/**
* 快速排序
*
* @param {Array<number>} array
* @returns {Array<number>}
*/
function QuickSort(array: Array<number>) : Array<number> {
let retArray = [].concat(array)
let n = retArray.length
/**
* 快速排序的递归方法
*
* @param {number} left
* @param {number} right
*/
function quick(begin: number, end: number) {

//递归出口
if (begin >= end) {
return
}
let l = begin // 左指针
let r = end // 右指针
let temp = retArray[l] // 基准数,这里取数组第一个数
// 左右指针相遇的时候退出扫描循环
while(l < r) {
// 右指针从右向左扫描,碰到第一个小于基准数的时候停住
while(l < r && retArray[r] >= temp) {
r--
}
// 左指针从左向右扫描,碰到第一个大于基准数的时候停住
while(l < r && retArray[l] <= temp) {
l++
}
// 交换左右指针所停位置的数
[retArray[l], retArray[r]] = [retArray[r], retArray[l]]
}
// 最后交换基准数与指针相遇位置的数
[retArray[begin], retArray[l]] = [retArray[l], retArray[begin]]
// 递归处理左右数组
quick(begin, l - 1)
quick(l + 1, end)
}
quick(0, n - 1)
return retArray
}

时间测试

  • 使用含5000个随机整数的数组测试排序效率
let testArr = []
let len = 5000
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')
}

// 插入排序
time = Date.now()
let ans3 = InsertSort(testArr)
if (JSON.stringify(resultArr) === JSON.stringify(ans3)) {
console.log('InsertSort Cost', Date.now() - time, 'ms')
}

// 希尔排序
time = Date.now()
let ans4 = ShellSort(testArr)
if (JSON.stringify(resultArr) === JSON.stringify(ans4)) {
console.log('ShellSort Cost', Date.now() - time, 'ms')
}

// 快速排序
time = Date.now()
let ans5 = QuickSort(testArr)
if (JSON.stringify(resultArr) === JSON.stringify(ans5)) {
console.log('QuickSort Cost', Date.now() - time, 'ms')
}