快速排序(《图解算法》笔记)
学习分而治之(divide and conquer, D&C)——快速排序
书中先讲了一个小案例,如果将一块长方形土地均匀分成方块,且分出的方块要尽可能大
两个要点:
- 找出基线条件,这种条件必须尽可能简单
- 不断将问题分解,直到符合基线条件(递归条件)
案例分析 基线条件:一条边是另一条边的整数倍 递归条件:长边整除短边划出区域,剩余区域继续调用基线条件和递归条件
答案:1680 * 640的土地,按短边整数倍长分出2 * 640 * 640的区域,剩余区域为640 * 400; 第二步分出240 * 240区域,剩余区域为240 * 160;第三步分出160 * 160区域,剩余区域为160 * 80;因为160为80整数倍,所以可均匀分出的方块边长为80
ps: 该结论可搜索欧几里得算法
快速排序
- 对于[]或者[1]这类数组,是不需要排序的,这是快速排序的基线条件
对于[33, 15, 10]
这种数组应该怎么做呢?
首先,从数组种选择一个元素,这个元素被称为基准值(pivot)
然后根据剩余元素对比基准值,可分成小于基准值的数组和大于基准值的数组(递归条件)
最后,将两个数组再用此方法排序,直到满足基线条件,将两个数组和基准值相结合
得到[15, 10], 33, []
,
再将[15, 10]
做排序得[10], 15, []
相结合得[10, 15, 33]
案例分析 基线条件:数组长度小于2 递归条件:选择其中一个元素作为基准值,与剩余元素比对,分割成小于和大于两个数组
答案(js版本):
function qsort(arr) {
if (!(arr instanceof Array)) throw new Error('arr is not a Array');
if (arr.length < 2) return arr;
var pivot = arr[0];
var less = [];
var greater = [];
for (i = 1; i < arr.length; i++) {
if (arr[i] < pivot) less.push(arr[i]);
else greater.push(arr[i])
}
return qsort(less).concat([pivot]).concat(qsort(greater));
}