javascript實(shí)現(xiàn)排序算法

xiangzhihong 發(fā)布于2019-08-22 10:39 / 2750人閱讀

摘要：高級排序算法有希爾排序歸并排序快速排序。冒泡排序首先聲明，這是最慢的排序算法之一，但是也是最容易實(shí)現(xiàn)的排序算法。穩(wěn)定性冒泡排序?yàn)橐环N穩(wěn)定排序。快速排序快速排序是出力大數(shù)據(jù)集最快的排序算法之一。

簡介

對計(jì)算機(jī)中存儲(chǔ)的數(shù)據(jù)執(zhí)行的兩種最常見的操作是排序和檢索，也是面試經(jīng)常會(huì)被問到的一個(gè)知識(shí)點(diǎn)，本文將整理數(shù)據(jù)排序的基本算法和高級算法。其中基本排序算法有：冒泡排序、選擇排序、插入排序。高級排序算法有：希爾排序、歸并排序、快速排序。
通常排序問題都可以分隔為相同的小規(guī)模問題來解決，即問題的解決都是遞歸的思路。

冒泡排序

首先聲明，這是最慢的排序算法之一，但是也是最容易實(shí)現(xiàn)的排序算法。
算法描述：對于一個(gè)數(shù)列，從第一個(gè)元素開始，依次對相鄰元素進(jìn)行兩兩比較，如果第一個(gè)元素大于第二個(gè)元素就交換他們的位置。
穩(wěn)定性：冒泡排序?yàn)橐环N穩(wěn)定排序。
步驟：
1.從第一個(gè)元素開始，比較相鄰的元素，如果第一個(gè)比第二個(gè)大，就交換他們的位置，一次排序可以將大元素沉底。
2.持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。

function bubble(list){
    for (var i=1; ilist[j+1]){//如果第一個(gè)元素大于第二個(gè)，交換二者的位置
                list[j] = list[j] + list[j+1];
                list[j+1] = list[j] - list[j+1]; //list[j]
                list[j] = list[j] - list[j+1]; //list[j+1]
            }
        }
    }
    return list;
}

選擇排序

算法描述：從數(shù)組的開頭開始，將第一個(gè)元素和其他元素進(jìn)行比較。檢查完所有元素后最小的元素將會(huì)被放到數(shù)組的第一個(gè)位置，然后對第二個(gè)元素執(zhí)行相同的操作，最后直到所有的元素排序完畢。
穩(wěn)定性：選擇排序是一種不穩(wěn)定的排序。

function selection(list){
    for(var i=0; ilist[j]){ //交換二者的位置
                list[i] = list[i]+list[j];
                list[j] = list[i]-list[j];
                list[i] = list[i]-list[j];
            }
        }
    }
    return list;
}

插入排序

算法描述：對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入，直到所有的數(shù)據(jù)排序完畢。
步驟：
1.第一個(gè)元素，認(rèn)為已經(jīng)被排序。
2.下一個(gè)元素，從已排序的的序列中從前向后掃描，一直找到大于或等于它的元素，將此元素插入到那個(gè)元素之前。
3.重復(fù)步驟2.
穩(wěn)定性：插入排序是一個(gè)穩(wěn)定排序。

function insert(list){
    for(var i =1; i=j; k--){//從j到i－1的元素向后移動(dòng)一位
                   list[k] = list[k-1];
               }
               list[j] = a;
           }
       }
    }
    return list;
}

希爾排序

希爾排序是在插入排序的基礎(chǔ)上改進(jìn)的。希爾排序是基于插入排序的以下兩點(diǎn)性質(zhì)而提出改進(jìn)方法的：
1、插入排序在對幾乎已經(jīng)排好序的數(shù)據(jù)操作時(shí)，效率高，即可以達(dá)到線性排序的效率
2、但插入排序一般來說是低效的，因?yàn)椴迦肱判蛎看沃荒軐?shù)據(jù)移動(dòng)一位
步驟：
1.先取一個(gè)小于n的整數(shù)d1作為第一個(gè)增量，把所有距離為d1的元素放在同一個(gè)分組中，先在各組內(nèi)進(jìn)行直接插入排序；
2.然后取第二個(gè)增量d2一般的初次取序列的一半為增量，以后每次減半，直到增量為1。
穩(wěn)定性：希爾排序是不穩(wěn)定排序

歸并排序

實(shí)現(xiàn)原理是把一系列排好序的字序列合并成一個(gè)大的完整有序序列。

快速排序

快速排序是出力大數(shù)據(jù)集最快的排序算法之一。它是一種分而治之的算法，通過遞歸的方式將數(shù)據(jù)一次分解為包含小元素和包含大元素的不同子序列。然后不斷重復(fù)這個(gè)步驟直到所有數(shù)據(jù)都是有序的。快速排序非常適合大型數(shù)據(jù)集合的排序，對于小數(shù)據(jù)集時(shí)性能反而會(huì)有下降。
步驟：
1.選擇一個(gè)基準(zhǔn)元素，將列表分隔成兩個(gè)子序列；
2.對序列重新排序，將所有小于基準(zhǔn)值的元素放在基準(zhǔn)值前面，所有大于基準(zhǔn)值的元素放在基準(zhǔn)值后面；
3.分別對較小元素的子序列和較大元素的子序列重復(fù)步驟1、2。
穩(wěn)定性：快速排序是不穩(wěn)定排序

function quickSort(list){
    if(list.length == 0){
        return [];
    }
    else{
        var lesser = []; //小于基準(zhǔn)值的序列
        var greater = []; //大于基準(zhǔn)值的序列
        var pivot  = list[0];
        for(var i=1; i