一、分而治之（divide and conquer，D&C）
定义：一种著名的递归式问题解决方法。D&C并非可用于解决问题的算法，而是一种解决问题的思路。
D&C的工作原理：
(1) 找出简单的基线条件；
(2) 确定如何缩小问题的规模，使其符合基线条件。
例子：对数组进行求和，[2, 4, 6]
第一步：找出基线条件。最简单的数组什么样呢？（如果数 组不包含任何元素或只包含一个元素，计算总和将非常容易。）
基线条件：
[] = 0 // 不包含任何元素
[7] = 7 // 只包含一个元素
第二步：缩小问题的规模。每次递归调用都必须离空数组更近一步。
===> sum( [2, 4, 6] )
===> 2 + sum( [4, 6] )
===> 2 + ( 4 + sum( [6] ) ) // sum( [6] ) 基线条件，只包含一个元素，sum( [6] ) = 6
----------------------------------------------------------------------------- 递归 保存了 未完成的函数 调用的状态
===> 2 + ( 4 + 6 )
===> 2 + ( 10 )
===> 12
二、快速排序
定义
快速排序（Quicksort）是对冒泡排序算法的一种改进。快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
时间复杂度
O(n log n)
*在最糟情况下，O(n^2 )
*最佳情况也是平均情况下，O(n log n)
输入
数组
输出
按一定规则排序的 数组
代码
Python
def quick_sort(data):
"""快速排序 会改变原数组"""
if len(data) >= 2: # 递归入口及出口
mid = data[len(data)//2] # 选取基准值，也可以选取第一个或最后一个元素
left, right = [], [] # 定义基准值左右两侧的列表
data.remove(mid) # 从原始数组中移除基准值 *会修改传入的数组
for num in data:
if num >= mid:
right.append(num)
else:
left.append(num)
return quick_sort(left) + [mid] + quick_sort(right)
else:
return data
def quicksort(array):
"""快速排序 列表推导式版本"""
if len(array) < 2:
return array # 基线条件：为空或只包含1个元素的数组是”有序“的
else:
pivot = array[0] # 选取基准值，缩小问题规模
less = [i for i in array[1:] if i <= pivot] # 子数组：所有小于基准值的元素
greater = [i for i in array[1:] if i > pivot] # 子数组：所有大于基准值的元素
return quicksort(less) + [pivot] + quicksort(greater)
# 测试：
array1 = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]
array2 = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]
print(quick_sort(array1))
print(array1)
print(quicksort(array2))
# 输出为[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]
JavaScript
const quickSort = (array) => {
const sort = (arr, left = 0, right = arr.length - 1) => {
if (left >= right) {
//如果左边的索引大于等于右边的索引说明整理完毕
return;
}
let i = left;
let j = right;
const baseVal = arr[j]; // 取无序数组最后一个数为基准值
while (i < j) {
//把所有比基准值小的数放在左边大的数放在右边
while (i < j && arr[i] <= baseVal) {
//找到一个比基准值大的数交换
i++;
}
arr[j] = arr[i]; // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
while (j > i && arr[j] >= baseVal) {
//找到一个比基准值小的数交换
j--;
}
arr[i] = arr[j]; // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
}
arr[j] = baseVal; // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
sort(arr, left, j - 1); // 将左边的无序数组重复上面的操作
sort(arr, j + 1, right); // 将右边的无序数组重复上面的操作
};
const newArr = array.concat(); // 为了保证这个函数是纯函数拷贝一次数组
sort(newArr);
return newArr;
};
// 测试：
array = [2,3,5,7,1,4,6,15,5,2,7,9,10,15,9,17,12]
console.log(quickSort(array));
// 输出为[1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 9, 9, 10, 12, 15, 15, 17]