快速排序也许是最常用的排序算法了。它的复杂度为O(nlogn)，且它的性能通常比其他的复杂度为O(nlogn)的排序算法要好。和归并排序一样，快速排序也使用分治的方法，将原始数组分为较小的数组(但它没有像归并排序那样将它们分割开)。
快速排序比到目前为止你学过的其他排序算法要复杂一些。让我们一步步地来学习。
(1) 首先，从数组中选择中间一项作为主元。
(2) 创建两个指针，左边一个指向数组第一个项，右边一个指向数组最后一个项。移动左指针直到我们找到一个比主元大的元素，接着，移动右指针直到找到一个比主元小的元素，然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。这一步叫作划分操作。
(3) 接着，算法对划分后的小数组(较主元小的值组成的子数组，以及较主元大的值组成的子数组)重复之前的两个步骤，直至数组已完全排序。
让我们开始快速排序的实现吧:
this.quickSort = function(){
quick(array, 0, array.length - 1);
};
就像归并算法那样，开始我们声明一个主方法来调用递归函数，传递待排序数组，以及索引0及其最末的位置(因为我们要排整个数组，而不是一个子数组)作为参数。
var quick = function(array, left, right){
var index; //{1}
if (array.length > 1) { //{2}
index = partition(array, left, right); //{3}
if (left < index - 1) {
quick(array, left, index - 1);
}
if (index < right) { //{6}
quick(array, index, right);
}
}
}
首先声明index(行{1})，该变量能帮助我们将子数组分离为较小值数组和较大值数组，这样，我们就能再次递归的调用quick函数了。partition函数返回值将赋值给index(行{3})。
如果数组的长度比1大(因为只有一个元素的数组必然是已排序了的(行{2})，我们将对给定子数组执行partition操作(第一次调用是针对整个数组)以得到index(行{3})。如果子数组存在较小值的元素(行{4})，则对该数组重复这个过程(行{5})。同理，对存在较大值得子数组也是如此，如果存在子数组存在较大值，我们也将重复快速排序过程(行{7})。
1. 划分过程
第一件要做的事情是选择主元(pivot)，有好几种方式。最简单的一种是选择数组的第一项(最左项)。然而，研究表明对于几乎已排序的数组，这不是一个好的选择，它将导致该算法的最差表现。另外一种方式是随机选择一个数组项或是选择中间项。
现在，让我们看看划分过程:
var partition = function(array, left, right) {
var pivot = array[Math.floor((right + left) / 2)], //{8}
i = left,
j = right;
while (i <= j) {
while (array[i] < pivot) { //{12}
i++;
}
while (array[j] > pivot) { //{13}
j--;
}
if (i <= j) { //{14}
swap(array, i, j); //{15}
i++;
j--;
}
}
return i; //{16}
};
在本实现中，我们选择中间项作为主元(行{8})。我们初始化两个指针:left(低——行{9})，初始化为数组第一个元素;right(高——行{10})，初始化为数组最后一个元素。
只要left和right指针没有相互交错(行{11})，就执行划分操作。首先，移动left指针直到找到一个元素比主元大(行{12})。对right指针，我们做同样的事情，移动right指针直到我们找到一个元素比主元小。
当左指针指向的元素比主元大且右指针指向的元素比主元小，并且此时左指针索引没有右指针索引大(行{14})，意思是左项比右项大(值比较)。我们交换它们，然后移动两个指针，并重复此过程(从行{11}再次开始)。
在划分操作结束后，返回左指针的索引，用来在行{3}处创建子数组。
swap函数和我们在本章开始为冒泡排序算法实现的相同。我们也可以将此函数替换为以下ES6代码。
[array[index1], array[index2]] = [array[index2], array[index1]];
2. 快速排序实战
让我来一步步地看一个快速排序的实际例子:
给定数组[3, 5, 1, 6, 4, 7, 2]，前面的示意图展示了划分操作的第一次执行。
下面的示意图展示了对有较小值的子数组执行的划分操作(注意7和6不包含在子数组之内):
接着，我们继续创建子数组，请看下图，但是这次操作是针对上图中有较大值的子数组(有1的那个较小子数组不用再划分了，因为它仅含有一个项)。
子数组([2, 3, 5, 4])中的较小子数组([2, 3])继续进行划分(算法代码中的行{5}):
然后子数组([2, 3, 5, 4])中的较大子数组([5, 4])也继续进行划分(算法中的行{7})，示意图如下:
最终，较大子数组[6, 7]也会进行划分(partition)操作，快速排序算法的操作执行完成。
网友评论