leetcode刷题

1. 快速排序的思想是：先找一个基准，比如下面的例子中找的基准就是第一个数，然后传入一个数组需要排序部分的头指针和尾指针，实际用的传入下标索引就行。
   然后把这个数组中所有比基准大的放在基准后面，所有比基准小的放在基准前面，这样基准肯定是被放到了该数组中正确的位置，然后开始递归，接着排前面的部分和后面的部分。
2. 具体代码中怎么操作，怎么将小的移动到前面，大的移动到后面呢？
   • 还需要定义两个指针，叫下标也行，然后头尾一起遍历，一个last指针，一个first指针。找到nums[last]
   • 然后找到nums[first]>key的就把现在的值赋给nums[last],找不到就first++.
   • 找到first = last了就说明前后都找完了。然后此时把nums[first] = key,也即是把基准放到最正确的位置。
   • 开始递归，传入[l,first]找前面的，和传入[first+1,r]找后面的。
   • 具体参照以下代码。

#include
#include
using namespace std;
void quick_sort(vector& nums, int l, int r);

int main()
{
	vector a = { 4,2,5,1,7,6,3 };
	quick_sort(a, 0, 7);
	return 0;

}


void quick_sort(vector& nums, int l, int r)
{
	if (l + 1 >= r)
	{
		return;
	}
	int first = l, last = r - 1, key = nums[first];
	while (first < last)
	{
		while (first < last && nums[last] >= key) {
			--last;
		}
		nums[first] = nums[last];
		while (first < last && nums[first] <= key)
		{
			++first;
		}
		nums[last] = nums[first];
	}
	nums[first] = key;
	quick_sort(nums, l, first);
	quick_sort(nums, first + 1, r);
}