小撒是一只好學(xué)的小鴨子耐量,這天,小撒在學(xué)習(xí)算法
插入排序
插入排序(Insertion Sort)的時(shí)間復(fù)雜度是O(n ^ 2)
滤港,其過程是不斷將新元素插入到已排序部分中的正確位置:
插入排序示意圖
在每一次插入過程中廊蜒,需要自右向左將已排序的元素與當(dāng)前插入元素想比較,找到正確的插入位置:
單次插入示意圖
代碼示例(js)
const sort = (arr) => {
for(let i = 1; i < arr.length; i++){
const temp = arr[i]
let j = i-1
while(j >= 0 && temp < arr[j] ){
arr[j+1] = arr[j]
j--
}
arr[j+1] = temp
}
return arr
}
冒泡排序
冒泡排序(Bubble Sort)與插入排序非常類似溅漾,其時(shí)間復(fù)雜度也是O(n ^ 2)
山叮,算法過程如其名稱,最小的元素逐一上浮
至數(shù)組前部:
冒泡排序示意圖
代碼示例
const sort = (arr) => {
for(let i = 0; i < arr.length - 1; i++){
for (let j = arr.length - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
swap(arr, j, j-1)
}
}
}
return arr
}
選擇排序
選擇排序(Selection sort)的時(shí)間復(fù)雜度同樣是O(n ^ 2)
樟凄,其過程為聘芜,不斷選擇剩余元素中最小的元素,并置于剩余元素的最左(緊挨已排序元素的右側(cè)):
選擇排序圖示
代碼示例
const sort = (arr) => {
for (let i = 0; i < arr.length - 1; i++) {
let indexMin = i
for (let m = i + 1; m < arr.length; m++) {
if (arr[m] < arr[indexMin]) indexMin = m
}
if (arr[i] > arr[indexMin]) {
swap(arr, i, indexMin)
}
}
return arr
}
小結(jié)
插入排序缝龄、冒泡排序汰现、選擇排序都是非常直觀與樸素的排序算法,空間復(fù)雜度都是O(1)
叔壤,不過時(shí)間復(fù)雜度就不夠理想啦瞎饲!