快速排序C++

思路：复杂度：O(nlogn) 稳定排序

1、设置左边第一个元素为基准元素

2、设置左指针，设置右指针

3、只要左指针小于右指针，就进入while循环

4、从右指针开始将右指针所指的元素与基准元素比较

        若右指针大于基准元素，则右指针左移；

        反之右指针所指的元素填入基准的位置，且右指针所指的位置成为新的基准;

5、接着上步，从左指针开始将左指针所指的元素与新的基准元素比较

        若左指针所指的元素小于基准元素，则左指针右移；

        反之左指针所指元素填入基准的位置，且左指针的位置成为新的基准；

6、while循环结束后，将最终的基准元素放入左右指针重叠的位置，此时基准元素左边为小于基准元素的序列；基准右边为大于基准元素的序列；

7、在继续分别对基准元素的左右序列进行上述 *** 作，用递归实现。

代码：

#include 
#include 
#include 
using namespace std;
void mysort(vector& nums, int start, int end)
{
	if (start >= end)
		return;
	int left = start;//设置左指针
	int right = end;//设置右指针
	int temp = nums[left];//选取的基准元素
	while (left < right)
	{
		//从右指针开始将指针所指的元素和基准比较
		while (lefttemp)
			right--;//若右指针所指的元素比基准大，则将右指针向左移动
		nums[left] = nums[right];//若右指针所指的元素比基准小，就将右指针的元素填入基准的位置中，且右指针的位置成为新的基准
		//从左指针开始将指针所指的元素和基准比较
		while (left < right && nums[left] < temp)
			left++;//若左指针指向的元素小于基准元素，左指针右移
		nums[right] = nums[left];//若左指针指向的元素大于基准元素，左指向的元素填入坑中，且左指针成为新基准
	}
	nums[left] = temp;//将最终的基准放回到指针重叠的位置。
	//此时基准元素的左边为小于基准元素的序列，右边为大于基准元素的序列
	mysort(nums, start, left-1);//对于基准元素左边的序列进行上述排序
	mysort(nums, left + 1, end);//对于基准元素右边的序列进行上述排序
}
int main()
{
	vector nums = { 7,5,8,6,4,3 };
	mysort(nums, 0, nums.size() - 1);
	for (int num : nums)
		cout << num;
	cout << endl;
	system("pause");
	return 0;
}

运算结果：