还没三数取中，取到的mid是最小的话还是会退化到冒泡n平方

#include #include using namespace std; int a[100010]; //交换元素位置 void swap(int* a, int* b) { int temp; temp = *a; *a = *b; *b = temp; } void quickSort(int* arr, int low, int high) { //若长度已经不符合要求,直接返回 if (low >= high) { return; } int left = low; int right = high; //选取中间为基准,注意是取中间的值,而不是下标,因为下标可能在后续交换中会改变 //比如left走到了mid这里,而right停在了mid右边,这时会去交换,arr[mid]就变了 int mid = arr[(low + high) >> 1]; while (left <= right) { //注意是小于,如果是小于等于的话,常数列就会一直left移动,而right不移动,沦为n平方 while (arr[left] < mid) { left++; } //同样注意是大于 while (arr[right] > mid) { right--; } //这里要注意是小于或等于,以便于left和right直接跳到枢纽点的左右 if (left <= right) { swap(&arr[left], &arr[right]); left++; right--; } } //递归调用 //right走到了区间一的尾部 quickSort(arr,low, right); //left走到了区间二的头部 quickSort(arr, left, high); } int main() { int n, i; cin >> n; for (i = 1; i <= n; i++) { cin >> a[i]; } quickSort(a,1,n); for (i = 1; i <= n; i++) { cout << a[i] << " "; } cout << endl; }

此处取到的mid是60

• 然后left发现不满足条件,86>mid(60)，left还在86
  • right满足条件,right去--，走到了15那里停下来
• 然后left不满足<=right,直接就要开始继续递归了
  • 递归的区间①是: [42,15] (都小于等于60)
  • 区间②是 : [86,68] (都大于等于60)

while (arr[left] < mid) { left++; } //同样注意是大于 while (arr[right] > mid) { right--; } //这里要注意是小于或等于,以便于left和right直接跳到枢纽点的左右 if (left <= right) { swap(&arr[left], &arr[right]); left++; right--; } //递归调用 //right走到了区间一的尾部 quickSort(arr,low, right); //left走到了区间二的头部 quickSort(arr, left, high);

自行用一定数据量测试的话，时间效率上差距还算不上很大的。

#include #include #include"RcdSqList.h" using namespace std; //int a[100010]; //交换元素位置 void swap(int* a, int* b) { int temp; temp = *a; *a = *b; *b = temp; } //三数取中 int getmid(int* array, int left, int right) { int mid = left + ((right - left) >> 1); if (array[left] <= array[right]) { if (array[mid] < array[left]) return left; else if (array[mid] > array[right]) return right; else return mid; } else { if (array[mid] < array[right]) return right; else if (array[mid] > array[left]) return left; else return mid; } } void quickSort(int* arr, int low, int high) { //若长度已经不符合要求,直接返回 if (low >= high) { return; } int left = low; int right = high; //选取中间为基准,注意是取中间的值,而不是下标,因为下标可能在后续交换中会改变 //比如left走到了mid这里,而right停在了mid右边,这时会去交换,arr[mid]就变了 //调用三数取中,得到中间数 int mid = arr[getmid(arr, low, high)]; while (left <= right) { //注意是小于,如果是小于等于的话,常数列就会一直left移动,而right不移动,沦为n平方 while (arr[left] < mid) { left++; } //同样注意是大于 while (arr[right] > mid) { right--; } //这里要注意是小于或等于,以便于left和right直接跳到枢纽点的左右 if (left <= right) { swap(&arr[left], &arr[right]); left++; right--; } } //递归调用 //right走到了区间一的尾部 quickSort(arr, low, right); //left走到了区间二的头部 quickSort(arr, left, high); } int main() { int n, i; /*cin >> n; */ /*for (i = 1; i <= n; i++) { cin >> a[i]; }*/ int a[100] = { 0,42 ,90,30,86,42,15,57,20 }; quickSort(a, 1, 8); for (i = 1; i <= 8; i++) { cout << a[i] << " "; } cout << endl; }

最后是下载了测试点，然后看了博客，去找超时的原因，其实是完全有序
然后拿标准答案debug一下，终于发现了区别，就是常数列的时候他两个都移动，我只是一个移动，就退化成n平方了

看黑马视频得出的感悟....
这个问题很严重，会变成n平方
如果把基准放最左边，而本身有序的话就会超时了

• 注意这里的取中间值不是说取区间中间的值，而是大小在首尾和区间中间数三个值排列居中的那个
  • 如果取的是区间中间的值，并不能解决完全有序的问题，比如 5 4 1 2 3 ，取mid等于1，又是取到了最小的情况，最后mid放到正确的位置(即第一个位置)，递归他的左右，并没有起到把原区间化成两半的效果，只是得到了右边那一段，相当与只是减少了一个元素(类似冒泡的把一个元素放到正确的位置而已)

