about quick sort algorithm

算法
Catalogue
  1. 1. 历史
  2. 2. 思路1：非原址排序
  3. 3. 思路2：原址排序
  4. 4. 原址与非原址快排的性能对比
  5. 5. 参考

历史

快速排序算法是由 Tony Hoare 在 1959 年发明的。如果实现得好，那么它的速度可以达到其两个主要竞争者——归并排序与堆排序——的两倍到三倍以上。

在高速的实现中，快排是一个不稳定的算法，即它不能保证原来相等的值的位置不变。

思路1：非原址排序

pivot，为“中枢、支点”的意思。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * q-1.js
 */
// 选取中间值为基准点、高效的实现示例
function quickSort1(A) {
  if (A.length <= 1) {
    return A;
  }

  var pivot = Math.floor(A.length / 2);
  var left = [];
  var right = [];

  for (var i = 0; i < A.length; i++) {
    if (i === pivot) {
      continue;
    } else if (A[i] <= A[pivot]) {
      left.push(A[i]);
    } else {
      right.push(A[i]);
    }
  }

  return quickSort(left).concat([A[pivot]].concat(quickSort(right)));
}


var A = [1, 3, 89, 5, 34, 2, 80, 50];
var b = quickSort1(A);
console.log(b);

思路2：原址排序

上面的排序实现里，left、right 数组都是新创建的，无疑会增加内存的消耗。这里再给出一版基于原址的快速排序实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * q-2.js
 */
function quickSort2(A) {
  /**
   * 在原数组中交换数组里的两个项
   */
  var swapArrayItems = function(arr, i, j) {
    var tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
  };

  /**
   * 在原数组中寻找分隔左右数组的项的下标
   */
  var partition = function(arr, left, right) {
    var pivot = arr[Math.floor((left + right) / 2)];
    var i = left;
    var j = right;
    while(i < j) {
      while(arr[i] < pivot) i++;
      while(arr[j] > pivot) j--;
      if (i <= j) {
        swapArrayItems(arr, i, j);
        i++;
        j--;
      }
    }
    return i;
  };

  /**
   * 原址快排函数
   */
  var quick = function(arr, left, right) {
    var index;
    if (arr.length > 1) {
      index = partition(arr, left, right);

      if (left < index - 1) {
        quick(arr, left, index - 1);
      }

      if (right > index) {
        quick(arr, index, right);
      }
    }
  };

  return quick(A, 0, A.length - 1);
}

原址与非原址快排的性能对比

如果对上面的两种实现以及 JavaScript 内置的 sort 方法进行性能对比，会发现原址排序快很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * test.js
 */
var q1 = require('./q-1.js');
var q2 = require('./q-2.js');

var arr1 = [3, 5, 1, 6, 4, 7, 2];
var arr2 = arr1.map(i => i);
var arr3 = arr1.map(i => i);
var NUM = 100000;

console.time('非原址排序');
for (var i = 0; i < NUM; i++) {
  q1(arr1);
}
console.timeEnd('非原址排序');

console.time('原址排序');
for (var i = 0; i < NUM; i++) {
  q2(arr2);
}
console.timeEnd('原址排序');

console.time('Array.prototype.sort');
for (var i = 0; i < NUM; i++) {
  arr3.sort();
}
console.timeEnd('Array.prototype.sort');

console.log('arr1 => ', arr1);
console.log('arr2 => ', arr2);
console.log('arr3 => ', arr3);

运行时间对比（10万次）：

  • 非原址排序: 246.511ms
  • 原址排序: 31.057ms
  • Array.prototype.sort: 56.593ms

注：数组原型上的 sort 方法有不同的实现，根据参考资料[3]，Mozilla Firefox 使用了归并排序来实现 sort，而 Chrome 则使用了快排的一种变体。

参考

第一篇是维基百科的词条，非常有意思。

  1. https://en.wikipedia.org/wiki/Quicksort
  2. http://www.ruanyifeng.com/blog/2011/04/quicksort_in_javascript.html
  3. Loiane Groner. 学习JavaScript数据结构与算法[M], 北京: 人民邮电出版社, 2015.
Share