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);//對右邊進行遞迴

}}

Rating
• Thomas
Lv 6

#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;

}