快速算法演示

 快速算法是通过反复对产生的文件进行划分来实现的

时间复杂度:最坏情况的时间是O(n2)平均情况的时间是O(nlogn)

空间复杂度:当n>1  S(n)=2+S(|_(n-1)/2_|)当n<=1 S(n)=0

(C#)源代码 quicksort.cs

using  System; using  System.Text; namespace  cn.blog8s{     ///   <summary>      ///  快速分类算法演示     ///   </summary>      public   class  BINSRCH    {         static   void  Main()        {             int [] A  =   new   int [] {  65 ,  70 ,  75 ,  80 ,  85 ,  60 ,  55 ,  50 ,  45 ,  32767  };            print(A,  9 );            quickSort(A,  0 ,  9 );            Console.Write( " 请输入一个大于1且小于9的数:  " );             int  k  =  Convert.ToInt32(Console.ReadLine());            Console.WriteLine( " 第 "   +  k  +   " 小元素是: "   +  A[select(A,  9 , k  -   1 )]);            Console.Read();        }         private   static   int  partition( int [] a, int  m, int  p)        { // 划分集合算法               int  v  =  a[m]; // 划分元素              int  i  =  m;             int  sum  =  p;             int  temp;             while  ( true )            {                 do                 {                    i ++ ;                }                 while  (a[i] < v); // 找一个比划分元素大的元素                  do                 {                    p -- ;                }                 while  (a[p] > v); // 找一个比划分元素小的元素                  if  (i  <  p)                {                    temp  =  a[i]; a[i]  =  a[p]; a[p]  =  temp; // 用上面找出来的值来交换                 }                 else                 {                     break ;                }            }            a[m]  =  a[p]; a[p]  =  v; // 把划分元素和右半部分最小的值交换             Console.Write( " 本次划分元素: " + a[p] + "     " );            print(a,  9 );             return  p; // p是快速分类划分元素的下标a[p]是第p小的值，划分元素是位置不用变了         }         private   static   void  quickSort( int [] a, int  p, int  q)        { // 快速分类算法              int  j;             if  (p  <  q)            {                j  =  partition(a, p, q + 1 ); // j是返回的划分元素的位置 参数q+1很关键记得要加1哦                 quickSort(a, p, j  -   1 );                quickSort(a, j  +   1 , q);             }         }         private   static   int  select( int [] a, int  n, int  k)        { // 选择算法              int  N  =  n;             int  m  =   0 ;             int  j;            Console.WriteLine( " 选择问题算法开始执行 " );             do             {                                j = partition(a,m,N);                 if  (j  ==  k)                {                     break ;                }                 else   if  (k  <  j)                {                    N  =  j;                }                 else                 {                    m  =  j  +   1 ;                }            }             while  ( true );             return  j;        }         private   static   void  print( int [] a, int  sum)        { // 打印用              for  ( int  i  =   0 ; i  <  sum; i ++ )            {                Console.Write(a[i] + "   " );            }            Console.WriteLine( "" );        }    }}

 

(c++)源代码 quicksort.cpp (这个代码没有包含选择算法)

#include  < stdlib.h > #include  < iostream.h > int  a[] = { 65 , 70 , 75 , 80 , 85 , 60 , 55 , 50 , 45 , 32767 }; void  print(){     for  ( int  i = 0 ;i < 9 ;i ++ )    {        cout << a[i] << "   " ;    }    cout << endl;} int  partition( int  m, int  p){     int  i,j,k;     int  v;     int  temp;    v = a[m];    i = m;    j = p;     while  (i < j)    {         do          {            i ++ ;        }         while  (a[i] < v);                 do         {            j -- ;        }         while  (a[j] > v);         if  (i < j)        {          temp = a[i];          a[i] = a[j];          a[j] = temp;        }    }    a[m] = a[j];    a[j] = v;    print();     return  j;} void  quicksort( int  p, int  q){     int  i;     int  j;    i = p;    j = q;     if  (i < j)    {        j = q + 1 ;    j = partition(i,j);    quicksort(i,j - 1 );    quicksort(j + 1 ,q);    }    } void  main(){  quicksort( 0 , 9 );  print();}