目录
- 1 知识点
- 2 算法模板
1 知识点
排序算法:
- 快速排序
算法关键步骤:
step1:确定分界点。
step2:调整位置,使得分界点左边元素都小于等于分界点,分界点右边元素都大于等于分界点。可以使用双指针算法来实现此步骤。
step3:递归处理左边和右边。 - 归并排序
二分算法:
- 整数二分:
存在边界情况,容易得到错误的解或进入死循环。 - 浮点数二分:
正常求解即可,比较容易处理。
2 算法模板
//对向量类容器nums中下标在[l,r]范围内元素进行排序
void quick_sort(vector<int>& nums, int l, int r) {
if (l >= r) return;
int x = nums[l + r >> 1];
int i = l - 1; //因为下文中使用的是do...while...语句,循环块肯定会被执行一次,故先构造出初始状态
int j = r + 1;
while (i < j) {
do i++; while(nums[i] < x);
do j--; while(nums[j] > x);
if (i < j) {
swap(nums[i], nums[j]);
}
}
quick_sort(nums, l, j);
quick_sort(nums, j + 1, r);
return;
}