几种排序算法的javascript表示

首先写一个测试用的生成随机数的类：

class TestArr {
    constructor(numElems = 10000){
        this.dataStore = [];     //被排序的随机数组
        this.numElems = numElems;   //被排序的数组长度，默认值10000
    }

    //生成一个随机数组
    setData(){
        for(let i = 0; i < this.numElems; ++i ){
            this.dataStore[i] = Math.floor(Math.random() * (this.numElems + 1));
        }
    }

    //每10个数为一组，返回每趟排序的结果
    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;
    }

    //交换两个元素的内容
    swap(arr, index1, index2){
        let temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

下面每一种排序算法使用一个简单的类，并继承随机数的类

冒泡排序

冒泡排序

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())   
        }
    }
}

通过以下方式测试排序结果 和 排序时间：

const bSort =new BubbleSort()  //如果不加参数，则默认数值是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());
        }
    }
}

可使用类似的方式测试排序时间和结果

选择排序

选择排序

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;
            }
        }
    }
}

快速排序

快速排序在数据很大的时候，优势是很明显的，在数据较小的时候，效率反而会相对较低

快速排序

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));
    }
}

通过以下方式测试排序结果 和 排序时间：

const qSort =new QuikSort()  //如果不加参数，则默认数值是10000
qSort.setData()
console.time('快速排序')
console.log(qSort.sort(qSort.dataStore))
console.timeEnd('快速排序')

算法的时间复杂度和稳定性

排序算法	时间复杂度	稳定性
插入排序	O(n*n)	1
希尔排序	O(n*n)	0
冒泡排序	O(n*n)	1
选择排序	O(n*n)	0
快速排序	O(nlogn)	0