题解:
quick sort三部曲
step1: 初始化 i = l - 1, j = r + 1
, 参照值 x = a[(l+r)>>1]
step2: 双指针从两侧找, i
指针找第一个不满足 a[i] < x
的位置, j
指针找第一个不满足 a[j] > x
的位置,
此时若满足 i < j
,则交换 a[i]
和 a[j]
step3: 递归调用前后两部分,记得下标:当参照值 x
可以取到 l
的时候,要以 j
为临界点调用;当 x
可以取到 r
的时候,要以 i
作为临界点区分调用
c语言
#include<stdlib.h>
#include<stdio.h>
#define MAX_LEN 100010
int a[MAX_LEN];
int n;
void quick_sort(int a[], int l, int r){
if(l >= r) return ;
int i = l - 1, j = r + 1, x = a[(l + r) >> 1];
while(i < j){
do i++; while(a[i] < x);
do j--; while(a[j] > x);
if(i < j){
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
quick_sort(a, l, j);
quick_sort(a, j + 1, r);
}
int main(){
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
quick_sort(a, 0, n - 1);
for(int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}
楼主,我这个渣渣来提问一下,quick_sort(a, l, j);和 quick_sort(a, j + 1, r);没有看懂,当参照值 x 可以取到 l 的时候,要以 j 为临界点调用;当 x 可以取到 r 的时候,要以 i 作为临界点区分调用,我可能是函数的调用不懂吧,主函数里面的我也不懂, quick_sort(a, 0, n - 1);希望楼主解答一下,感谢大佬