快速排序（递归和非递归两种方法实现）

快速排序：

1.首先找一个基准点（一般选取最左边第一个）

2.先从后往前遍历，找到第一个小于基准值的元素；

3.再从前往后，找到第一个大于基准值的元素；

4.将这两个元素两两交换

5.当i与j相遇时，说明找到了排序后当前这个基准值的正确位置，将基准点进行归位；

6.开始新的一轮，以上一轮的基准点为中轴，分成左边区域和右边区域，分别选取一个新的基准点对新的基准点进行归位即可。

非递归（利用队列实现）

//进行分区，也就是找到基准点排序后的正确位置
int pation(vector<int>& nums, int left, int right)
{int tmp = nums[left];//先将基准点保存起来//循环结束条件：i和j相遇while (left < right){//从后往前找，找到第一个小于基准点的下标while (left<right && nums[right]>tmp)--right;//将当前这个值赋给左下标的元素if (left < right) nums[left] = nums[right];//从前往后，找到第一个大于基准值的下标while (left < right && nums[left] <= tmp)++left;将当前这个值赋给右下标的元素if (left < right) nums[right] = nums[left];}//此时left和right就是基准值的正确位置//将基准值归位nums[left] = tmp;return left;
}
//非递归
void quickSort(vector<int>& nums, int left, int right)
{queue<int> qu;//通过队列实现非递归，如果用栈就是先放右边的值再放左边的值qu.push(left);qu.push(right);while(!qu.empty()){left = qu.front(); qu.pop();right = qu.front(); qu.pop();//分区int pos = pation(nums, left, right);//对左边序列进行排序if (left < pos - 1){qu.push(left);qu.push(pos - 1);}//对右边序列进行排序if (right > pos + 1){qu.push(pos + 1);qu.push(right);}}
}
int main()
{cout << "请输入数组大小：" << endl;int n;cin >> n;vector<int> nums(n);for (int i = 0; i < n; i++){cin >> nums[i];}quickSort(nums, 0, n - 1);cout << "排序后的数组：" << endl;for (auto& i:nums){cout << i << " ";}cout << endl;return 0;
}

递归：

void dfs(vector<int>& nums, int left, int right)
{//左右边界相遇时，直接return结束if (left >= right) return;int key = nums[left];//保存基准值int i = left, j = right;while (i < j){//从后往前找第一个小于基准值的元素while (nums[j]>=nums[left] &&i<j){j--;}//从前往后找第一个大于基准值的元素while (nums[i] <= nums[left] && i<j){i++;}//左右边界没有相遇，将这两个值两两交换if (i < j){swap(nums[j], nums[i]);}}//此时循环结束，i或j下标就代表基准值的正确下标位置nums[left] = nums[i];nums[i] = key;//递归左边区域dfs(nums, left, i - 1);//递归右边区域dfs(nums, i + 1, right);
}

 注意：

快速排序的时间复杂度通常情况下是O(nlogn)

但在特殊情况下，比如选取的这个基准点刚好是最大值或是最小值时，对n个元素排序，需要遍历n次，此时时间复杂度为O(n*n);