目录
算法基础
第一节 基础算法（一）
1.1排序
一、快速排序
分治法：分治法原则是把原问题分解成几个子问题，分解成相同问题，各个子问题相互独立。 将一个问题划分为同一类型的若干子问题，子问题最好规模相同。 对这些子问题求解（一般使用递归方法，但在问题规模足够小时，有时也会利用另一个算法）。有必要的话，合并这些子问题的解，以得到原始问题的答案。
确定分界点，调整范围，递归处理左右两段
快速排序：在待排序的数列中，我们首先要找一个数字作为基准数（这只是个专用名词）。为了方便，我们一般选择第 1 个数字作为基准数（其实选择第几个并没有关系）。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。
首先从数列的右边开始往左边找，我们设这个下标为 i，也就是进行减减操作（i--），找到第 1 个比基准数小的值，让它与基准值交换；接着从左边开始往右边找，设这个下标为 j，然后执行加加操作（j++），找到第 1 个比基准数大的值，让它与基准值交换；然后继续寻找，直到 i 与 j 相遇时结束，最后基准值所在的位置即 k 的位置，也就是说 k 左边的值均比 k 上的值小，而 k 右边的值都比 k 上的值大。
7和3进行交换，交换后ij相遇，相遇后，j和基准元素i进行交换，第一轮就变成326798
i指向3j指向2，ij分别进行试探，ij相遇，ij交换变成236后对798进行排序，i指向7j指向8然后ij进行试探，第二轮就变成236798，接着对98进行排序。第三轮变成236789
左边的都是小于基准值，右边的都是大于基准值。
例题：
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
void quick_sort(int q[], int l, int r) {
if (l >= r) return;//判断边界里面有一个或者零个直接return
int x = q[(l + r) >> 1];//取分界点x
int i = l - 1;//指针
int j = r + 1;//指针
while (i < j) {
do i ++ ; while (q[i] < x);
do j -- ; while (q[j] > x);
if (i < j) swap(q[i],q[j]);;//交换，
}
quick_sort(q, l, j);//边界问题
quick_sort(q, j + 1, r);
}
int main () {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &q[i]);
}
quick_sort(q, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", q[i]);
}
}
二、归并排序
1.排序思路
1.确定分界点 mid =()
2.递归排序 left right
3.归并 合二为一(重点)
2.归并排序时间复杂度
3.归并排序代码
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], tmp[N];
void merge_sort(int q[], int l, int r)//q[]为数组里面的数字，l为左边界，r为右边界
{
if (l >= r) return;//左边界大于右边界时，错误，不用进行排序
int mid = l + r >> 1;//取中点
merge_sort(q, l, mid);//递归排序左边
merge_sort(q, mid + 1, r);//递归排序右边
//左右两边都已经排好序
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];//对排好的序进行归并，将小的放进去
else tmp[k ++ ] = q[j ++ ];
while (i <= mid) tmp[k ++ ] = q[i ++ ];//左半边没有循环完
while (j <= r) tmp[k ++ ] = q[j ++ ];//右半边没有循环完
for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];//输出排序结果
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
merge_sort(a, 0, n - 1);
for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);
return 0;
}