int Partition(int a[], int head, int rear){
int temp = -1;
int key = a[head]; //哨兵
int i = head;
int j = rear;
while (TRUE) {
while (a[j] > key) {
j--;
}
while (a[i] < key) {
i++;
}
if (i < j) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
} else {
return j;
}
}
}
void QuickSort(int *a, int head, int rear){
int mid = -1;
if(head < rear){
mid = Partition(a,head,rear);
QuickSort(a,head,mid);
QuickSort(a,mid+1,rear);
}
}
======================================================================
#include
#include
void swap(int *a, int *b){
int c;
c = *a;
*a = *b;
*b = c;
}
int partion(int A[],int q, int r){
int x = A[q];
int i = q;
int j = r;
while(1){
while (A[j]>x)
j--;
while(A[i]
i++;
if(i
swap(A+i,A+j);
else
return j;
}
}
void quicksort(int A[], int q, int r){
int j;
if(q
j = partion(A,q,r);
quicksort(A,q,j);
quicksort(A,j+1,r);
}
}
void array_printf(int A[], int start, int end){
int i = start;
while(i <= end){
printf("%d ",A[i]);
i++;
}
printf("\n");
}
int main(){
int n;
scanf("%d",&n);
int *ptr;
ptr = (void*)calloc(sizeof(int),n);
int i = 0;
while(i
scanf("%d",ptr+i);
i++;
}
quicksort(ptr,0,n-1);
array_printf(ptr,0,n-1);
return 0;
}
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#include
#include
int qkSort(int R[],int s, int t)
{
int i,j;
int temp;
i = s;
j = t;
temp = R[s];
do
{
while((R[j]>=temp)&&(i j--;
if(i {
R[i] = R[j];
i++;
}
while((R[i]<=temp)&&(i i++;
if(i {
R[j]=R[i];
j--;
}
}while((i < j));
R[i] = temp;
return i;
}
void macroQK(int R[], int s ,int t)
{
int i;
if(s {
i = qkSort(R,s,t);
macroQK(R,s,i-1);
macroQK(R,i+1,t);
}
}
int main (){
struct timeval t1,t2;
struct timezone tz;
gettimeofday(&t1,&tz);
int s, t, i, k;
int R[]={36,73,65,97,13,27,36,29};
s = 0;
t = sizeof(R)/sizeof(int)-1;
printf("R[]=\n");
for(i = 0; i <= t ; i++)
printf("%d ",R[i]);
printf("\nAfter sort:\n");
macroQK(R, s, t);
for(i = 0; i <= t ; i++)
printf("%d ",R[i]);
printf("\n");
gettimeofday(&t2,&tz);
printf("time usage:%d ms\n",(t2.tv_usec-t1.tv_usec));
}
阅读(845) | 评论(0) | 转发(0) |
