這里用JavaScript實(shí)現(xiàn)冒泡排序、選擇排序、插入排序、歸并排序以及快速排序這些常見(jiàn)的排序算法

首先我們給本文約定一個(gè)實(shí)現(xiàn)的框架：定義一個(gè)ArrayList類里面包含排序數(shù)組聲明、數(shù)組元素添加、排序算法實(shí)現(xiàn)以及數(shù)組輸出的方法。

代碼框架：

    function ArrayList(){
        var array=[];
    
        this.inputArraymember=function(){   //將10個(gè)大小在1~15的隨機(jī)數(shù)添加到數(shù)組中
            var ins=0;
            for(var i=0;i<10;i++){
                ins=Math.floor(Math.random()*15+1);
                array.push(ins);
            }
        };
    
        this.相應(yīng)的排序算法=function(){...算法的具體實(shí)現(xiàn)代碼...};    //代碼塊替換部分
    
        this.toString=function(separator){  //將數(shù)組按指定分隔符生成字符串方便輸出
            return array.join(separator);
        };
    
    }
    
    var a = new ArrayList();
    a.inputArraymember();
    console.log("隨機(jī)生成的原始數(shù)組為："+a.toString("-"));
    a.bubbleSort();
    console.log("排序后數(shù)組為："+a.toString("-"));

用兩層循環(huán)，第一層用來(lái)記錄剩余的還未排序的數(shù)的個(gè)數(shù)，第二層用來(lái)在剩下的未排序的數(shù)中找到最大的數(shù)并將其放到未排序數(shù)的最后面（冒泡）。

代碼實(shí)現(xiàn)：

    this.bubbleSort=function(){ 
        var length=array.length;
        for(var i=0;iarray[j+1]){
                    var t=array[j];    array[j]=array[j+1];array[j+1]=t;
                }
            }
        }
    };

冒泡排序的時(shí)間復(fù)雜度是O(n2)。將以上代碼替換文章開(kāi)始約定的代碼框架中的“代碼塊替換部分”即可用于在調(diào)試工具中運(yùn)行查看代碼運(yùn)行結(jié)果。

思路很簡(jiǎn)單，每次都找出未排序的數(shù)當(dāng)中最小的數(shù)并放在開(kāi)頭，直到所有數(shù)的位置確定下來(lái)。說(shuō)清楚點(diǎn)就是從所有序列中先找到最小的，然后放到第一個(gè)位置。之后再看剩余元素中最小的，放到第二個(gè)位置……以此類推。

代碼實(shí)現(xiàn)：

    this.selectsort=function(){
        var length=array.length,currentMin;
        for(var i=0;iarray[j]){
                   currentMin=j;    
               }
            }

            if(i!==currentMin){    //若下標(biāo)不是未排序的最開(kāi)始的那個(gè)元素的下標(biāo)，則將兩者的值交換
                var t=array[currentMin];
                array[currentMin]=array[i];
                array[i]=t;
            }
       }
    };

可看出，選擇排序也用了兩個(gè)嵌套著的循環(huán)，所以時(shí)間復(fù)雜度也是O(n2)，是一種原址排序。

從第二個(gè)數(shù)開(kāi)始（因?yàn)榈谝粋€(gè)數(shù)只有一個(gè)，前面沒(méi)得比。），與前面的數(shù)挨個(gè)比較，直到找到前一個(gè)數(shù)比當(dāng)前值小，后一個(gè)數(shù)比當(dāng)前值大的位置，讓后將當(dāng)前值置于此處，以此類推。

代碼實(shí)現(xiàn)：

    this.insertsort=function(){
        var length=array.length, j,temp;

        for(var i=1;i0&&array[j-1]>temp){    //如果這個(gè)數(shù)比上一個(gè)數(shù)小，則讓上一個(gè)數(shù)占據(jù)現(xiàn)在這個(gè)數(shù)的位置（右移每個(gè)比當(dāng)前數(shù)小的數(shù)）
                array[j]=array[j-1];
                j--
            }
            array[j]=temp;    //直到這個(gè)數(shù)不比上一個(gè)數(shù)小的時(shí)候，將這個(gè)數(shù)放在當(dāng)前的位置
        }
    };

時(shí)間復(fù)雜度為O(nlogn)。歸并用的是分治的思想，將原始數(shù)組切分成較小的數(shù)組，直到每個(gè)小數(shù)組只有一個(gè)位置，接著講小數(shù)組歸并成較大的數(shù)組，直到最后只有一個(gè)排序完畢的大數(shù)組。

代碼實(shí)現(xiàn)：

    this.mergeSort=function() {
        array = mergeSortRec(array);
    };
    
    //建堆函數(shù)，將數(shù)組一直拆分成兩部分，直到各部分?jǐn)?shù)組長(zhǎng)度都為1的時(shí)候停止，然后進(jìn)行merge操作
    var mergeSortRec = function(array){
        var length = array.length;
        if (length === 1) {
            return array;
        }
        var mid = Math.floor(length / 2),
            left = array.slice(0, mid),//slice() 方法可從已有的數(shù)組中返回選定的元素,語(yǔ)法 arrayObject.slice(start,end)
            right = array.slice(mid, length);

        return merge(mergeSortRec(left), mergeSortRec(right));
    };

    //將各部分進(jìn)行歸并
    var merge = function(left, right) {
        var result = [],
            il = 0,
            ir = 0;
        while(il < left.length && ir < right.length) {
            if (left[il] < right[ir]) {
                result.push(left[il++]);
            } else {
                result.push(right[ir++]);
            }
        }

        //如果il數(shù)組還有剩余，則將其剩余部分添加到結(jié)果數(shù)組中
        while (il < left.length) {
            result.push(left[il++]);
        }

        //如果ir數(shù)組還有剩余，則將其剩余部分添加到結(jié)果數(shù)組中
        while (ir < right.length) {
            result.push(right[ir++]);
        }

        return result;
    };

時(shí)間復(fù)雜度為O(logn)。用的是分治的思想。

代碼實(shí)現(xiàn)：

    this.quickSort = function(){
        quick(array,  0, array.length - 1);
    };

    var partition = function(array, left, right) {    //劃分過(guò)程
        
        //主元的選擇方法最好是隨機(jī)選擇一個(gè)數(shù)組想或是選擇中間項(xiàng)，這里選擇中間項(xiàng)
        var pivot = array[Math.floor((right + left) / 2)],
            i = left,
            j = right;

        console.log("pivot is " + pivot + "; left is " + left + "; right is " + right);

        while (i <= j) {
            while (array[i] < pivot) {
                i++;
                console.log("i = " + i);
            }

            while (array[j] > pivot) {
                j--;
                console.log("j = " + j);
            }

            if (i <= j) {
                console.log("swap " + array[i] + " with " + array[j]);
                swapQuickStort(array, i, j);
                i++;
                j--;
            }
        }

        return i;
    };

    var swapQuickStort = function(array, index1, index2){
        var aux = array[index1];
        array[index1] = array[index2];
        array[index2] = aux;
    };

    var quick = function(array, left, right){//將子數(shù)組分離為較小值數(shù)組和較大值數(shù)組

        var index;

        if (array.length > 1) {

            index = partition(array, left, right);

            if (left < index - 1) {
                quick(array, left, index - 1);
            }

            if (index < right) {
                quick(array, index, right);
            }
        }
        return array;
    };