【算法】排序（快排、堆排、归并）、查找

快速排序

具体做法

首先选第一个待排序元素作为枢轴，根据枢轴将待排序列分为两个子列，这两个子列必须满足一下条件：一个子列的元素关键字都不大于枢轴的关键字，另一个子列的元素关键字都不小于枢轴，接着对两个子列分别进行累死操作——选定枢轴并进行划分。这样不断划分知道所有子列仅包含0或个元素位置。

快排是一个递归算法，假设待排序列A
（1）如果A中元素个数为0或1，则返回；否则，继续；
（2）选取A中的一个元素p作为枢轴
（3）讲A中剩下的元素“划分”成两个不相交的集合：A1——key比枢轴的key小的；A2——key比枢轴的key大的；
（4）QuickSort（A1），p，QuickSort（A2）
划分具体做法：设置两个标志low和high，分别指向A中的第一个元素和最后一个元素。首先，从high所指位置起向前搜索，找到第一个关键字小于p.key的元素和枢轴p交换，然后从low所指位置起向后搜索，找到第一个关键字大于p.key的元素和枢轴p交换，重复这两步直至low=high为止。