洛谷 P1177 【模板】快速排序

洛谷 P1177 【模板】快速排序

1.翻书，该题很容易解决，但不算掌握。

2.凭空编写，边界点的取值有些问题，等号去还是不取。

3.想了一个办法，写出一组数据进行手动模拟，弄明白了，程序再开始根据模拟进行编制。

4.很久没写快排了，如果能一次性编写成功，这次可以说快排掌握了。

5.开始动手，。

6.第一次取a[left]为中枢，得分40.

7.第二次取a[(left+right)/2]为中枢，得分60.

8.第三次取a[left],a[right],a[(left+right)/2]中间值为中枢，得分60.

9.本想上归并排序，但难度较大，时间较紧，只能作罢。

10.参考AC代码，进行模拟，发现一个很好的快排代码。

11.对着模拟，进行编码,修改小错误后，提交AC.

附上AC代码，编译环境Dev-C++4.9.9.2

#include <stdio.h>

int a[100000+100];

void quicksort(int left,int right){

    int i=left,j=right,t;

    int mid=a[(left+right)/2];//请注意，在处理的过程中a[(left+right)/2]的值是会变化的

    while(i<=j){//i,j的值是会跳跃的,循环结束时i>j

        while(a[i]<mid)

            i++;

        while(a[j]>mid)

            j--;

        if(i<=j){

            t=a[i];

            a[i]=a[j];

            a[j]=t;

            i++;

            j--;

        }

    }

    if(i<right)

        quicksort(i,right);

    if(left<j)

        quicksort(left,j);

}

int main(){

    int n;

    int i;

    scanf("%d",&n);

    for(i=0;i<n;i++)

        scanf("%d",&a[i]);

    quicksort(0,n-1);

    printf("%d",a[0]);

    for(i=1;i<n;i++)

        printf(" %d",a[i]);

    printf("\n");

    return 0;

}