快速排序

• 快速排序
  • 基本思想
  • 代码
  • 时间复杂度
  • 注意事项
  • 模板题
• 归并排序
  • 基本思想
  • 代码
  • 时间复杂度
  • 模板题

基本思想

1. 随机找到一个基准数.
2. 将所有小于他的数放在左边，所有大的数放在右边.
3. 最后重复以上操作，直至各部分左右指针相遇.

如GIF所示，一个无序的数组3 5 8 1 2 9 4 7 6
把右端点作为基准数，然后左指针开始从左扫描，当遇到>=6 的数时停止，此时右指针就开始扫描，当遇到<=6 的数时停止，这两个数的位置并不符合第二个基本思想，那么就进行交换，随后左指针再次开始扫描，当左右指针相遇时为第一次遍历.

数组被分开为两个部分，重复上面操作.

代码

int op[10010];//开数组空间

void quick_sort(int op[], int l, int r) {
	if (l >= r)//递归的结束标志
		return ;
	int key = op[(l + r) / 2];//基准数
	int i = l - 1, j = r + 1;//左右指针(为什么要-1，+1后面要讲到)
	while (i < j) {
		do
			i++;
		while (op[i] < key);//左指针扫描
		do
			j--;
		while (op[j] > key);//右指针扫描
		if (i < j) {//数字交换
			int t = op[i];
			op[i] = op[j];
			op[j] = t;
		}
	}
	quick_sort(op, l, j);//递归
	quick_sort(op, j + 1, r);
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &op[i]);
		
	quick_sort(op, 0, n - 1);
	
	for (int i = 0; i < n; i++)
		printf("%d ", op[i]);
		
	return 0;
}

时间复杂度

快速排序的时间复杂度为O(nlogn)
这里借用 的解释
快速排序每次将数组区间分为两个部分，在最理想的情况下，即所选取的基准数正好是这个区间的中位数，那么每次分割就可以分为两个大小相同的区间，然后接着递归.

• 递归第一层，n个数被分为2个区间，每个区间有n/2个数.
• 递归第二层，n个数被分为4个区间，每个区间有n/4个数.
• 递归第三层，n个数被分为8个区间，每个区间有n/8个数.
  ………
• 递归第logn层，n个数被分为n个区间，每个区间里有1个数.
  一共进行logn层递归，而每一次递归都是O(n)，所以快排的时间复杂度为O(nlogn)，但是当数组本身就是有序数列的时候，时间复杂度就很立马变为O(n^2)，因此快速排序比较不稳定

注意事项

• 为什么要+1,-1？

• 为什么使用do ;while;而不用while

• 为什么使用数组中间值作为基准，而不是用端点

• 为什么交换前检查指针的相对位置
  1. 问题一和问题二是同一个问题，这是因为为了防止出现i与 j所指数字的值相等，交换之后i与j所指数字依然相等，从而导致程序崩溃的情况发生，所以每次要先加减.

  2. 问题三与问题四也是同一个，将中间值作为基准是为了防止出现边界问题.

当你选取左端点作为基准的时候quick_sort(op, l, j),quick_sort(op, j + 1, r);这里的递归不可以将i作为递归分界线
相应的选取右端点作为基准的时候不可以将j作为递归分界线.

是因为会出现单边死循环，如：2 1 3 5 4

模板题

acwing785
洛谷P1177

归并排序

基本思想

1. 将待排序区间无限分割，分割为不可分割的子区间
2. 然后将所有的子区间进行两两合并，合并过程中完成排序操作，最终合并得到的新区间就是有序序列

相比于快排，归并排序就没有那么多的边界问题，也就很简单了，而且时间复杂度都是O(nlogn)不会出现像快排那样最多O(n^2)的情况.

代码

#include 
int op[10010];
int temp[10010];

void merge_sort(int op[], int l, int r) {
	if (l >= r)
		return ;
	int mid = (l + r ) / 2;
	merge_sort(op, l, mid), merge_sort(op, mid + 1, r);//先递归
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r) {//后排序
		if (op[i] <= op[j])
			temp[k++] = op[i++];
		else
			temp[k++] = op[j++];
	}
	while (i <= mid)//多余的数加入数组中
		temp[k++] = op[i++];
	while (j <= r)
		temp[k++] = op[j++];
	for (i = l, j = 0; i <= r; i++, j++)
		op[i] = temp[j];
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &op[i]);
	merge_sort(op, 0, n - 1);
	for (int i = 0; i < n; i++)
		printf("%d ", op[i]);
	return 0;
}

时间复杂度

• 递归第一层，n个数被分为2个区间，每个区间有n/2个数.
• 递归第二层，n个数被分为4个区间，每个区间有n/4个数.
• 递归第三层，n个数被分为8个区间，每个区间有n/8个数.
  ………
• 递归第logn层，n个数被分为n个区间，每个区间里有1个数.
  一共进行logn层递归，而每一次递归都是O(n)，所以归并排序的时间复杂度为O(nlogn).

模板题

acwing787