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

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

代碼框架：

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

用兩層循環(huán)，第一層用來記錄剩余的還未排序的數(shù)的個數(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;
                }
            }
        }
    };

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

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

代碼實現(xiàn)：

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

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

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

從第二個數(shù)開始（因為第一個數(shù)只有一個，前面沒得比。），與前面的數(shù)挨個比較，直到找到前一個數(shù)比當前值小，后一個數(shù)比當前值大的位置，讓后將當前值置于此處，以此類推。

代碼實現(xiàn)：

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

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

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

代碼實現(xiàn)：

    this.mergeSort=function() {
        array = mergeSortRec(array);
    };
    
    //建堆函數(shù)，將數(shù)組一直拆分成兩部分，直到各部分數(shù)組長度都為1的時候停止，然后進行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ù)組中返回選定的元素,語法 arrayObject.slice(start,end)
            right = array.slice(mid, length);

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

    //將各部分進行歸并
    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;
    };

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

代碼實現(xiàn)：

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

    var partition = function(array, left, right) {    //劃分過程
        
        //主元的選擇方法最好是隨機選擇一個數(shù)組想或是選擇中間項，這里選擇中間項
        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;
    };