Как переопределить метод сортировки массива JavaScript?

Question

ЭТОТ ВОПРОС ОСТАЛОСЬ НЕ ИСПРАВЛЕНО ОТВЕТА НА ПОНЕДЕЛЬНИК 31 октября (Люди ошибочно отвечают на него, как будто я прошу изменить массив. Сортировать, но я не спрашиваючто)

Как переопределить встроенный метод сортировки JavaScript для одного массива (не Array.sort) с помощью radix-msd algorthim?

У меня есть алгоритм для сортировки radix msd, он

// radix most-significant-bit sort for integers
//arr: array to be sorted
//begin: 0
//end: length of array
//bit: maximum number of bits required to represent numbers in arr
function radixsort (arr, begin, end, bit) {
    var i, j, mask;
    i = begin;
    j = end;
    mask = 1 << bit;
    while(i < j) {
        while(i < j && !(arr[i] & mask)) {
            ++i;
        }
        while(i < j && (arr[j - 1] & mask)) {
            --j;
        }
        if(i < j) {
            j--;
            var tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
        }
    }
    if(bit && i > begin) {
        radixsort(arr, begin, i, bit - 1);   //    <=== RECURSIVE FUNCTION
    }
    if(bit && i < end) {
        radixsort(arr, i, end, bit - 1);     //    <=== RECURSIVE FUNCTION
    }
}

И мой массив объектов JavaScript:

homes[0].price;
homes[0].address;
homes[0].city;
homes[0].state;
homes[0].zip;

Так что, когда я вызываю "homes.sort()" - я хочуэто отсортировать весь массив homes[x] на основе price, используя мой массив radix sort сверху. Как мне это сделать?

Answer 1

Вам не нужно переопределять функцию sort , вам просто нужно передать функцию сравнения в метод sort в качестве параметра.

Сигнатура функции дляпараметр function (a, b), где a - это сравниваемый элемент с b.

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

Array.prototype.radixsort = function ( ...params... )

, что позволит вам вызывать

[1,2,3].radixsort(...params...);

В качестве альтернативы, вы можете добавить служебную функцию к Array:

Array.radixsort = function ( ...params... )

Который будет называться:

Array.radixsort([1,2,3], ...params...);

Answer 2

Я думаю, что модификация Array.prototype.sort очень опасна (потому что будут затронуты все другие коды, возможно использующие sort ()).Вот код, хотя:

//Just use this function like radixsort(homes,0,homes.length,32)
function radixsort (arr, begin, end, bit) {
    var i, j, mask;
    i = begin;
    j = end;
    mask = 1 << bit;
    while(i < j) {
        while(i < j && !(arr[i].price & mask)) {
            ++i;
        }
        while(i < j && (arr[j - 1].price & mask)) {
            --j;
        }
        if(i < j) {
            j--;
            var tmp = arr[i].price;
            arr[i].price = arr[j].price;
            arr[j].price = tmp;
            i++;
        }
    }
    if(bit && i > begin) {
        radixsort(arr, begin, i, bit - 1);
    }
    if(bit && i < end) {
        radixsort(arr, i, end, bit - 1);
    }
}
//If you really want to modify default sort function:
Array.prototype.sort = function(){
    radixsort(this,0,this.length,32); //Use 'this' to access (get reference) to the array.
}

Answer 3

Продолжая обсуждение Рэя Тула и zzzzBov:

  function defaultCompare(a, b) {
      var a_str = str(a);
      var b_str = str(b);
      if (a_str < b_str) {
          return -1;
      } else if (a_str > b_str) {
          return 1;
      } else {
          return 0;
      }
   }

   homes.sort = function (compare_func) {
       compare_func = compare_func || defaultCompare;
       RadixSort(this, 0, this.length, 64);
   }

Возможно, в приведенном выше описании есть опечатки, но это должно стать шагом к более полной реализации.

Answer 4

Ваш вопрос задает две вещи:

1. Как один вызов sort для массива, но вызов функции, отличной от Array.sort?
2. Как заставить алгоритм сортировки использовать конкретное поле без его жесткого кодирования?

Ответ на первый вопрос заключается в том, чтобы прикрепить метод sort к самому объекту homes:

homes.sort = function () {radixSort(homes, 0, homes.length, bit);}

Как указали один из комментаторов и другие авторы, это может быть очень запутанным. С одной стороны, Arrays.sort принимает второй параметр, который является функцией сравнения. Radix sort - это сортировка на основе распределения, а не сортировка на основе сравнения, поэтому «переопределение» sort таким образом не имеет особого смысла. Вы бы проигнорировали функцию сравнения, если бы кто-то ее передал.

Но есть и другая проблема. Ваш radixSort как написано не работает, потому что он не сравнивает цены. Один из ответов жестко определяет цену, но вы сказали, что вам не нравится эта ситуация. Вы можете исправить это следующим образом: добавьте пятый параметр, который является именем поля. Если значение не определено, используйте сам элемент массива, в противном случае выберите поле. Примерно так (не проверено):

function radixsort (arr, begin, end, bit, field) {
    var i = begin, j = end , mask = 1 << bit;
    // Use the value of the field at i if present, otherwise the whole element
    var at = function (i) {return field in arr ? arr[i][field] : arr[i]};
    while (i < j) {
        while (i < j && !(arr.at(i) & mask)) {
            ++i;
        }
        while (i < j && (arr.at(j-1) & mask)) {
            --j;
        }
        if (i < j) {
            j--;
            var tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
        }
    }
    if (bit && i > begin) {
        radixsort(arr, begin, i, bit - 1);
    }
    if (bit && i < end) {
        radixsort(arr, i, end, bit - 1);
    }
}

Теперь вы можете сказать:

homes.sort = function () {radixSort(homes, 0, homes.length, 64, 'price');}

Однако учтите следующее предостережение:

CAVEAT : Если price является значением с плавающей запятой, сортировка по основанию, вероятно, не будет работать. Лучше всего просто использовать Array.prototype.sort и передать компаратор для сортировки по различным полям.