快速排序算法

快速排序

先这这组数中随便找一个数作为基准数，

先从左往右找，找一个大于基准数的数

在从右往左找，找一个小于基准数的数

然后交换他们

举例：

以i和j遍历数组

i从前往后

j从后往前

j先动

6、1、2、7、9、3、4、5、10、8

以6为基准数

1：7和5交换

6、1、2、5、9、3、4、7、10、8

2：9和4交换

6、1、2、5、4、3、9、7、10、8

3：i==j i与j相遇 6和3交换 基准数和数组的i位交换

3、1、2、5、4、6、9、7、10、8

比6小的数都在6的左边

比6大的数都在6的右边

第二轮：

以3为基准数 处理6的左边

1：3和2交换

2、1、3、5、4

左边以2为基准数处理：

1、2

右边以5为基准数处理：

4、5

以9为基准数 处理6的左边

9、7、10、8

1：8、7、9、10

左边以8为基准数处理

7、8

最后

1、2、3、4、5、6、7、8、9、10

#include 
int a[200],n;
void quicksort(int left,int right){
    int i,j,t,temp;
    if(left>right)
        return;
    temp=a[left];//temp中存放基准数
    i=left;
    j=right;
    while (i!=j){
        //先从右往左找
        while (a[j]>temp && i<j) j--;
        //再从左往右找
        while (a[i]<=temp && i<j) i++;
        //交换两个数的位置
        if(i<j){
            t=a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }
    a[left]=a[i];
    a[i]=temp;

    quicksort(left,i-1);//处理基准数左边的
    quicksort(i+1,right);//处理基准数右边的
}
int main(){
    int i,j,t;
    scanf("%d",&n);
    for(i=0;i<n;i++) {
        scanf("%d", &a[i]);
    }
    quicksort(0,n-1);

    for(i=0;i<n;i++){
        printf("%d ",a[i]);
    }
        return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

改变12/14行的大于小于号实现从大到小排序

//先从右往左找
while (a[j]<temp && i<j) j--;
//再从左往右找
while (a[i]>=temp && i<j) i++;
//交换两个数的位置
if(i<j){
    t=a[i];
    a[i]=a[j];
    a[j]=t;
}
1
2
3
4
5
6
7
8
9
10