quickSort.js

// 2018.5.11更新： 减少了swap
function qSort(compare) {
    var swap = (p1, p2) => {
        var tmp = this[p1];
        this[p1] = this[p2];
        this[p2] = tmp; 
    }
    var sortRange = (start, end) => {
        var midValue = this[start];
        var p1 = start + 1, p2 = end - 1;
        while(p1 < p2) {
            while(compare(this[p1], midValue) <= 0 && p1 < p2) {
                swap(p1, p2--);
            }
            p1 ++;
        }
        var mid = this[p2] <= midValue ? p2 : p2 -1;
        swap(start, mid);
        if(start < mid - 1) 
            sortRange(start, mid);
        if(mid + 1 < end ) 
            sortRange(mid + 1, end);
        
    }
    sortRange(0, this.length);
    return this;
};

qSort.call([6, 1, 2, 7, 9, 3, 4, 5, 10, 8], (a, b) => b - a);

quickSortFP.js

var y = g => 
    (f=>f(f))(
        self => 
            g( (...args)=>self(self).apply(this,args) ) 
    )

var qSort = y(qSort => 
    (array, compare) =>
        array.length <= 1 ? 
            array :
            qSort(array.slice(1).filter(e => compare(e, array[0]) > 0), compare)
                .concat([array[0]])
                .concat(qSort(array.slice(1).filter(e => compare(e, array[0]) <= 0),compare)))
qSort([6, 1, 2, 7, 9, 3, 4, 5, 10, 8], (a, b) => b - a);

好顶赞~

233，说写就写

666

用数组压栈循环替代递归的版本

function qSort(compare) {
    var swap = (p1, p2) => {
        var tmp = this[p1];
        this[p1] = this[p2];
        this[p2] = tmp;
    }

    var sortRange = (start, end) => {
        var ranges = [
            [start, end]
        ];

        while (ranges.length) {
            var range = ranges.pop();
            start = range[0];
            end = range[1];

            var midValue = this[start];
            var p1 = start,
                p2 = end - 1;

            while (p1 < p2) {
                swap(p1, p1 + 1);
                while (compare(this[p1], midValue) <= 0 && p1 < p2) {
                    swap(p1, p2--);
                }
                p1++;
            }

            if (start < p1 - 1)
                ranges.push([start, p1]);
            if (p1 < end - 1)
                ranges.push([p1, end]);
        }

    }

    sortRange(0, this.length);
    return this;
}

console.log(qSort.call([6, 1, 2, 7, 9, 3, 4, 5, 10, 8], (a, b) => b - a));

给大佬们递茶

@xicilion
叔，我测得你这个版本咋比阮一峰版的还慢。。。

@xiaomuzhu 哈哈，演示一下，只是为了消除递归。js 的数组实在太慢。

nice~

winter 老师，我贴过来测试发现 compare 换成 a - b 好像结果不对啊。。。
输出的是这样的。。
[8, 7, 10, 4, 9, 6, 2, 5, 1, 3]

let swapTimes = 0;

function qs<T>(this: T[], compare: (a: T, b: T) => number): T[] {
  const swap = (a: number, b: number) => {
    // console.log(
    //   a,
    //   b,
    //   this.map((v, i) => {
    //     return {
    //       v,
    //       i,
    //       to: i === a ? b : i === b ? a : undefined,
    //     };
    //   }).filter(v => v.to !== undefined),
    // );
    const temp = this[a];
    this[a] = this[b];
    this[b] = temp;
    swapTimes++;
  };
  const sort = (start: number, end: number) => {
    const piv = this[start];
    let p1 = start + 1;
    let p2 = end;
    while (p1 < p2) {
      while (compare(this[p1], piv) > 0 && p1 < p2) {
        // this[p1] < piv;
        p1++;
      }
      // find -> this[p1] >= piv;
      while (compare(this[p2], piv) <= 0 && p1 < p2) {
        // this[p2] > piv;
        p2--;
      }
      // find -> this[p2] <= piv;

      if (p1 < p2) {
        swap(p1, p2);
      }
    }
    if (p1 - 1 === start) {
      if (compare(this[p1], piv) > 0) {
        swap(p1, start);
      }
    } else {
      if (compare(this[p1 - 1], piv) > 0) {
        swap(p1 - 1, start);
      }
    }
    if (p1 - 2 > start) {
      sort(start, p1 - 2);
    }
    if (end > p1) {
      sort(p1, end);
    }
  };
  sort(0, this.length - 1);
  return this;
}

const arr = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8];
qs.call(arr, (a, b) => b - a);

console.log(arr);
console.log("swapTimes", swapTimes);

交换次数最优解：交换9次。
compare换成a-b也对，并且只交换6次。