洛谷 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;

}