// 排序算法 [9,2,4,5,3,1]
// 冒泡排序： 第一層for循環(huán)：比較輪數(shù) = length - 1述雾，第二層for循環(huán)比較次數(shù)減少是因為不需要和已經(jīng)確定排序的數(shù)進行比較檐薯，相鄰比較兼都，把最大的往后冒
/*
每一輪經(jīng)過相鄰兩兩比較之后都會確定一個較大的數(shù)字放到數(shù)組后面的位置
第一輪：[........9] 不需要比較 自己 需要比較 5次
第二輪：[.......5,9] 不需要比較 自己 + 9 需要比較 4次
第三輪：[......4,5,9]不需要比較 自己 + 5 + 9 需要比較 3次
第四輪：[..3,4,5,9] 不需要比較 自己 + 4 + 5 + 9 需要比較 2次
第五輪：[1,2,3,4,5,9] 比較剩余的最后兩個數(shù)粪糙，只需要比較 需要比較 1次
算法復(fù)雜度最壞情況 5 + 4 + 3 +2 + 1 = (n-1)+(n-2)+(n-3)+(n-4)+(n-5) = n*(n-1)/2 = O(n^2)
*/
let arr = [9,2,4,5,3,1,3,-1,0]
function bubbbleSort(arr) {
let n = arr.length - 1
// 0,1,2,3,4 五輪
for (let i = 0; i < n; i++) {
// 每一輪不需要比較自己和比較過確定數(shù)量的累計
for(let j = 0; j < arr.length-1-i; j++) {
if(arr[j] > arr[j+1]){
[arr[j],arr[j+1]] = [arr[j+1],arr[j]]
}
}
}
return arr
}
// console.log(bubbbleSort(arr))
// 選擇排序： [9,2,4,5,3,1],第一層for循環(huán)確定比較輪數(shù)异旧，第二層j 從i+1開始尤勋，是因為每次都把最小的放在最前i的位置
/*
每一輪 篩選記錄最小值的下標(biāo)侮措，將和每一輪的輪數(shù)交換位置
第一輪 假設(shè)arr[0] = 9 是最小值，依次和2做盅、4缤削、5、3吹榴、1比較亭敢。每次比較都令arr[0]是最小值，需要比較 5次（不和自己比較）
第二輪 假設(shè)arr[1] = 2 是最小值腊尚，依次和9吨拗、4满哪、5婿斥、3 比較，每次比較都令arr[1]是最小值哨鸭，需要比較 4次（不和自己 + 9比較）
...
第五輪 剩余兩個數(shù) 只需要比較 1次
算法復(fù)雜度最壞情況 5 + 4 + 3 +2 + 1 = (n-1)+(n-2)+(n-3)+(n-4)+(n-5) = n*(n-1)/2 = O(n^2)
*/
function selectionSort(arr) {
for(let i = 0; i < arr.length-1; i++){
// j = i +1 表示每一輪不需要自己和比較過確定數(shù)量的累計
for(let j = i +1; j < arr.length; j++){
if(arr[j] < arr[i]) {
[arr[i],arr[j]] = [arr[j],arr[i]]
}
}
}
return arr
}
// console.log(selectionSort(arr))
// 插入排序：把當(dāng)前的數(shù)插入到之前經(jīng)過交換已排好序的數(shù)組中
// function insertSort(arr) {
// let a = []
// a[0] = arr[0];
// for (let i = 1; i < arr.length; i++) {
// for(let j = a.length - 1; j >= 0; j--){
// if(arr[i] >= a[j]) {
// a.splice(j+1,0,arr[i])
// break
// }
// if(j === 0){
// a.unshift(arr[i])
// }
// }
// }
// return a
// }
// 插入排序優(yōu)化
function insertSort(arr) {
for (let i = 1; i < arr.length; i++) {
// 取出待插入的元素
let insertValue = arr[i];
let j = i - 1;
for (; (j >= 0) && (insertValue < arr[j]); j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = insertValue;
}
return arr
}
// console.log(insertSort(arr))
// 希爾排序 建立在插入排序上民宿，因為前面三個排序性能最好的是插入排序，進行分組的插入排序 nlogn
function shellSort(arr) {
for(let gap = Math.floor(arr.length / 2); gap > 0; gap = Math.floor(gap / 2)){
//將數(shù)組按照一定間隔分組像鸡，將分組好的數(shù)組分別進行插入排序活鹰，直到間隔為1，進行最后一次插入排序
for(let i = 0; i < arr.length - gap; i++){
let insertValue = arr[i+gap]
let j = i
for(;j >= 0 && arr[j] > insertValue;j = j - gap){
arr[j + gap] = arr[j]
}
arr[j + gap] = insertValue
}
}
return arr
}
console.log(shellSort(arr))
// 歸并排序 遞歸+合并 把數(shù)組分成左右兩部分只估，對左邊進行遞歸排序志群，對右邊進行遞歸排序，在合并左右排序
function mergeSort(arr) {
if(arr.length === 1) return arr
let a = []
let n = Math.floor(arr.length / 2)
let left = arr.slice(0,n)
let right = arr.slice(n)
let kl = mergeSort(left)
let kr = mergeSort(right)
let il = 0;
let ir = 0
while (il < kl.length && ir < kr.length) {
if(kl[il] < kr[ir]){
a.push(kl[il])
il++
}else{
a.push(kr[ir])
ir++
}
}
if(il < kl.length){
let b = kl.slice(il)
a = a.concat(b)
}
if(ir < kr.length){
let c = kr.slice(ir)
a = a.concat(c)
}
return a
}
console.log(mergeSort(arr))
// 快速排序 找到一個基準(zhǔn)點蛔钙，保證比基準(zhǔn)點大的都在基準(zhǔn)點右邊锌云，比基準(zhǔn)點小的都在基準(zhǔn)點的左邊，最后形成【左吁脱，基準(zhǔn)點桑涎，右】依次遞歸
function quickSort(arr) {
if(arr.length <= 1) return arr
let n = Math.floor(arr.length / 2)
let pivot = arr.splice(n,1)[0]
const left = []
const right = []
arr.map(item=>{
if(item < pivot){
left.push(item)
}else{
right.push(item)
}
})
return quickSort(left).concat(pivot,quickSort(right))
}
console.log(quickSort(arr))
希爾排序for循環(huán)i < arr.lenght - gap過程
image.png