如果我们不在交换完做移动的话，那>就得改成>=，这样才会移动，但就变成单指针移动了，还是退化成n平方了

https://www.luogu.com.cn/problem/P1177(依旧是模板题)

#include #include using namespace std; int a[100010]; //交换元素位置 void swap(int* a, int* b) { int temp; temp = *a; *a = *b; *b = temp; } //三数取中 int getmid(int* array, int left, int right) { int mid = left + ((right - left) >> 1); if (array[left] <= array[right]) { if (array[mid] < array[left]) return left; else if (array[mid] > array[right]) return right; else return mid; } else { if (array[mid] < array[right]) return right; else if (array[mid] > array[left]) return left; else return mid; } } void quickSort_2(int rcd[], int low, int high) { if (low >= high) { return; } //调用三数取中,获取枢纽位置 int pivot=getmid(rcd,low,high); //把枢纽值放到low位置(交换) swap(&rcd[low],&rcd[pivot]); //枢纽值就等于rcd[low] int pivotVal = rcd[low]; //i用来遍历一趟区间 int left, right, i; //直接从枢纽的下一位开始遍历区间 left = low, right = high, i = low + 1; //遍历整个区间 while (i <= right) { //若小于枢纽值 if (rcd[i] < pivotVal) { //得放到前边,跟left交换 swap(&rcd[i], &rcd[left]); //交换完,i换来了一个i前边的值,肯定比较过了,所以i++ i++; //left换来了一个i原来位置的值,也比较过了,所以left++ left++; } //若大于枢纽值 else if(rcd[i]>pivotVal) { //得放到后边,跟right交换 swap(&rcd[i], &rcd[right]); //right换来了一个i原来位置的值,也比较过了,所以right++ right--; //i不动,因为换过来一个i后边的新的值,还没比较过} //等于的情况 else { i++; } } quickSort_2(rcd, low, left - 1); quickSort_2(rcd, right + 1, high); } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } quickSort_2(a,0, n - 1); for (int i = 0; i < n; i++) { i == n - 1 ? printf("%d", a[i]) : printf("%d ", a[i]); } }

这里我们先默认枢轴就是最左边的元素就好了，方便理解（实际情况再按上边代码取中后跟最左边交换即可）

• 当 rcd[i]大于枢纽值时，比如图中的90
• 当rcd[i]小于枢纽值时，比如图中的20
• 当rcd[i]等于枢纽值时，比如图中的42

具体看图中的文字说明

• 减少了对重复元素的比较操作，因为重复元素在一次排序中就已经作为单独一部分排好了，之后只需要对不等于该重复元素的其他元素进行排序。

• 到了快排这里，其实已经涉及到一些递归的知识，跟递归相关的其实还有“折半查找”、“归并排序”等，本专栏也还还会持续更新相关的知识，欢迎关注一起学习！

推荐阅读

• 

  参茶泡柠檬可以天天喝吗
• 

  广东灯饰批发市场 「中山古镇灯具厂家拿货」
• 

  硬质合金网站硬质合金网纹摩擦表面如何处理
• 

  十五夜望月中心句 十五夜望月古诗的中心句
• 

  考评语大全来了 年终考核评语
• 

  鹿角菜的营养价值及功效 鹿角菜的营养价值
• 

  汽车铅酸蓄电池寿命在2年左右 汽车蓄电池能用多久
• 

  怎样辨别自己是不是有洁癖？洁癖有哪些症状表现？
• 

  为什么网页无法看视频，为什么打开网页看不了视频
• 

  360安全卫士可以进行木马查杀 360安全卫士查杀木马的具体方法介绍
• 

  谁能全面的回答一下,乌托邦是什么？
• 

  军事博物馆门票网上预约 军事博物馆预约门票官网电话多少
• 

  浙江杭州 浙江乾祥
• 

  iOS冒险游戏，求iphone文字冒险类游戏
• 

  苦瓜怎么做好吃又减肥瘦身？ 苦瓜怎么做才能减肥
• 

  酥肉几分钟可以炸熟 炸好的酥肉可以留多久
• 

  我言秋日胜春朝的意思
• 

  三阴交拔罐能调理哪些疾病
• 

  后退的反义词和近义词 后退的反义词是什么词
• 

  晶体熔化时吸热为什么温度不变

• 一个选择排序算法
• 排序（归并排序）
• 【图解】9张图彻底搞懂堆排序
• neo4j|neo4j cql语句 快速查询手册
• 通过复盘快速成长（附模板）
• jar|springboot项目打成jar包和war包，并部署（快速打包部署）
• 快速阅读作业【2/21】《阅读（革命性新定义》）
• Spring注解05|Spring注解05 @Import 给容器快速导入一个组件
• vue|vue 上移 下移 删除 排序
• 必须掌握的八种基本排序算法