快速排序(分治)-创新互联

日常分享:岁聿云暮,日月其除,前路未远,步履不停。

为昭阳等地区用户提供了全套网页设计制作服务,及昭阳网站建设行业解决方案。主营业务为成都网站设计、网站建设、昭阳网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!

算法基础—快速排序
  • 前言
  • 一、快速排序的时间复杂度
  • 二、快速排序实现
  • 总结
  • 三、代码


前言

快速排序就是先找一个关键字,然后通过一趟排序,把大于关键字的位于一侧,小于关键字的位于一侧,然后对两侧在进行排序。

一、快速排序的时间复杂度

快速排序最优情况下时间复杂度为:O( nlgn )
最优情况下空间复杂度为: O(logn)
怎么去计算这个复杂度在这里就不多说了。

二、快速排序实现

1.首先我们应该输入数组的值

const int N = 1e6 + 10;//1e6 就是1*10的6次方

int q[N];

int n;

	cin >>n;

	for (int i = 0; i< n; i++)
	{cin >>q[i];
	}

也可以用scanf,scanf和printf是要比cin,cout快的,但是不要忘记用&符号。

2.确定函数的分界点
确定分界点之前,不要忘记考虑一种情况,左边界==有边界的时候,是不是应该直接退出函数??

if (l >= r)
	{return;
	}

左边界可不能>=有边界。

int x = q[l + r >>1];

这个不加括号是因为➕的优先级要比>>的优先级要高。
在这里我们以中间值为分界点,也可以选取q[0]当分解点。当然,最好选取中间值,当你选两边的值的时候,再做一些题的时候,可能会出现超时的情况。
在这里插入图片描述
这样确定了分界点之后,就可以进行下一步了。

3.在这里有两个指针,i和j,q[i]小于x,就++,直到出现大于x的情况,q[j]大于x,j就–,直到遇到小于x的情况。
代码实现如下:

int x = q[l + r >>1];
	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]);
		}
	}

这里为什么要用l-1和r+1呢?因为这里我用的是do—while循环,先执行的i++,在执行的判断条件,大家也可以改成while循环。

在这里插入图片描述

可以把数组以中间值,分开,然后每个指针进行移动+判断,直到两个指针都不满足循环条件,进入交换。
在这里插入图片描述

就是这样交换的,如果你的学的编程语言没有swap这样的函数,那么我们也可以自己实现一下

if (i< j)
{int tmp = q[i];
	q[i] = q[j];
	q[j] = tmp;
}

这个代码够简单了,在这里不多说了。
4.最重要的一点,边界问题

代码如下(示例):

QuickSort(q, l, j);
	QuickSort(q, j + 1, r);

也可以用其他方法,在这里就不多介绍了。

总结

为什么要学快速排序呢,明明有库函数,如C++(sort),C语言(qsort)等等,
学快排,学的是思想,正如一句话:算法学的好,工作不愁找。哈哈

三、代码
#includeusing namespace std;

const int N = 1e6 + 10;

int q[N];

int n;

void QuickSort(int q[], int l, int r)
{if (l >= r)
	{return;
	}

	int x = q[l + r >>1];
	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]);
		//}

		if (i< j)
		{	int tmp = q[i];
			q[i] = q[j];
			q[j] = tmp;
		}
	}

	QuickSort(q, l, j);
	QuickSort(q, j + 1, r);

}

int main()
{cin >>n;

	for (int i = 0; i< n; i++)
	{cin >>q[i];
	}

	QuickSort(q, 0, n - 1);

	for (int i = 0; i< n; i++)
	{cout<< q[i]<< ' ';
	}

	return 0;
}

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


本文题目:快速排序(分治)-创新互联
当前网址:http://myzitong.com/article/cogodo.html