javascript - 在原型(prototype)数组上实现快速排序递归函数

Question

Array.prototype.quickSort = function () {
let self = this;
let len = self.length;
let pivot_pos;
let result = []
if (len < 2) {
  return self
}
pivot_pos = self.partition();
let left = self.splice(0, pivot_pos),
right = self.splice(0);


error --> left.quickSort();
error --> right.quickSort();

console.log(left);
console.log(right);
//right_pivot_pos = right.partition();

return this;
}

Array.prototype.partition = function () {
    let arr = this;
    let pivot_pos = Math.floor((arr.length-1)/2);
let last_small = arr[0]
let i;
//console.log(`before this[0] ${this[0]} and before this[pivot_pos] 
${this[pivot_pos]}`);
[arr[pivot_pos], arr[0]] = [arr[0], arr[pivot_pos]];
//console.log(`this[0] ${this[0]} and this[pivot_pos] 
${this[pivot_pos]}`);

 for (i=1;i<arr.length; i++) {
   if(arr[i]<arr[0]) {
     //[this[i], this[num]] = [this[num], this[i]];
     let tmp = arr[last_small];
     arr[last_small] = arr[i];
     arr[i] = tmp;
     last_small++;
     }
   }
 [arr[0], arr[last_small-1]] = [arr[last_small-1], arr[0]];
 return last_small;
}

let sandbox = [1,2,6,5,4,3,7,9];
console.log(sandbox.quickSort());

我不能调用 left.quickSort();和 right.quickSort(); JavaScript 堆内存不足...编写此代码的替代方法是什么？我在 git 上在线浏览了一些，但它不同于计算运行函数的成本。

Answer 1

我在下面列出了您代码的固定版本。最重要的修复包括:

• 在 partition 中，变量 last_small 包含元素的值，但它在稍后的循环中用作索引。
• 在 partition 中，您总是比较索引为 0 的元素，而不是移动的枢轴元素。
• quicksort 函数保持对 2 元素数组的分区和排序。因此内存溢出异常。
• 完成后不会重建原始数组。请注意，拼接修改了原始数组。

Array.prototype.quickSort = function () {
    var self = this;

    if ( self.length < 2 ) {
        return self
    }

    var pivot_pos = self.partition();

    if ( self.length > 2 ) {
        var left = self.splice( 0, pivot_pos );
        var right = self.splice( 0 );

        self.splice.apply( self, [ 0, 0 ].concat( right.quickSort() ) );
        self.splice.apply( self, [ 0, 0 ].concat( left.quickSort() ) );
    }

    return this;
};

Array.prototype.swap = function (i, j) {
    var tmp = this[i];
    this[i] = this[j];
    this[j] = tmp;
};

Array.prototype.partition = function () {
    var self = this;
    var pivot_pos = Math.floor( (self.length - 1) / 2 );
    var last_small_i = 0;

    self.swap( last_small_i, pivot_pos );

    for ( var i = 1; i < self.length; i++ ) {
        if ( self[ i ] < self[ last_small_i ] ) {
            self.swap( last_small_i, i );
            last_small_i++;
            
            if(i != last_small_i) {
                self.swap( last_small_i, i );
            }
        }
    }

    return last_small_i;
};

var sandbox = [ 1, 10, 6, 5, 4, 3, 7, 9 ];
console.log( sandbox.quickSort() );