快速排序

阿秀自己刷过的算法部分经过整理后是按照不同基础、不同人群分类的，如果你不知道自己该看哪个部分的算法题，可以先看一下这里，戳我直达。

以下是本部分正文：

这里简单为大家讲解一下一些算法基础知识与十大排序，在面试考察中十大排序出现的频率是非常高的，特别是冒泡排序、快速排序、归并排序等，具体可点击这里

快速排序 不太好记住

算法思想

1、选取第一个数为基准

2、将比基准小的数交换到前面，比基准大的数交换到后面

3、对左右区间重复第二步，直到各区间只有一个数

我们从数组中选择一个元素，我们把这个元素称之为中轴元素吧，然后把数组中所有小于中轴元素的元素放在其左边，所有大于或等于中轴元素的元素放在其右边，显然，此时中轴元素所处的位置的是有序的。也就是说，我们无需再移动中轴元素的位置。

从中轴元素那里开始把大的数组切割成两个小的数组(两个数组都不包含中轴元素)，接着我们通过递归的方式，让中轴元素左边的数组和右边的数组也重复同样的操作，直到数组的大小为1，此时每个元素都处于有序的位置。

为方便理解我还准备了动图：

void quickSort(vector<int>& a, int low, int high) {
	if (low >= high)		// 结束标志
		return;
	int first = low;		// 低位下标
	int last = high;		// 高位下标
	int key = a[first];		// 设第一个为基准

	while (first < last)
	{
		// 从后往前走，将比第一个小的移到前面
		while (first < last && a[last] > key)
			last--;
		if (first < last)
			a[first++] = a[last];

		//从前往后走， 将比第一个大的移到后面
		while (first < last && a[first] <= key)
			first++;
		if (first < last)
			a[last--] = a[first];
	}

	a[first] = key;
	// 前半递归
	quickSort(a, low, first - 1);
	// 后半递归
	quickSort(a, first + 1, high);
	
}


quickSort(A, 0,A.size()-1);
	for (auto a : A) {
		cout << a << endl;
	}

自己复写一遍，加强了理解

void quickSort(vector<int>&numbers, int low, int high) {
	//  numbers = {10,8,4,6,9,10,123,6,2,14,3,8,5};
	if (low >= high) return;
	int first = low, last = high, key = numbers[low];
	cout << low << " " << high << " "<<key << endl;
	for (int i = 0; i < numbers.size(); ++i) {
		cout << numbers[i] << " ";
	}
	cout << endl;

	while (first < last) {
		//从后往前找比他小的放前面,从前往后找比他大的放在后面，
		//以第一个数为基准，必须先从后往前走，再从前往后走
	
		while (first < last && numbers[last] >= key)
			last--;
		if (first < last) numbers[first++] = numbers[last];


		while (first < last && numbers[first] <= key)
			first++;
		if (first < last) numbers[last--] = numbers[first];

	}
	numbers[first] = key;

	cout << "the index " << first << "  value " << key << endl;

	quickSort(numbers, low, first - 1);
	quickSort(numbers, first + 1, high);
}

再一次复写

void quickSort2(vector<int>& nums, int begin, int end) {
	if (begin >= end) return;//4,10,3,0,5,1,2
	int first = begin, last = end;
	int key = nums[first];
	while (first < last) {
		while (first < last && nums[last] >= key)
			last--;
		if (first < last)
			nums[first++] = nums[last];

		while (first < last && nums[first] <= key)
			first++;
		if (first < last)
			nums[last--] = nums[first];
	}

	nums[first] = key;
	cout << begin << " " << end << " " << key << endl;
	for (auto a : nums)
		cout << a << " ";
	cout << endl << endl;


	quickSort2(nums, begin, first-1);
	quickSort2(nums, first+1, end);

}

再次复写

void print(vector<int>& nums) {
	for (auto a : nums)
		cout << a << " ";
	cout << endl;

}
void quickSort(vector<int>& nums, int begin, int end) {
	if (begin >= end) return;
	int low = begin, high = end, key = nums[begin];
	while (low < high) {
		while (low < high && nums[high] >= key) {
			high--;

		}
		if (low < high)  nums[low++] = nums[high];

		while (low < high && nums[low] <= key) {
			low++;

		}
		if (low < high)  nums[high--] = nums[low];
	}

	nums[low] = key;
	print(nums);

	quickSort(nums, begin, low - 1);
	quickSort(nums, low + 1, end);

}