2009年11月30日 星期一

快速排序

//---------------------------------------------------------------------------
#define  SWAP(x,y) {int t; t = x; x = y; y = t;}
//---------------------------------------------------------------------------
#define  LEFT      'L'
#define  RIGHT     'R'
//---------------------------------------------------------------------------
int      g_icount = 1;
//---------------------------------------------------------------------------
void quickSort(char type, int preindex, int list[], int left, int right)
{
    int i     = left;
    int j     = right;
    int pivot = left;
    int max   = right;
    int min   = left;
   
    //current index
    int index = g_icount;
   
    //debug
    printf("(%02d) %02d %c  ", g_icount++, preindex, type);
   
    for(int i = left; i <= right; i++)
        printf("%02d ", list[i]);
    printf("\n");
   
    if(left >= right) return;
   
    while(i < j)
    {
        while(list[i] <= list[pivot] && i < max) i++;
       
        while(list[j] > list[pivot] && j > min) j--;
       
        if(i < j)
        {
            //i,j change
            SWAP(list[i], list[j]);
        }           
    }

    //pivot, j change
    SWAP(list[j], list[pivot]);
   
    quickSort(LEFT,  index, list, left, j-1);
    quickSort(RIGHT, index, list, j+1, right);
}

沒有留言:

張貼留言