[数据结构与算法]排序算法JavaScript

    // 交换数组中元素
    // 方法一
    Array.prototype.swap=function(originIndex,targetIndex){
        let tmp=this[originIndex]
        this[originIndex]=this[targetIndex]
        this[targetIndex]=tmp
        return this
    }
    // 方法二
    function swap(arr,i,j){
        let tmp=arr[i]
        arr[i]=arr[j]
        arr[j]=tmp
        return arr
    }
    // let arr=[1,2,7,8,4,0,5,2]
    // console.log(swap(arr,1,2))

    //直接插入排序
    //空间复杂度：只声明常数个变量，因此O(1)
    //时间复杂度：最好 O(n) 最坏O(n方) 平均 O(n方)
    //算法稳定性：稳定（相同元素相对位置不发生变化）
    // 方法一
    function insertSort(arr){
        for(let i=1;i<arr.length;i++){
            for(let j=i-1;j>=0;j--){
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1)
                }
            }
        }
        console.log(arr)
    }
    // 方法二
    function insertSort(array){
        for(var i=1;i<array.length;i++){
            if(array[i]<array[i-1]){
                var t=array[i]
                for(var j=i-1;j>=0&&t<array[j];j--){
                    array[j+1]=array[j]
                }
                array[j+1]=t
            }
        }
        console.log(array)
    }

    //冒泡排序
    // 空间复杂度：O(1)
    // 时间复杂度：最好O(n) 最坏O(n方) 平均O(n方)
    // 算法稳定性：稳定
    function bubbleSort(arr){
        for(let i=0;i<arr.length-1;i++){
            for(j=i+1;j<arr.length;j++){
                if(arr[i]>arr[j]){
                    swap(arr,i,j)
                }
            }
        }
        console.log(arr)
    }
    bubbleSort([1,2,7,8,4,0,5,2])

    // 希尔排序
    // 空间复杂度：O(1)
    // 时间复杂度:最坏 O(n方) 平均O(n1.3方)
    // 稳定性：不稳定
    function shellSort(arr){
        for(let d=Math.floor(arr.length/2);d>=1;d=Math.floor(d/2)){
            for(let i=d;i<arr.length;i++){
                for(let j=i;j-d>=0;j-=d){
                    if(arr[j]<arr[j-d]){
                        swap(arr,j,j-d)
                    }
                }
            }
        }
        console.log(arr)
    }
    shellSort([1,2,7,8,4,0,5,2])

    // 快速排序
    // 空间复杂度 最好 O(log2n) 最坏 O(n)
    // 时间复杂度 最好O(n(log2n)) 最坏O(n方) 平均O(nlog2n)
    // 稳定性：不稳定
    // 注：对于顺序和逆序的元素不适合快速排序，因为会是递归的深度达到最大n,降低效率
    // 优化：枢轴元素的选取可以随机 ，或者可以从头中尾选择一个中间值
    function quickSort(arr){
        let left=[]
        let right=[]
        let tag=arr[0]
        if(arr.length==1||arr.length==0) return arr
        for(let i=1;i<arr.length;i++){
            if(arr[i]<tag){
                left.push(arr[i])
            }else{
                right.push(arr[i])
            }
        }
        return [...quickSort(left),tag,...quickSort(right)]
    }
    console.log(quickSort([1,2,7,8,4,0,5,2]))

    // 选择排序
    // 空间复杂度 O(1)
    // 时间复杂度 O(n方) 
    // 稳定性：不稳定
    function selectSort(arr){
        for(let i=0;i<arr.length-1;i++){
            let min=i
            for(let j=i+1;j<arr.length;j++){
                if(arr[min]>arr[j]) {
                    min=j
                }
            }
            swap(arr,min,i)
        }
        return arr
    }
    console.log(selectSort([1,2,7,8,4,0,5,2]))
    // 归并排序
    // 时间复杂度 O(log2n)
    // 空间复杂度 O(n)
    // 稳定性：稳定
    function mergeSort(arr){
        let len=arr.length
        if(len<=1) return arr
        let mid=Math.floor(len/2)
        let left=arr.slice(0,mid)
        let right=arr.slice(mid)
        return merge(mergeSort(left),mergeSort(right))
        
    }
    function merge(left,right){
        let list=[]
        let i=0,j=0
        while(i<left.length&&j<right.length){
            if(left[i]<=right[j]){
                list.push(left[i])
                i++
            }else{
                list.push(right[j])
                j++
            }
        }
        while(i<left.length){
            list.push(left[i])
            i++
        }
        while(j<right.length){
            list.push(right[j])
            j++
        }

        return list
    }
    console.log(mergeSort([1,2,7,4,5,6]))