Anonymous
Anonymous asked in 電腦與網際網路程式設計 · 1 decade ago

c++演算法名稱快速排序

void quick_sort(int*A,int left,int right)

{

int low,upper,point;

if(left<right){

point=A[(left+right)/2];

low=left-1;

upper=right+1;

while(1){

while(A[++low]<point); //向右找

while(A[--upper]>point);//向左找

if(low>=upper)

break;

swap(A[low],A[upper]); <<這行有錯在哪 可以幫我訂正嗎>>

}

point=A[left];

A[left]=A[upper];

A[upper]=point;

}

quick_sort(A, left, upper-1);//對左邊進行遞迴

quick_sort(A, upper+1, right);//對右邊進行遞迴

}}

1 Answer

Rating
  • Thomas
    Lv 6
    1 decade ago
    Favorite Answer

    #include <stdio.h>

    #include <stdlib.h>

    void MySwap(int *a, int *b)

    {

    int temp;

    temp = *a;

    *a = *b;

    *b = temp;

    }

    void quick_sort(int A[],int left,int right)

    {

    int low,upper,point;

    if(left<right)

    {

    point=A[(left+right)/2];

    //將選的pivot(point變數)放在最左

    MySwap(&A[(left+right)/2],&A[left]);//@@@

    //low=left-1;要partition的少了A[left],就是pivot

    low=left;//@@@

    upper=right+1;

    while(1)

    {

    while(A[++low]<point); //向右找

    while(A[--upper]>point);//向左找

    if(low>=upper) break;

    MySwap(&A[low],&A[upper]);

    }

    //point=A[left];

    //A[left]=A[upper];

    //A[upper]=point;

    MySwap(&A[left],&A[upper]);//@@@把pivot放到正確位置

    //}

    quick_sort(A, left, upper-1);//對左邊進行遞迴

    quick_sort(A, upper+1, right);//對右邊進行遞迴

    }

    }

    int main()

    {

    int i;

    int a[20]={ 7, 8,12, 6, 7, 2, 1,19,55,77,

    33,22,11, 1,66,99,88, 6,22,75};

    quick_sort(a,0,19);

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

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

    printf("\n");

    system("pause");

    return 0;

    }

Still have questions? Get your answers by asking now.