关于前端:javascript之排序算法

6次阅读

共计 1217 个字符，预计需要花费 4 分钟才能阅读完成。

冒泡排序，最简略的算法，从运行工夫角度看，性能最差一个, 比拟相邻项，替换地位 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. 计数排序,(整数排序算法), 一个数组计算，数字呈现过的次数

正文完