首先寫一個(gè)測試用的生成隨機(jī)數(shù)的類：

class TestArr {
    constructor(numElems = 10000){
        this.dataStore = [];     //被排序的隨機(jī)數(shù)組
        this.numElems = numElems;   //被排序的數(shù)組長度，默認(rèn)值10000
    }

    //生成一個(gè)隨機(jī)數(shù)組
    setData(){
        for(let i = 0; i < this.numElems; ++i ){
            this.dataStore[i] = Math.floor(Math.random() * (this.numElems + 1));
        }
    }

    //每10個(gè)數(shù)為一組，返回每趟排序的結(jié)果
    toString(){
        var restr = '';
        for(var i = 0; i < this.dataStore.length; ++i){
            restr += this.dataStore[i] + ', ';
            if(i > 0 & i % 10 == 0){
                restr += '\n';
            }
        }
        return restr;
    }

    //交換兩個(gè)元素的內(nèi)容
    swap(arr, index1, index2){
        let temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

下面每一種排序算法使用一個(gè)簡單的類嚼酝，并繼承隨機(jī)數(shù)的類

冒泡排序

冒泡排序

class BubbleSort extends TestArr {
    constructor(numElems){
        super(numElems)
    }

    sort(){
        let data = this.dataStore
        for(let i = this.dataStore.length; i > 1; -- i){
            for(let j = 0; j < i - 1; j ++){
                if(data[j] > data[j + 1]){
                    this.swap(data, j, j + 1)
                }
            }
           // console.log(this.toString())   
        }
    }
}

通過以下方式測試排序結(jié)果 和 排序時(shí)間：

const bSort =new BubbleSort()  //如果不加參數(shù)莺琳，則默認(rèn)數(shù)值是10000
bSort.setData()
console.time('冒泡排序')
bSort.sort()
console.timeEnd('冒泡排序')
console.log(sort.toString())

直接插入排序

插入排序

class InsertionSort extends TestArr {
    constructor(numElems){
        super(numElems);
    }

    sort(){
        let data = this.dataStore
        let temp, j;

        for(let i = 1; i < data.length; i ++ ){
            temp = data[i];
            j = i;
            while (j > 0 && data[j - 1] > temp) {
                this.swap(data, j, j - 1);
                -- j;
            }
            data[j] = temp;

            // console.log(this.toString());
        }
    }
}

可使用類似的方式測試排序時(shí)間和結(jié)果

選擇排序

選擇排序

class SelectionSort extends TestArr{
    constructor(numElems){
        super(numElems);
    }
    sort(){
        let [min, data, temp] = [null, this.dataStore, null]
        for(let i = 0; i < data.length; i ++){
            min = i;
            for(let j = i; j < data.length; j ++){
                if(data[j] < data[min]){
                    min = j;
                }
            }
            this.swap(data, i, min);
            // console.log(this.toString())
        }
    }
}

希爾排序

希爾排序

希爾排序

class ShellSorting extends TestArr{
    constructor(numElems){
        super(numElems);
        this.gaps = [5, 3, 1];
    }

    sort(){
        let data = this.dataStore;
        let gaps = this.gaps;
        let temp;

        for(let g = 0; g < gaps.length; g++ ){
            for(let i = gaps[g]; i < data.length; i ++){
                temp =  data[i];
                let j;
                for(j = i; j >= gaps[g] && data[j - gaps[g]] > temp;  j -= gaps[g]){
                    data[j] = data[j - gaps[g]];
                }
                data[j] = temp;
            }
        }
    }
}

快速排序

快速排序在數(shù)據(jù)很大的時(shí)候嚷缭，優(yōu)勢是很明顯的，在數(shù)據(jù)較小的時(shí)候忆首，效率反而會相對較低

快速排序

class QuikSort extends TestArr {
    constructor(numElems) {
        super(numElems);
    }

    sort(arr){
        if(arr.length == 0) return arr;

        let [temp, less, large] = [arr[0], [], []];
        for(var i = 1; i < arr.length; i ++){
            if(arr[i] < temp){
                less.push(arr[i]);
            }else{
                large.push(arr[i]);
            }
        }
        return this.quikSort(less).concat(temp, this.quikSort(large));
    }
}

通過以下方式測試排序結(jié)果 和 排序時(shí)間：

const qSort =new QuikSort()  //如果不加參數(shù)，則默認(rèn)數(shù)值是10000
qSort.setData()
console.time('快速排序')
console.log(qSort.sort(qSort.dataStore))
console.timeEnd('快速排序')

算法的時(shí)間復(fù)雜度和穩(wěn)定性