本文介绍: 【排序算法】——快速排序
先取一个中间值，将该值临时保存，将两个指针指向最左边元素和最右边元素。左右指针指向元素依次和中间值比较，判断左指针指向元素是否小于中间值，是，则左指针右移；否，则左指针指向元素覆盖右指针指向元素，然后判断右指针元素是否大于中间值，是，则右指针左移；否，则右指针指向元素覆盖左指针指向元素。两边指针依次与中间值判断，相向而行，直到两个指针指向同一个位置，把中间值放回到该位置。此时，数据分成左右两组，左边数据小于中间值，右边数据大于中间值（左边的最大的那个要小于右边的最小的那个），然后无限分下去，直到不可拆分为止（递归）
66 43 89 98 12 18 15 23 33 50
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
left right
//假设a[left]是中间数据，临时保存，然后判断大小，循环挪动L和R并覆盖
//由于初始中间值取左指针指向元素，则先由右指针指向元素比较，50<66，则覆盖
50 43 89 98 12 18 15 23 33 50
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
L R
//轮到左指针指向元素判断，43<66，则左指针右移，89>66，则元素覆盖到右指针位置
50 43 89 98 12 18 15 23 33 89
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
L R
//轮到右指针指向元素判断，89>66，则右指针左移，33<66，则元素覆盖到左指针位置
50 43 33 98 12 18 15 23 33 89
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
L R
//轮到左指针指向元素判断，33<66，则左指针右移，98>66，则元素覆盖到右指针位置
50 43 33 98 12 18 15 23 98 89
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
L R
//轮到右指针指向元素判断，98>66，则右指针左移，23<66，则元素覆盖到左指针位置
50 43 33 23 12 18 15 23 98 89
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
L R
//轮到左指针指向元素判断，23<66，则左指针右移，12<66，则元素覆盖到右指针位置
50 43 33 23 12 18 15 12 98 89
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
L R
//轮到右指针指向元素判断，12<66，则元素覆盖到左指针位置
50 43 33 23 12 18 15 12 98 89
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
L R
//轮到左指针指向元素判断，12<66,18<66,15<66,左指针右移到左右指针指向同一位置后中间值覆盖该位置元素
50 43 33 23 12 18 15 66 98 89
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
LR
//此时以左右指针重合处为分界点，将已有元素分为两组，两组继续上述排序，然后递归分组直到无法分组为止
//left到L-1为一组，R+1到right为一组
50 43 33 23 12 18 15 66 98 89
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
left L-1 R+1 right
代码：
//快速排序
void quickSort(int* a, int left, int right){
//0或者5 递归结束
if (left >= right) return;
//1 先假设a[left]是中间数据,并临时保存
int temp = a[left];
int L = left;
int R = right;
//2 循环挪动l和r并覆盖 循环结束后 L==R
while (L < R){
//2.1 先挪右边的
while (L<R && a[R]>temp) R--;
a[L] = a[R];
//2.2 再挪左边的
while (L<R && a[L]<temp) L++;
a[R] = a[L];
}
//3 用中间数据覆盖回来
a[R] = temp;//a[L]=temp;
printf("mid:%dn", temp);
//4 递归分组
quickSort(a, left, L-1); //左边那一组继续递归
quickSort(a, R+1, right); //右边那一组继续递归
}原文地址:https://blog.csdn.net/qq_59470001/article/details/135329493
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_52402.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
