快速排序

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

以下是本部分正文：

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

快速排序 不太好记住

算法思想

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); }