Порядок строк для метода очереди приоритетов

Question

У меня возникли проблемы с сортировкой строки в методе приоритетной очереди, который я использую. Вот пример строки ключей, которые я сортировочных:

[ '.0', '.1', '.2', '.4', '.2.1', '.3', '.4.1', '.5', '.5.1.5' ] 

Значения представление иерархии, которые должны быть заказаны от наименьшего к наибольшему. В результате я ожидаю это:

[ '.0', '.1', '.2.1', '.2, '.3', '.4', '.4.1', '.5', '.5.1.5' ] 

метод я использую, чтобы впихнуть в мою очередь работает на O(log n) и выглядит так:

queue.add = function(myval) { 
     // console.log(myval); 
     var i = this.size; 
     this.array[this.size++] = myval; 
     while (i > 0) { 
      var p = (i - 1) >> 1; 
      var ap = this.array[p]; 
      if(!this.compare(myval, ap)) break; 
      this.array[i] = ap; 
      i = p; 
     } 
    }; 

И моя функция сравнения просто:

(a, b) => { 
    return a[0] < b[0]; 
} 

Я рассматривал возможность использования localeCompare, но так как я нахожусь в узле, по какой-то причине он не выглядит надежно. Когда я использую:

(a, b) => { 
    return a[0].localeCompare(b[0]) > 0; 
} 

Я получаю compareLocal неопределенной ошибки, которая может быть связана с чем-то другим.

Мой вопрос, следовательно, как я могу эффективно определить порядок строк в том порядке, который я изложил?

Answer 1

Хотя мой результат выглядит следующим образом:

[".0", ".1", ".2", ".2.1", ".3", ".4", ".4.1", ".5", ".5.1.5"] 

Я надеюсь, что это помогает, я использовал вставки-то отсортировать эти значения:

var arr = [ '.0', '.1', '.2', '.4', '.2.1', '.3', '.4.1', '.5', '.5.1.5' ]; 

// transform these values into '.21' or '.515' so that they can be sorted better 
var transormedArray = arr.map(function(ele){ 
    return '.'+ele.replace(/[.]/g,''); 
}); 

// insertion sort max-iterations n^2, min-iterations n(if already ordered) 
for(var i=1; i< transormedArray.length; i++){ 
    for(var r=i; r>=0 && transormedArray[r-1]>transormedArray[r]; r--){ 
     var tmp = transormedArray[r]; 
     transormedArray[r] = transormedArray[r-1]; 
     transormedArray[r-1] = tmp; 
    } 
} 

// retransform them back into '.2.1' or '.5.1.5' 
var result = transormedArray.map(function(ele){ 
    var str = ele.toString()[0]; 
    for(var i=1; i< ele.toString().length; i++){ 
    str += ele.toString()[i]+'.'; 
    } 
    return str.slice(0,str.length-1); 
}); 

console.log(result); // [".0", ".1", ".2", ".2.1", ".3", ".4", ".4.1", ".5", ".5.1.5"] 

Answer 2

можно разделить строки и сравнения деталей.

function customSort(data, order) { 
 

 
    function isNumber(v) { 
 
     return (+v).toString() === v; 
 
    } 
 

 
    var sort = { 
 
      asc: function (a, b) { 
 
       var i = 0, 
 
        l = Math.min(a.value.length, b.value.length); 
 

 
       while (i < l && a.value[i] === b.value[i]) { 
 
        i++; 
 
       } 
 
       if (i === l) { 
 
        return a.value.length - b.value.length; 
 
       } 
 
       if (isNumber(a.value[i]) && isNumber(b.value[i])) { 
 
        return a.value[i] - b.value[i]; 
 
       } 
 
       return a.value[i].localeCompare(b.value[i]); 
 
      }, 
 
      desc: function (a, b) { 
 
       return sort.asc(b, a); 
 
      } 
 
     }, 
 
     mapped = data.map(function (el, i) { 
 
      return { index: i, value: el.split('.') }; 
 
     }); 
 

 
    mapped.sort(sort[order] || sort.asc); 
 
    return mapped.map(function (el) { 
 
     return data[el.index]; 
 
    }); 
 
} 
 

 
var array = ['.0', '.1', '.2', '.4', '.2.1', '.3', '.4.1', '.5', '.5.1.5']; 
 

 

 
console.log('sorted array asc', customSort(array)); 
 
console.log('sorted array desc ', customSort(array, 'desc')); 
 
console.log('original array ', array);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

Вы можете создать метод компаратора пользовательских сортировок, который расщепляет значения точки и сравнивает их длину; вместе с их целыми значениями.

Это самый простой и удобный метод.

var compareVersions = (a, b) => { 
 
    if (a === b) return 0; 
 
    var aArr = a.split("."), bArr = b.split("."); 
 
    for (var i = 0; i < Math.min(aArr.length, bArr.length); i++) { 
 
     if (parseInt(aArr[i]) < parseInt(bArr[i])) return -1; 
 
     if (parseInt(aArr[i]) > parseInt(bArr[i])) return 1; 
 
    } 
 
    if (aArr.length < bArr.length) return -1; 
 
    if (aArr.length > bArr.length) return 1; 
 
    return 0; 
 
}; 
 
var compareVersionsDesc = (a, b) => compareVersions(b, a); 
 

 
// Example 
 
let versionArr = ['.0', '.1', '.2', '.4', '.2.1', '.3', '.4.1', '.5', '.5.1.5']; 
 

 
console.log('Original Array: ', JSON.stringify(versionArr)); 
 
console.log('Sort Ascending:', JSON.stringify(versionArr.sort(compareVersions))); 
 
console.log('Sort Descending:', JSON.stringify(versionArr.sort(compareVersionsDesc)));

.as-console-wrapper { max-height: 100% !important; top: 0; }