常见排序

近来要校招了，基本的排序还是需要掌握的。数据结构，算法永远都是写出好程序的基本功。

冒泡排序

function bubleSort(arr){
    for(let j = arr.length;j>0;j--){
        for(let i = 0;i<j;i++){
            if(arr[i]>arr[i+1]){
                let temp = arr[i]
                arr[i] = arr[i+1]
                arr[i+1] = temp
            }
        }
    }
    return arr
}

选择排序

function selectSort(arr){
    for(let i=0;i<arr.length;i++){
        let min = arr[i]
        let minIndex = i
        for(let j=i;j<arr.length;j++){
            if(arr[j]<min){
                min = arr[j]
                minIndex = j
            }
        }
        let temp = arr[i]
        arr[i] = min
        arr[minIndex] = temp
    }
    return arr
}

插入排序

function insertSort(arr){
    let min = arr[0]
    for(let i=0; i<arr.length;i++){
        for(let j=i;j>0;j--){
            if(arr[j]<arr[j-1]){
                let temp = arr[j]
                arr[j] = arr[j-1]
                arr[j-1] = temp
            }
        }
    }
    return arr
}

希尔排序

function shellSort(a){
    let length = a.length
    let gap = Math.floor(length/2)
    while(gap>0){
        for(let i=gap;i<length;i++){
            for(let j=i;j>0;j-=gap){
                if(a[j-gap]>a[j]){
                    let temp = a[j-gap]
                    a[j-gap] = a[j]
                    a[j] = temp
                }
            }
        }
        gap = Math.floor(gap/2)
    }
    return a
}

分治思想的典型，快排和归并

快排

function quickSort(array){

    sort(array,0,array.length - 1)

    function sort(array,left,right){
        if(left>right){
            return
        }else{
            let partIndex = part(array,left,right)
            sort(array,left,partIndex - 1)
            sort(array,partIndex + 1,right)
        }
    }

    function part(array,left,right){
        let partValue = array[right]
        let storeIndex = 0
        for(let i=0;i<array.length;i++){
            if(array[i]<partValue){
                swap(array,i,storeIndex)
                storeIndex++
            }
        }
        swap(array,right,storeIndex)
        return storeIndex
    }

    function swap(array,i,j){
        let temp = array[i]
        array[i] = array[j]
        array[j] = temp
    }
}

归并

function mergeSort(arr){

    function sort(arr,left,right){
        left = (left === undefined)?0:left
        right = (right === undefined)?arr.length-1:right
        if(left - right >= 0){
            return 
        }
        let middle = Math.floor((left + right)/2)

        sort(arr,left,middle)
        sort(arr,middle+1,right)


        while(left <= middle && middle + 1 <= right){
            if(arr[left] >= arr[middle + 1]){
                let temp = arr[middle + 1]
                for(let i = middle; i >= left; i--){
                    arr[i+1] = arr[i]
                }
                arr[left] = temp
                middle++
            }else{
                left++
            }
        }
        return arr
    }
    return arr
}

Ref

1. http://bubkoo.com/tags/algorithm/ 详细学习了这位作者的文章