快速排序算法C语言实现（源代码）

快速排序算法

快速排序算法在很多的数据结构与算法书中都有讲解，关于它不过多介绍了.

快速排序算法的时间复杂度最坏情况下是O(n^2)也就是每次哨兵几乎都不起作用的情况下,平均时间复杂度是O(nlgn).

 

 
   
    
   #include 
   < 
   stdio.h 
   > 
   
#include 
   < 
   stdlib.h 
   > 
   
#include 
   < 
   time.h 
   > 
   
 
   #define 
    MAX  100 
   
 
   /* 
   
快速排序算法的两个主要步骤，分割（Partition和QuickSort）
 
   */ 
   
 
   int 
    Partition( 
   int 
    A[], 
   int 
    p, 
   int 
    q);
 
   int 
    QuickSort( 
   int 
    A[], 
   int 
    p, 
   int 
    q);
 
   int 
    test();
 
   int 
    main()
{
 test();
  
   return 
     
   0 
   ;
}
 
   /* 
   
一个很简单的测试函数
 
   */ 
   
 
   int 
    test()
{
  
   int 
    a[MAX];
  
   int 
    i;
 srand(( 
   int 
   )time( 
   0 
   ));
  
   for 
   (i  
   = 
     
   0 
   ;i 
   < 
   MAX;i 
   ++ 
   )
 {
  
  a[i]  
   = 
    rand();
 }
  
   for 
   (i  
   = 
     
   0 
   ;i 
   < 
   MAX;i 
   ++ 
   )
  printf( 
   " 
   %d\t 
   " 
   ,a[i]);
 printf( 
   " 
   \n 
   " 
   );
 QuickSort(a, 
   0 
   ,MAX 
   - 
   1 
   );
  
   for 
   (i  
   = 
     
   0 
   ;i 
   < 
   MAX;i 
   ++ 
   )
  printf( 
   " 
   %d\t 
   " 
   ,a[i]);
 printf( 
   " 
   \n 
   " 
   );

}
 
   /* 
   
Partition步骤中哨兵选取的是最后一个元素作为哨兵
 
   */ 
   
 
   int 
    Partition( 
   int 
    A[], 
   int 
    p, 
   int 
    q)
{
  
   int 
    i,j,x,t;
 x  
   = 
    A[q];
 i  
   = 
    p 
   - 
   1 
   ;
  
   for 
    (j  
   = 
    p;j 
   <= 
   q;j 
   ++ 
   )
   
   if 
   (A[j]  
   < 
    x)
  {
   i 
   ++ 
   ;
   t  
   = 
    A[j];
   A[j]  
   = 
    A[i];
   A[i]  
   = 
    t;
  }
 A[q]  
   = 
    A[i 
   + 
   1 
   ];
 A[i 
   + 
   1 
   ]  
   = 
    x;
  
   return 
    i 
   + 
   1 
   ;
}
 
   /* 
   
递归调用的QuickSort程序
 
   */ 
   
 
   int 
    QuickSort( 
   int 
    A[], 
   int 
    p, 
   int 
    r)
{
  
   if 
   (p 
   < 
   r)
 {
   
   int 
    q  
   = 
    Partition(A,p,r);
  QuickSort(A,p,q 
   - 
   1 
   );
  QuickSort(A,q 
   + 
   1 
   ,r);
 }
}