如何使用原型编写快速排序函数

Question

我在 quickSort 函数中收到以下错误消息：

TypeError: array is undefined

如何使用下面定义的原型 ArrayList 编写 quickSort 函数？

function ArrayList() {
  this.items = [];
}
ArrayList.prototype.insert = function(item) {
  this.items.push(item);
}
ArrayList.prototype.toString = function() {
  return this.items.join();
}

//This is a function to create a non sorted array using the array function above

function createNonSortedRandomArray(size) {
  var elements = size;
  var array = new ArrayList();
  for (var i = elements; i > 0; i--) {
    array.insert(i);
  }
  return array;
}

swap = function(array, index1, index2) {
    var aux = array[index1];
    array[index1] = array[index2];
    array[index2] = aux;
}

// quickSort function begins here 

ArrayList.prototype.quickSort = function() {
  quick(this.array, 0, this.array.length - 1);
}

quick = function(array, left, right) {
  var index;

  if (array.length > 1) {
    index = partition(array, left, right);
    if (left < index - 1) {
      quick(array, left, index - 1);
    }
    if (index < right) {
      quick(array, index, right);
    }
  }
};

partition = function(array, left, right) {
  var pivot = array[Math.floor((right + left) / 2)],
    i = left,
    j = right;

  while (i <= j) {
    while (array[i] < pivot) {
      i++;
    }
    while (array[j] > pivot) {
      j--;
    }
    if (i <= j) {
      swap(array, i, j);
      i++;
      j--;
    }
  }
  return i;
};

// Execute code block here

var array2 = new createNonSortedRandomArray(33);
console.log(array2.toString());
array2.quickSort();
console.log(array2.toString());

Answer 1

我在 JS 中实现各种算法或数据结构的一个重要灵感来源是 trekhleb's javascript-algorithms 存储库。

见Quicksort。

Answer 2

问题出在访问 this.array 的 quickSort 方法中，但 ArrayList 实例没有具有该名称的属性。查看构造函数（在顶部），属性是 items。所以把方法改成：

ArrayList.prototype.quickSort = function() {
    quick(this.items, 0, this.items.length - 1);
//             ^^^^^          ^^^^^
}

这将解决问题。

注意：总是用var、let或const声明变量。对于用函数表达式定义的几个函数，您没有这样做：swap、quick 和 partition。在严格模式下，如果没有该关键字，它甚至不会解析。

如何使用原型编写快速排序函数

How to write a quickSort function using prototypes

javascript

algorithm

structure