排序算法——javascript

cucumber 發(fā)布于2019-08-20 11:07 / 2178人閱讀

摘要：筆試面試如果涉及到數(shù)據(jù)結(jié)構(gòu)和算法之類的題，貌似都比較喜歡問(wèn)二叉樹，排序算法等，所以整理一下用寫的排序算法排序算法幾個(gè)關(guān)鍵點(diǎn)就是時(shí)間復(fù)雜度空間復(fù)雜度穩(wěn)定性，前兩者對(duì)于數(shù)學(xué)渣渣的我來(lái)說(shuō)只能盡可能記下來(lái)了，判定穩(wěn)定性主要是看兩個(gè)相同的元素在排序后

筆試面試如果涉及到數(shù)據(jù)結(jié)構(gòu)和算法之類的題，貌似都比較喜歡問(wèn)二叉樹，排序算法等，所以整理一下用js寫的排序算法

排序算法幾個(gè)關(guān)鍵點(diǎn)就是時(shí)間復(fù)雜度、空間復(fù)雜度、穩(wěn)定性，前兩者對(duì)于數(shù)學(xué)渣渣的我來(lái)說(shuō)只能盡可能記下來(lái)了，判定穩(wěn)定性主要是看兩個(gè)相同的元素在排序后和排序前的順序是否改變，如果改變了就是不穩(wěn)定

冒泡排序

比較相鄰的元素，如果第一個(gè)數(shù)比第二個(gè)數(shù)大，就交換他們兩個(gè)，從開始第一對(duì)到結(jié)尾的最后一對(duì)，這樣每一輪比較結(jié)束都將會(huì)把最大的數(shù)排在最后，再重復(fù)從第一對(duì)開始比較，直到某一輪比較結(jié)束后沒(méi)有進(jìn)行交換，則排序結(jié)束

時(shí)間復(fù)雜度：O(n^n)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定

JavaScript語(yǔ)言實(shí)現(xiàn)

    function bubbleSort(arr){
        var len = arr.length,k=0;
        for(var i=0;;i++){
            k=0;
            for(var j=0;j arr[j+1]){
                    var temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    k=1;                    
                }
            }
            if(k == 0) break;
        }
        console.log(arr);
    }

選擇排序

從一組數(shù)中選出最小的與第一個(gè)數(shù)據(jù)交換，再?gòu)氖Ｓ鄶?shù)據(jù)中繼續(xù)選出最小的與第二個(gè)數(shù)據(jù)交換

時(shí)間復(fù)雜度：O(n^n)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定

JavaScript語(yǔ)言實(shí)現(xiàn)

    function selectSort(arr){
        var len = arr.length;
        for(var i=0;i
插入排序
將數(shù)據(jù)分為有序和無(wú)序，初始有序數(shù)據(jù)為第一個(gè)數(shù)，無(wú)序數(shù)據(jù)為剩余的，將無(wú)序數(shù)據(jù)循環(huán)插入到有序數(shù)據(jù)中
時(shí)間復(fù)雜度：O(n^n)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定
JavaScript語(yǔ)言實(shí)現(xiàn)
    function insertSort(arr){
        var len = arr.length;
        for(var i=1;i=0 && arr[j]>temp){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = temp;
        }
        console.log(arr);
    }
快速排序
先選取數(shù)組中一個(gè)數(shù)作為基數(shù)，將其他數(shù)據(jù)與該基數(shù)比較，如果大于基數(shù)就排在基數(shù)的右側(cè)，如果小于就排在基數(shù)的左側(cè)，再分別對(duì)小于基數(shù)和大于基數(shù)的數(shù)組做快速排序
時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(1ogn)
穩(wěn)定性：不穩(wěn)定
JavaScript語(yǔ)言實(shí)現(xiàn)
    function quickSort(arr,start,end){

        if(start < end){
            var base = arr[start];
            var temp;
            var i=start,j=end;
            do{
                while(arr[i] < base && i < end){
                    i++;
                }
                while(arr[j] > base && j > start){
                    j--;
                } 
                if(i <= j){
                    temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                    i++;
                    j--;
                }
            }while(i <= j);
            if(start < j){
                sort4(arr,start,j);
            }
            if(end > i){
                sort4(arr,i,end);
            }
        }
        console.log(arr);
    }
歸并排序
先將所有數(shù)據(jù)兩兩分組進(jìn)行排序，再兩兩歸并，重復(fù)進(jìn)行直到所有數(shù)據(jù)歸并成一個(gè)有序表
時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(1)
穩(wěn)定性：穩(wěn)定
JavaScript語(yǔ)言實(shí)現(xiàn)
    function mergeSort(arr){
        function sort(array,first,last){
            first = (first === undefined) ? 0 : first;
            last = (last === undefined) ? array.length-1 : last;
            if(last - first <１){return;}
            sort(arr,first,middle);
            sort(arr,middle+1,last);

            var f=first,
                m=middle,
                i,
                temp;
            while(f <= m && m + 1 <= last){
                if(arr[f] >= arr[m+1]){
                    temp = arr[m+1];
                    for(i=m;i>=f;i--){
                        arr[i+1]=arr[i];
                    }
                    arr[f] = temp;
                    m++;
                }else {
                    f++;
                }
            }
            return arr;
        }
        return sort(arr);
    }
堆排序
將數(shù)據(jù)表示成完全二叉樹的形式，并且以最大堆的方式排序，再一次交換最后一個(gè)最后一個(gè)元素和根元素，并且每一次都重新進(jìn)行最大堆排序
時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定
JavaScript語(yǔ)言實(shí)現(xiàn)
    function heapSort(array){
        function swap(array,i,j){
            var temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
        /*最大堆調(diào)整*/
        function maxHeapify(array,index,heapSize){
            var iMax,
                iLeft,
                iRight;
            while(true){
                iMax = index;
                iLeft = 2 * index + 1;
                iRight = 2 * (index + 1);

                if(iLeft < heapSize && array[index] < array[iLeft]){
                    iMax = iLeft;
                }
                if(iRight < heapSize && array[iMax] < array[iRight]){
                    iMax = iRight;
                }
                if(iMax != index){
                    swap(array,iMax,index);
                    index = iMax;
                }else{break;}
            }
        }
        /*創(chuàng)建最大堆*/
        function buildMaxHeap(array){
            var i,
                iParent = Math.floor(array.length/2) - 1;

            for(i = iParent; i >= 0; i--){
                maxHeapify(array,i,array.length);
            }
        }
        /*堆排序*/
        function sort(array){
            buildMaxHeap(array);

            for(var i = array.length - 1;i > 0; i--){
                swap(array, 0, i);
                maxHeapify(array, 0, i);
            }
            return array;
        }
        return sort(array);
希爾排序
每次對(duì)相隔一定間隔的數(shù)進(jìn)行插入排序
時(shí)間復(fù)雜度：O(nlogn)
空間復(fù)雜度：O(1)
穩(wěn)定性：不穩(wěn)定
JavaScript語(yǔ)言實(shí)現(xiàn)
    function shellSort(array){

        function swap(array, i, k){
            var temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

        var length = array.length,
            gap = Math.floor(length / 2);

        while(gap > 0){
            for(var i = gap; i < length; i++){
                for(var j = i; j > 0; j -= gap){
                    if(array[j - gap] > array[j]){
                        swap(array, j - gap, j);
                    }else {
                        break;
                    }
                }
            }

            gap = Math.floor(gap/2);
        }

        return array;
    }