快速排序采用分治法的一个非常典型的应用
算法思想
快速排序使用分治法策略来把一个序列分为两个子序列，其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
时间复杂度
O(nlgn)
步骤：
- 从数列中挑出一个元素，称为"基准"（pivot）
- 所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面
- 递归的把小于基准值元素的子数列和大于基准值元素的子数列排序
举例
现有一个数组：arr = [6,4,5,2,7]
那么先拿出一个基准：5
从左开始遍历该数组：
6 4 5 2 7
|
大于5
如果大于基准5则放在基准右边
4 5 6 2 7
|
放此位置
继续遍历：
4 5 6 2 7
|
小于5
如果小于基准5则放在基准左边，故位置不变，继续遍历：
4 5 6 2 7
|
小于5
则放在基准左边：
4 2 5 6 7
|
放此位置
那么我们的一次遍历就完成了，以此类推，再遍历左边序列以及右边序列
代码实现
常用实现方法如下，c和java都可以：
function quick_sort(arr,low,high){
var i = low;
var j = high;
var temp = arr[i];
if(low < high){
while(i < j){
while(i<j && arr[j] >= temp){
j--;
}
arr[i] = arr[j];
while(i<j && arr[i] <= temp){
i++;
}
arr[j] = arr[i];
}
arr[i] = temp;
quick_sort(arr,low,i-1);
quick_sort(arr,i+1,high);
}
else{
return;
}
}
var arr = [6,4,5,2,7];
quick_sort(arr,0,arr.length-1)
console.log(arr); // [2,4,5,6,7]
以下方法只适用于JavaScript，因为使用了JavaScript的数组的方法，并且该方法空间复杂度比较大，因为多使用了两个数组
function quick_sort(arr) {
if (arr.length <= 1) {
return arr;
}
var middle = Math.floor(arr.length / 2);
var pivot = arr.splice(middle, 1)[0];
var low = [];
var high = [];
for (var i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
low.push(arr[i]);
} else {
high.push(arr[i]);
}
}
return quickSort(low).concat([middleValue], quickSort(high));
}
var arr = [6,4,5,2,7];
quick_sort(arr); // [2,4,5,6,7]
优化思路
- 对于小数组，可以采用插入排序，避免递归调用
- 采用子数组的一部分元素的中位数来切分数组
