快速排序（分治）-创新互联

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

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

算法基础—快速排序

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

---

前言

---

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

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

快速排序最优情况下时间复杂度为：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://6mz.cn/article/cogodo.html