3月 192013
 

Your ads will be inserted here by

Easy AdSense.

Please go to the plugin admin page to
Paste your ad code OR
Suppress this ad slot.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int Datatype;
int random(int i, int j)
{
    return i + rand() % (j-i+1);
}

int randomPartition(Datatype A[], int low, int high)
{
    int i = random(low,high);
    int temp;
    temp = A[high];
    A[high] = A[i];
    A[i] = temp;
    return  partition(A, low, high);
}
int partition(Datatype A[], int low, int high)
{
    int i=low,
        j=high;
    Datatype pivot = A[low];
    while(i < j)
    {
        while(i<j&&A[j] >= pivot) j--;
        if(i<j) A[i++] = A[j];
        while(i<j&&A[i] <= pivot) i++;
        if(i<j) A[j--] = A[i];
    }
    A[i] = pivot;
    return i;
}

void quicksort(Datatype A[], int low, int high)
{
    int divide;
    if(low<high)
    {
        divide = randomPartition(A,low,high);
        //divide = partition(A,low,high);
        quicksort(A, low, divide);
        quicksort(A, divide+1, high);
    }
}

int main()
{
    int i;
    Datatype A[10] ={2,4,6,1,7,3,9,1,90,23};
    quicksort(A, 0, sizeof(A)/sizeof(Datatype));
    for(i=0;i<(sizeof(A)/sizeof(Datatype));i++)
    {
        printf("%d ",A[i]);
    }
    printf("\n");
    return 0;
}

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)