快速排序法 Quicksort

快速排序法（Quicksort）是目前排序算法里最常用的算法之一，由Tony Hoare于1959年开发，61年发布

引用Wiki

Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959,[1] with his work published in 1961,[2] it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.[3]

图解

这个gif图片特别明确地呈现了其实现原理

• 在数组所有元素中随机找一个基准值
• 所有小于基准点到左边，大于基准点到右边
• 左右两边的合集在进行以上两个步骤，排序完成

如:

[45, 20, 10, 28, 98, 67, 90]

以28为基准值，位移

[20, 10, 28, 45, 98, 67, 90]

左边的合集在找一个基准值

[20, 10]

排序后，变成

[10, 20]

右边的合集也找一个基准值

[45, 98, 67, 90]

排序后，变成

[45, 67, 98, 90]

依此类推，直到剩下最后一个数字

我们用程序实现一下:

var quickSort = (function () {
  var sort = function (arr) {
    // 这里要做一下判断，否则就死循环啦
    if (arr.length <= 1) {
      return arr;
    }

    // 定义左右合集
    var left = [];
    var right = [];

    for (var i = 1; i < arr.length; i++) {
      // 小于基准点到左边，否则到右边
      if (arr[i] < arr[0]) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }

    // 递归调用，最后拼接成数组返回
    return sort(left).concat(arr[0], (sort(right)));
  };
 
  return sort;
})();
 
 
var arr1 = [45, 20, 10, 28, 98, 67, 90];
console.log(quickSort(arr1)); // Output: [10, 20, 28, 45, 67, 90, 98]

以上是JavaScript实现方法，大家可以试试!