js最常用的排序---手撕js系列

冒泡排序

思想：遍曆len-1次,每次找到最大數放到末尾。比較是按照相鄰數組比較
時間複雜度：O(n^2)
空間複雜度：O(1)

function bubblesort(arr)
{
    
    for(let i=0;i<arr.length-1;i++)
    {
    
        for(let j=0;j<arr.length-i-1;j++)
        {
    
            if(arr[j]>arr[j+1])
            {
    
                let temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
    return arr;
}
console.log(bubblesort([10,2,4,5,60,2]))//[ 2, 2, 4, 5, 10, 60 ]

選擇排序

思想：遍曆len-1次,每次找到最小數放到開頭。比較是按照相鄰數組比較
時間複雜度：O(n^2)
空間複雜度：O(1)

function selectsort(arr)
{
    
    let min,temp;
    for(let i=0;i<arr.length-1;i++)
    {
    
    min=i;
    for(let j=i+1;j<arr.length;j++)
    {
    
        if(arr[j]<arr[min])
        {
    
            min=j;
        }
    }
    temp=arr[i];
    arr[i]=arr[min];
    arr[min]=temp;
    }
    return arr;
}
console.log(selectsort([3,2,4,5,8,0,1]))

插入排序

思想：假設前n個數已經排序，取出下一個元素，在以排序的元素中找到合適比特置插入。
時間複雜度：O(n^2)
空間複雜度：O(n)

function insertsort(arr)
{
    
    let len=arr.length;
    for(let i=0;i<len;i++)
    {
    
        let key=arr[i];
        let j=i-1;
        while(j>=0&&arr[j]>key)
        {
    
        arr[j+1]=arr[j];
        j--;
        }
        arr[j+1]=key;        
    }
    return arr;
}
console.log(insertsort([3,2,4,5,8,0]))

快速排序

思想：找到一個基准數，將小於基准數放到left數組，大於基准數放到right數組。然後concat拼接。left,right數組進入quicksort遞歸遍曆，直到找到出口。
時間複雜度：O(nlogn)
空間複雜度：O(n)

function quicksort(arr)
{
    
    if(arr.length<2) return arr;//出口
    let left=[]
    let right=[]
    let mid=arr.splice(Math.floor(arr.length/2),1);
    for(let i=0;i<arr.length;i++)
    {
    
        if(arr[i]<mid)
        {
    
            left.push(arr[i])
        }
        else{
    
            right.push(arr[i])
        }
    }
    return quicksort(left).concat(mid,quicksort(right))
}
console.log(quicksort([3,2,4,5,15,0]))

挑戰連續更文100天-----第一天