思路:循环数组,比较当前元素和下一个元素,小的那个向上冒泡,下一次循环继续上面的操作,排好序的数(在后面)不参与循环
时间复杂度:O(n2)
function bubbleSort (array) {
let len = array.length
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - i -1; j++) {
if (array[j] > array[j+1]) {
[ array[j], array[j+1] ] = [ array[j+1], array[j] ]
}
}
}
}
思路:循环数组,选取一个最小的数字放到前面的有序序列中,下一次循环继续上面的操作,排好序的数(在前面)不参与循环
时间复杂度:O(n2)
function selectSort (array) {
let len = array.length
for (let i = 0; i < len - 1; i++) {
for (let j = i + 1; j < len; j++) {
if (array[i] > array[j]) {
[ array[i], array[j] ] = [ array[j], array[i] ]
}
}
}
}
思路:将左侧序列看成一个有序序列,每次插入一个数字到该序列,插入时,从有序序列最右侧开始比较,较大的数后移
时间复杂度:O(n2)
function selectSort (array) {
let len = array.length
for (let i = 1; i < len; i++) {
for (let j = i; j >= 0; j--) {
if (array[j] < array[j-1]) {
[ array[j], array[j-1] ] = [ array[j-1], array[j] ]
} else break
}
}
}
思路:选择一个基准元素 target(一般选择第一个数),将比 target 小的元素移动到数组左边,比 target 大的元素移动到数组右边,继续对 target 左侧和右侧的元素进行相同操作
时间复杂度:平均 O(nlogn),最坏 O(n2)
function quickSort (array, start = 0, end = array.length - 1) {
if (start >= end) return
let target = start
let [ left, right ] = [ start, end ]
while (left < right) {
while (arr[right] >= arr[target] && left < right) {
right--
}
while (arr[left] <= arr[target] && left < right) {
left++
}
[ arr[left], arr[right] ] = [ arr[right], arr[left] ]
}
[ arr[target], arr[right] ] = [ arr[right], arr[target] ]
quickSort(array, start, right - 1)
quickSort(array, right + 1, end)
}