ACM记录之快速排序

递归法快速排序(Quicksort) ，时间复杂度 O (nlogn) ,以下为C语言的一种代码：

#include <stdio.h>
#include <conio.h>

/*==============================================================*/

int qsort(int s[], int l, int r)
{
     int i,j,x;
     i=l;
     j=r;
     x=s[l];
     if (i<j)
     {
             while (i<j)
             {
                   while((i<j)&&(s[j]>=x))
                         j--;
                   if (i<j)
                         s[i++]=s[j];
                   while ((i<j)&&(s[i]<=x))
                         i++;
                   if (i<j)
                         s[j--]=s[i];
             } 
             s[i]=x;
     qsort(s,l,i-1);
     qsort(s,i+1,r);
     }          
     return 0;
}
<!-- wp:more -->
<!--more-->
<!-- /wp:more -->
/*=================================================================*/
int main()
{
    int k,str[100],n;
    printf("input n:\n");
    scanf("%d",&n);
    printf("input data:");
    for(k=1;k<=n;k++)
          scanf("%d",&str[k]);
    qsort(str,1,n);
    printf("\noutput:");
    for(k=1;k<=n;k++)
          printf("%d ",str[k]);
    printf("\n");
   /* system("pause");*/
    getch();
    return 0;
}
       
                        
             

Views: 68