1、算法原理
将原问题分解为若干个规模更小但结构与原问题相似的子问题。 递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
2、排序流程
（1）在数据集之中，选择一个元素作为” 基准” （pivot）。
（2）所有小于” 基准” 的元素，都移到” 基准” 的左边；所有大于” 基准” 的元素，都移到” 基准” 的右边。 这个操作称为分区 (partition) 操作，分区操作结束后，基准元素所处的位置就是最终排序后它的位置。
（3）对” 基准” 左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
3、实例分析
举例来说，现有数组 arr = [3,7,8,5,2,1,9,5,4]，分区可以分解成以下步骤：
（1）首先选定一个基准元素，这里我们元素 5 为基准元素（基准元素可以任意选择）：
pivot
↓
3 7 8 5 2 1 9 5 4（2）将基准元素与数组中最后一个元素交换位置，如果选择最后一个元素为基准元素可以省略该步：
pivot
↓
3 7 8 4 2 1 9 5 5（3）从左到右（除了最后的基准元素），循环移动小于基准元素 5 的所有元素到数组开头，留下大于等于基准元素的元素接在后面。
在这个过程它也为基准元素找寻最后摆放的位置。 循环流程如下：
循环 i == 0 时，storeIndex == 0，找到一个小于基准元素的元素 3，那么将其与storeIndex 所在位置的元素交换位置，这里是 3 自身，交换后将 storeIndex 自增 1，storeIndex == 1：
pivot
↓
3 7 8 4 2 1 9 5 5
↑
storeIndex循环 i == 3 时，storeIndex == 1，找到一个小于基准元素的元素 4：
┌──────┐ pivot
↓ ↓ ↓
3 7 8 4 2 1 9 5 5
↑ ↑
storeIndex i交换位置后，storeIndex 自增 1，storeIndex == 2：
pivot
↓
3 4 8 7 2 1 9 5 5
↑
storeIndex循环 i == 4 时，storeIndex == 2，找到一个小于基准元素的元素 2：
┌───────┐ pivot
↓ ↓ ↓
3 4 8 7 2 1 9 5 5
↑ ↑
storeIndex i交换位置后，storeIndex 自增 1，storeIndex == 3：
pivot
↓
3 4 2 7 8 1 9 5 5
↑
storeIndex循环 i == 5 时，storeIndex == 3，找到一个小于基准元素的元素 1：
┌───────┐ pivot
↓ ↓ ↓
3 4 2 7 8 1 9 5 5
↑ ↑
storeIndex i交换后位置后，storeIndex 自增 1，storeIndex == 4：
pivot
↓
3 4 2 1 8 7 9 5 5
↑
storeIndex循环 i == 7 时，storeIndex == 4，找到一个小于等于基准元素的元素 5：
┌───────────┐ pivot
↓ ↓ ↓
3 4 2 1 8 7 9 5 5
↑ ↑
storeIndex i交换后位置后，storeIndex 自增 1，storeIndex == 5：
pivot
↓
3 4 2 1 5 7 9 8 5
↑
storeIndex（4）循环结束后交换基准元素和 storeIndex 位置的元素的位置：
pivot
↓
3 4 2 1 5 5 9 8 7
↑
storeIndex那么 storeIndex 的值就是基准元素的最终位置，这样整个分区过程就完成了。
引用维基百科图片
4、代码实现
function quickSort(array) {
// 交换元素位置
function swap(array, i, k) {
var temp = array[i];
array[i] = array[k];
array[k] = temp;
}
// 数组分区， 左小右大
function partition(array, left, right) {
var storeIndex = left;
var pivot = array[right]; // 直接选最右边的元素为基准元素
for (var i = left; i < right; i ++) {
if (array[i] < pivot) {
swap(array, storeIndex, i);
storeIndex ++; // 交换位置后， storeIndex 自增1， 代表下一个可能要交换的位置
}
}
swap(array, right, storeIndex); // 将基准元素放置到最后的正确位置上
return storeIndex;
}
function sort(array, left, right) {
if (left > right) {
return;
}
var storeIndex = partition(array, left, right);
sort(array, left, storeIndex - 1);
sort(array, storeIndex + 1, right);
}
sort(array, 0, array.length - 1);
return array;
}
var arr = [3, 7, 8, 5, 2, 1, 9, 5, 4];
console.log(quickSort(arr));
评论(0)