关于前端:javascript之排序算法

排序算法

记录一些常见的简略的算法

1. 冒泡排序，最简略的算法，从运行工夫角度看，性能最差一个,比拟相邻项，替换地位O(n2)

 function swap(array, i, j) {
      [array[j], array[i]] = [array[i], array[j]]
 }

 const Compare = {
       LESS_THAN: -1,
       BIGGER_THAN: 1,
       EQUAL_THAN: 0
 }
function defaultCompareFn(a, b) {
       if (a === b) {
            return Compare.EQUAL_THAN;
       }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
function modifiedBuddleSort(array,compareFn = defaultCompareFn){
    const {length} =array;
    for(let i=0;i<length;i++){
        for(let j =0;j<length-1-i;j++){
            if(compareFn(array[j],array[j+1])===Compare.BIGGER_THAN){
                swap(array,j,j+1)
            }
        }
    }
    return array;
}

2.抉择排序,旧址排序，找到最小值放第一位，第二小放第二位，以此类推O(n2)

function selectionSort(array,compareFn = defaultCompareFn){
    const {length} =array;
    let indexMin;
    for(let i=0;i<length-1;i++){
        indexMin =i;
        for(let j=i;j<length;j++){
            if(compareFn(array[indexMin],array[j])===Compare.BIGGER_THAN){
                indexMin = j;
            }
        }
        if(i!==indexMin){
            swap(array,i,indexMin);
        }
    }
    return array;
}

3.插入排序,每次排一个数组项,以此构建最初排序数组，假设第一项曾经排序过，接着和第二项进行比拟-，看第二项是否要插入第一项之前，接着和第三项比拟，看须要查到哪，以此类推/排序小型数组，这个比抉择和冒泡性能好。

function insertionSort(array, compareFn = defaultCompareFn){
    const {length}=array;
    let temp;
    for(let i=1;i<length;i++){
        let j =i;
        temp = array[i];
        while(j>0&&compareFn(array[j-1],temp)=== Compare.BIGGER_THAN){
            array[j] = array[j-1];
            j--;
        }
        array[j] = temp;
    }
    return array;
}

4.计数排序,(整数排序算法),一个数组计算，数字呈现过的次数