手撕排序算法C++
即将进入秋招阶段，面试手撕代码是常有的事情，所以呢，早点准备，以防万一。现场手撕代码，最常见的就是排序，今天先上来堆排序和快速排序。
（PS:这里的代码是我为面试现场准备的，效率方面肯定不是最佳实现）
8月10日 快速排序和堆排序
class sort{
public:/*最大堆调整，size的作用是限制该函数只对数组前size个数组成的
子数组做最大堆调整，因为随着排序的进行，堆顶数据会逐步移到后面
*/
static void adjustHead(std::vector & data,int size)
{
for(int j=size/2;
j>=0;
j--)
{
int lchild = j*2+1;
int rchild = j*2+2;
if(lchild>=size||rchild>=size)
continue;
if(max(data[j],max(data[lchild],data[rchild]))==data[lchild])
{
data[j]=data[lchild]-data[j];
data[lchild]=data[lchild]-data[j];
data[j]=data[lchild]+data[j];
continue;
}if(max(data[j],max(data[lchild],data[rchild]))==data[rchild])
{
data[j]=data[rchild]-data[j];
data[rchild]=data[rchild]-data[j];
data[j]=data[rchild]+data[j];
}
}}//调整+去堆顶+后移
static std::vector head_sort(std::vector input){
for(int j=(int)input.size()-1;
j>0;
j--)
{
adjustHead(input,j+1);
input[0]=input[j]-input[0];
input[j]=input[j]-input[0];
input[0]=input[j]+input[0];
}return input;
}
//快排的一个偷懒写法，可以借助std::partition来达到分组的效果
static std::vector quick_sort(std::vector input){
if(input.empty())
return input;
int pivot = input.front();
//lim是一个迭代器
auto lim = std::partition(input.begin(),input.end(),[&pivot](int & a){
return a【手撕排序算法C++】 left;
vector right;
for(auto iter=input.begin();
iter!=lim;
iter++)
left.push_back(*iter);
for(auto iter=++lim;
iter!=input.end();
iter++)
right.push_back(*iter);
auto left_res=quick_sort(left);
auto right_res=quick_sort(right);
left_res.push_back(pivot);
left_res.insert(left_res.end(),right_res.begin(),right_res.end());
return left_res;
}};
推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- 排序（归并排序）
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 【图解】9张图彻底搞懂堆排序