当前位置 博文首页 > 广大菜鸟的博客：算法学习（1）快速排序/归并排序/二分

最大化 缩小

    广大菜鸟的博客：算法学习（1）快速排序/归并排序/二分

    作者：[db:作者] 时间：2021-09-16 22:22 

    排序：快排，归并排序
二分：整数，浮点数

    1，快速排序大排列

    785.快速排序测试

    https：//www.acwing.com/problem/content/787
    在这里插入图片描述

    常规递归查找（不可以）

    #include<iostream>
using namespace std;

const int N = 100001;
int Partion(int[], int, int);
void Qsort(int a[], int low, int high) {
	if (low < high) {
		int p = Partion(a, low, high);
		Qsort(a, low, p - 1);
		Qsort(a, p + 1, high);
	}
}
int Partion(int a[], int low, int high) {
	int p = a[low];
	while (low < high) {
		while (low < high && a[high] >= p) high--;
		a[low] = a[high];
		while (low < high && a[low] <= p) low++;
		a[high] = a[low];
	}
	a[low] = p;
	return low;
}
int main() {
	int a[N];
	int size = 0;
	cin >> size;
	for (int i = 0; i < size; i++) {
		 cin >> a[i];
	}
	Qsort(a, 0, size - 1);
	for (int i = 0; i < size; i++) {
		cout << a[i] << " ";
	}
}

    递归法改进（可以）

    在这里插入图片描述

    #include<iostream>
using namespace std;

const int N = 100001;
int a[N] = { 0 };


void Qsort(int a[], int low, int high) {
	if (low >= high)
		return;

	int   p = a[(low + high) >> 1], i = low - 1, j = high + 1;	//	j >= l,i<=r-1

	while (i < j) {
		//a[0..i-1] <= p, a[i] >= p
		do
			i++;
		while (a[i] < p);

		// a[j+1..r] >= p, a[j] <= p
		do
			j--;
		while (a[j] > p);

		if (i < j)
			swap(a[i], a[j]);
	}
	Qsort(a, low, j);
	Qsort(a, j + 1, high);
}

int main() {
	int size;
	cin >> size;
	for (int i = 0; i < size; i++) {
		cin >> a[i];
	}
	Qsort(a, 0, size - 1);
	for (int i = 0; i < size; i++) {
		cout << a[i] << " ";
	}
}

    或

    #include<iostream>
using namespace std;

const int N = 100001;
int a[N] = { 0 };

void Qsort(int a[], int low, int high) {
	if (low >= high)
		return;

	int  i = low - 1, j = high + 1, p = a[(low + high + 1) >> 1];//

	while (i < j) {
		do
			i++;
		while (a[i] < p);

		do
			j--;
		while (a[j] > p);


		if (i < j)
			swap(a[i], a[j]);
	}

	Qsort(a, low, i-1);
	Qsort(a, i, high);
}

int main() {
	int size = 0;
	cin >> size;
	for (int i = 0; i < size; i++) {
		cin >> a[i];
	}
	Qsort(a, 0, size - 1);
	for (int i = 0; i < size; i++) {
		cout << a[i] << " ";
	}
}

    方法分析：https://www.acwing.com/solution/content/16777/

    2、归并排序

    787.归并排序测试

    https://www.acwing.com/problem/content/description/789
    在这里插入图片描述

    常规递归查找（不可以）

    #include<iostream>
using namespace std;

const int N = 100000;
int a[N],s[N];

// 比较放入
void Merge(int a[], int b[], int low, int high);
// 比较排序
void Msort(int a[], int b[], int low, int high);

void Msort(int a[], int b[], int low, int high) {
	int t[N] = { 0 };
	 //第一步：分成子问题
	if (low == high) {
		b[low] = a[high];
	}else {
		int mid = (low + high) >> 1;
		 //第二步：递归处理子问题
		Msort(a, t, low, mid);
		Msort(a, t, mid + 1, high);
		 //第三步：子问题合并
		Merge(t, b, low, high);
	}
}
void Merge(int a[], int b[], int low, int high) {
	int mid = (low + high) >> 1;
	int i = low, j = mid + 1,k=low;
	while (i <= mid && j <= high) {
		b[k++] = (a[i] <= a[j] ? a[i++] : a[j++
    上一篇：广大菜鸟的博客：学习如何通过监控按键中途退出python程序
    下一篇：没有了