js实现快速排序（in-place）简述
快速排序，⼜称划分交换排序。以分治法为策略实现的快速排序算法。
本⽂主要要谈的是利⽤javascript实现in-place思想的快速排序
分治法：
在中，分治法是建基于多项分⽀的⼀种很重要的算法。字⾯上的解释是“分⽽治之”，就是把⼀个复杂的问题分成两个或更多的相同或相似的⼦问题，直到最后⼦问题可以简单的直接求解，原问题的解即⼦问题的解的合并。（摘⾃）
快速排序的思想
数组中指定⼀个元素作为标尺，⽐它⼤的放到该元素后⾯，⽐它⼩的放到该元素前⾯，如此重复直⾄全部正序排列。
快速排序分三步：
1. 选基准：在数据结构中选择⼀个元素作为基准(pivot)
2. 划分区：参照基准元素值的⼤⼩，划分⽆序区，所有⼩于基准元素的数据放⼊⼀个区间，所有⼤于基准元素的数据放⼊另⼀区间，分
区操作结束后，基准元素所处的位置就是最终排序后它应该所处的位置
3. 递归：对初次划分出来的两个⽆序区间，递归调⽤第 1步和第 2步的算法，直到所有⽆序区间都只剩下⼀个元素为⽌。
现在先说说普遍的实现⽅法（没有⽤到原地算法）
function quickSort(arr) {
if (arr.length <= 1) return ;
//取数组最接近中间的数位基准，奇数与偶数取值不同，但不印象，当然，你可以选取第⼀个，或者最后⼀个数为基准，这⾥不作过多描述
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
/
/左右区间，⽤于存放排序后的数
var left = [];
var right = [];
console.log('基准为：' + pivot + ' 时');
for (var i = 0; i < arr.length; i++) {
console.log('分区操作的第 ' + (i + 1) + ' 次循环：');
//⼩于基准，放于左区间，⼤于基准，放于右区间
if (arr[i] < pivot) {
left.push(arr[i]);
console.log('左边：' + (arr[i]))
} else {
right.push(arr[i]);
sort函数 jsconsole.log('右边：' + (arr[i]))
}
}
//这⾥使⽤concat操作符，将左区间，基准，右区间拼接为⼀个新数组
//然后递归1，2步骤，直⾄所有⽆序区间都只剩下⼀个元素，递归结束
return quickSort(left).concat([pivot], quickSort(right));
}
var arr = [14, 3, 15, 7, 2, 76, 11];
console.log(quickSort(arr));
/*
* 基准为7时，第⼀次分区得到左右两个⼦集[ 3, 2,]  7  [14, 15, 76, 11];
* 以基准为2，对左边的⼦集[3,2]进⾏划分区排序，得到[2] 3。左⼦集排序全部结束
* 以基准为76，对右边的⼦集进⾏划分区排序，得到[14, 15, 11] 76
* 此时对上⾯的[14, 15, 11]以基准为15再进⾏划分区排序， [14, 11] 15
* 此时对上⾯的[14, 11]以基准为11再进⾏划分区排序， 11  [14]
* 所有⽆序区间都只剩下⼀个元素，递归结束
*
*/
通过断点调试，可得出结果。
弊端：
它需要Ω(n)的额外存储空间，跟归并排序⼀样不好。在⽣产环境中，需要额外的内存空间，影响性能。
同时，很多⼈认为上边的就是真正的快速排序了。所以，在下⾯，很有必要的推荐in-place算法的快速排序
有关于原地算法可参考，被墙的同学，百度也差不多。
in-place
快速排序⼀般是⽤递归实现，最关键是partition分割函数，它将数组划分为两部分，⼀部分⼩于pivot，另⼀部分⼤于pivot。具体原理上边提过
function quickSort(arr) {
// 交换
function swap(arr, a, b) {
var temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
// 分区
function partition(arr, left, right) {
/**
* 开始时不知最终pivot的存放位置，可以先将pivot交换到后⾯去
* 这⾥直接定义最右边的元素为基准
*/
var pivot = arr[right];
/**
* 存放⼩于pivot的元素时，是紧挨着上⼀元素的，否则空隙⾥存放的可能是⼤于pivot的元素，
* 故声明⼀个storeIndex变量，并初始化为left来依次紧挨着存放⼩于pivot的元素。
*/
var storeIndex = left;
for (var i = left; i < right; i++) {
if (arr[i] < pivot) {
/**
* 遍历数组，到⼩于的pivot的元素，（⼤于pivot的元素会跳过）
* 将循环i次时得到的元素，通过swap交换放到storeIndex处，
* 并对storeIndex递增1，表⽰下⼀个可能要交换的位置
*/
swap(arr, storeIndex, i);
storeIndex++;
}
}
// 最后：将pivot交换到storeIndex处，基准元素放置到最终正确位置上
swap(arr, right, storeIndex);
return storeIndex;
}
function sort(arr, left, right) {
if (left > right) return;
var storeIndex = partition(arr, left, right);
sort(arr, left, storeIndex - 1);
sort(arr, storeIndex + 1, right);
}
sort(arr, 0, arr.length - 1);
return arr;
}
console.log(quickSort([8, 4, 90, 8, 34, 67, 1, 26, 17]));
分区的优化
这⾥细⼼的同学可能会提出，选取不同的基准时，是否会有不同性能表现，答案是肯定的，但，因为，我是搞前端的，对算法不是很了解，所以，这个坑留给厉害的⼈来填补。
复杂度
快速排序是排序速度最快的算法，它的时间复杂度是O(log n)
在平均状况下，排序n个项⽬要(n log n)次⽐较。在最坏状况下则需要Ο(n2)次⽐较.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。