快速排序

浏览数：19 / 时间：2015年06月08日

代码：

#include <stdio.h>
#include <malloc.h>

int T,t,N,i;

#define LOG 1

//调试日志
void Log(int* data,int flag,int i,int j)
{
#ifdef LOG
    if(flag == 1)
    {
        for(int k=0;k<N;k++)
        {
            if(k==i || k==j)
                printf("* ");
            else
                printf("  ");
        }
        printf("\n");    
    }

    for(int k=0;k<N;k++)
    {
        printf("%d ",data[k]);
    }
    printf("\n");    
#endif
}


void quickSort(int* data,int left, int right)
{
    if(left > right)
    {
        return;
    }

    int i,j,temp1,temp2;

    temp1 = data[left];

    i = left;
    j = right;

    while(i!=j)
    {
        while(data[j] >= temp1 && j>i)
            j--;

        while(data[i] <= temp1 && i<j)
            i++;
        
        //i与j交换
        if(i<j)
        {    
            temp2 = data[i];
            data[i] = data[j];
            data[j] = temp2;
            Log(data,1,i,j);
        }
    }
    
    //当i与j相遇，将该值与基准值交换
    data[left] = data[i];
    data[i] = temp1;
    Log(data,1,i,left);

    quickSort(data,left,i-1);
    quickSort(data,i+1,right);
}


/*
*T:testcase number
*N:array size
*data
*/
int main()
{
    //从文件input.txt读取测试数据，并输出到output.txt
#ifdef WIN32
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif

    scanf("%d",&T);
    
    for(t=1;t<=T;t++)
    {
        scanf("%d",&N);
        
        //动态分配内存
        int *data;
        data = (int*)malloc(sizeof(int) * N);
        
        //读取数据
        for(i=0;i<N;i++)
        {
            scanf("%d",&data[i]);
        }
        
        Log(data,0,0,0);

        quickSort(data,0,N-1);
        
        //打印程序运行结果
        for(int k=0;k<N;k++)
        {
            printf("%d ",data[k]);
        }        

        //释放动态分配的内存
        free(data);
        data = NULL;
    }

    return 0;
}

Input：

1
10
6 1 2 7 9 3 4 5 10 8

Output:

6 1 2 7 9 3 4 5 10 8 
      *       *     
6 1 2 5 9 3 4 7 10 8 
        *   *       
6 1 2 5 4 3 9 7 10 8 
*         *         
3 1 2 5 4 6 9 7 10 8 
*   *               
2 1 3 5 4 6 9 7 10 8 
* *                 
1 2 3 5 4 6 9 7 10 8 
*                   
1 2 3 5 4 6 9 7 10 8 
      * *           
1 2 3 4 5 6 9 7 10 8 
      *             
1 2 3 4 5 6 9 7 10 8 
                * * 
1 2 3 4 5 6 9 7 8 10 
            *   *   
1 2 3 4 5 6 8 7 9 10 
            * *     
1 2 3 4 5 6 7 8 9 10 
            *       
1 2 3 4 5 6 7 8 9 10 
                  * 
1 2 3 4 5 6 7 8 9 10 
1 2 3 4 5 6 7 8 9 10