当前位置：首页 > article >正文

数据结构与算法之排序: 侏儒排序 (Typescript版)

article 2025/3/3 10:36:36

排序

排序：把某个乱序的数组变成升序或降序的数组 (这里用数组来做举例)

侏儒排序

该排序属于贪心策略
关注的是局部，是一种苟且的东西

算法实现

1 ）普通版

// version 1
Array.prototype.gnomeSort = function() {
    let len = this.length;
    for(let i=1; i<len;) {
        // 短路保护 贪心比较当前两个
        if(i < 1 || this[i-1] <= this[i]) {
            ++i; // 正确，则递增，这里有个性能的问题，当一轮比较结束，还需要自增移动到之前已经比较好的位置，重复性太大
        } else {
            // 逆序，则交换
            [this[i-1], this[i]] = [this[i], this[i-1]]
            --i; // i回退进行比较，直到当前所有都有序
        }
    }
}

let arr = [5,4,3,2,1]
arr.gnomeSort()
console.log(arr); // [1, 2, 3, 4, 5]

2 ）优化版

// version 2 改进了不需要重复比较已经有序的元素了, 也就是说不需要自己再往回走了
Array.prototype.gnomeSort = function() {
    let len = this.length;
    // k是当前比较的位置, 从1 ~ len-1
    for(let k=1; k<len; ++k) {
        // 通过i进行内部比较排序, 逆序，则交换
        for(let i=k; i>0 && this[i-1] > this[i]; --i) {
            [this[i-1], this[i]] = [this[i], this[i-1]]
        }
    }
}

let arr = [5,4,3,2,1]
arr.gnomeSort()
console.log(arr); // [1, 2, 3, 4, 5]