主页 / 问题 / 1597092
Accepted
u111
Asked:2024-10-18 16:26:43 +0000 UTC2024-10-18 16:26:43 +0000 UTC

梳状排序中的错误

  • 772

我读了一篇关于梳排序的文章https://thecode.media/comb-sort/，测试了代码，结果发现当因子值大于1.31时，代码开始工作不正确，尽管文章没有对此有何评论。为什么这种情况会从这个值开始发生，而不是从 1.2 或 1.4 开始发生？

// исходный массив 
var arr = [];
for(let i = 0;i < 1000;i++){
    arr.push(Math.random());
}

// получаем длину массива
const l = arr.length;
// оптимальное число для вычисления шага сравнения
const factor = 1.32;
// получаем точный шаг сравнения
let gapFactor = l / factor;
// пока шаг больше единицы
while (gapFactor > 1) {
    // округляем шаг до целого
    const gap = Math.round(gapFactor);
    // и организуем цикл как в пузырьковой сортировке
    for (let i = 0, j = gap; j < l; i++, j++) {
        // если сначала идёт большое число
        if (arr[i] > arr[j]) {
            // меняем их местами
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
        // выводим текущее состояние массива в консоль 
        // это необязательный шаг, он здесь для наглядности 
        //console.log(arr);
    }
    // в конце цикла рассчитываем новый шаг
    gapFactor = gapFactor / factor;
}

for(let i = 0;i < arr.length - 1;i++){
    if(arr[i + 1] < arr[i]){
        console.log('Массив неправильно отсортирован! ' + i);
    }
}
javascript

1 个回答

  1. Best Answer

    问题在于，一次冒泡排序并不能提供完整的排序。

    有必要以递减的长度进行通过——在第一圈中，保证最大的元素将在末端结束，在第二圈中——第二个将是倒数第二个，依此类推。排序可能会更快，但事实并非如此。当音调发生微小变化时，问题并不明显，但当音调变化较大时，经常会出现“排序不足”的情况。

    最好添加一个排序是否完成的检查 - 在元素靠近其位置的情况下，这会更快。

    在线查询

    var arr = [];
for(let i = 0;i < 100;i++){
    arr.push(Math.round(Math.random()*1000));
}

const l = arr.length;

const factor = 1.7;

let gap = l;
let swaps = true;

// пока шаг больше единицы и были обмены
while ((gap > 1) || swaps) {
    gap = Math.max(1, Math.round(gap / factor));
    swaps = false;
    for (let i = 0; i+gap < l; i++) {
        if (arr[i] > arr[i+gap]) {
            let t = arr[i+gap];
            arr[i+gap] = arr[i];
            arr[i] = t;
            swaps = true;
        }
       //print(arr);
    }
}

for(let i = 0;i < arr.length - 1;i++){
    if(arr[i + 1] < arr[i]){
        print('Массив неправильно отсортирован! ' + i + ' ' + arr[i] + ' ' +arr[i+1]);
    }
}
    • 1

相关问题