quicksorting.cpp

算法之快速排序,用于说明快速排序的程序.

#include "stdafx.h"


#include <iostream> 
using namespace std;
 
  #include<stdlib.h>   
  #include<malloc.h>   
    
  typedef   int   KeyType;   
  #define   MAXSIZE   100   
  #define   MAXNUM   12   
  #define   OK   1   
    
  struct   RedType{   
  KeyType   key;      
  };   
    
  struct   SqList{   
  RedType   r[MAXSIZE+1];   
  int   length;   
  };//specify the structure  
      
  void   Enter_List(SqList   &L){   
  int   test,i=1,n;   
  cout<<"Please enter the length of Array(n):"<<endl;   
  cin>>n;   
  cout<<"Please enter the data:"<<endl;   
  while(n){   
  cin>>test;   
  L.r[i].key=test;   
  i++;   
  L.length++;   
  n--;   
  }   
  }   
  //cin the array which was not sorted
    
  KeyType   LT(KeyType   s1,KeyType   s2){   
  if(s1>=s2)   
  return   0;   
  else   
  return   1;   
  }   
  //compare s1 s2   
    
  void   Print(SqList   L){   
  cout<<"Array Sorted:"<<endl;   
  int   n=L.length;   
  for(int   i=1;i<=n;i++)   
  cout<<L.r[i].key<<'\t';   
  cout<<endl<<endl;   
  }   
  //输出排好序的序列(通过检查序列是否为升序判断程序运行成功与否)   
    
  void   Print_time(int   time){   
  cout<<"Time complexity is:\t"<<time<<endl<<endl;   
  } 

  KeyType   Partition(SqList   &L,int   low,int   high,int   &time){   
  RedType   s;   
  int   pivotkey;   
  pivotkey=L.r[low].key;   
  while(low<high){   
  while(low<high&&L.r[high].key>=pivotkey){   
  --high;   
  time++;   
  }   
  s=L.r[low];   
  L.r[low]=L.r[high];   
  L.r[high]=s;   
  while(low<high&&L.r[low].key<=pivotkey){   
  ++low;   
  time++;   
  }   
  s=L.r[low];   
  L.r[low]=L.r[high];   
  L.r[high]=s;   
  time+=6;   
  }   
  return   low;   
  }   
    
  int   time=0;   
  KeyType   Qsort(SqList   &L,int   low,int   high){   
  int   pivotkey;   
  if(low<high){   
  pivotkey=Partition(L,low,high,time);   
  Qsort(L,low,pivotkey-1);   
  Qsort(L,pivotkey+1,high);   
  }   
  return   time;   
  }   
    
  KeyType   QuickSort(SqList   &L){   
  int   time=0;   
  time=Qsort(L,1,L.length);   
  return   time;   
  }   
  //各种排序方法：   
  
  /*   
  KeyType   InsertSort(SqList   &L){   
  int   time=0;   
  for(int   i=2;i<=L.length;i++)   
  if(LT(L.r[i].key,L.r[i-1].key)){   
  L.r[0]=L.r[i];   
  L.r[i]=L.r[i-1];   
  for(int   j=i-2;LT(L.r[0].key,L.r[j].key);--j){   
  L.r[j+1]=L.r[j];   
  time++;   
  }   
  L.r[j+1]=L.r[0];   
  time+=3;   
  }   
  return   time;   
  }   
  //插入排序   
    
 
    
  
    
  
  
    
  KeyType   SelectMinKey(SqList   &L,int   i,int   &time){   
  int   s,t;   
  s=L.r[i].key;   
  t=i;   
  for(int   j=i+1;j<=L.length;j++)   
  if(s>L.r[j].key){   
  s=L.r[j].key;   
  t=j;   
  time+=2;   
  }   
  return   t;   
  }   
  KeyType   SelectSort(SqList   &L){   
  int   j,time=0;   
  RedType   s;   
  for(int   i=1;i<L.length;++i){   
  j=SelectMinKey(L,i,time);   
  if(i!=j){   
  s=L.r[i];   
  L.r[i]=L.r[j];   
  L.r[j]=s;   
  time+=3;   
  }   
  }   
  return   time;   
  }   
  //简单选择排序   
    
  KeyType   HeapAdjust(SqList   &H,int   s,int   m,int   &time){   
  RedType   rc;   
  rc=H.r[s];   
  for(int   j=2*s;j<=m;j*=2){   
  if(j<m&&LT(H.r[j].key,H.r[j+1].key))   
  ++j;   
  if(!LT(rc.key,H.r[j].key))   
  break;   
  H.r[s]=H.r[j];   
  s=j;   
  time+=4;   
  }   
  H.r[s]=rc;   
  return   OK;   
  }   
    
  KeyType   HeapSort(SqList   &H){   
  int   time=0;   
  for(int   i=H.length/2;i>0;--i)   
  HeapAdjust(H,i,H.length,time);   
  for(i=H.length;i>1;--i){   
  RedType   rc;   
  rc=H.r[1];   
  H.r[1]=H.r[i];   
  H.r[i]=rc;   
  time+=3;   
  HeapAdjust(H,1,i-1,time);   
  }   
  return   time;   
  }*/   
  //堆排序 

  void   main(){   
  SqList   L;   
  int   time=0;   
  L.length=0;   
  Enter_List(L);   
  //time=InsertSort(L);   
  //插入排序   
    
  //time=BInsertSort(L);   
  //折半插入排序   
    
  /*int   *dlta,n;   
  cout<<"输入增量序列数:"<<endl;   
  cin>>n;   
  dlta=(int   *)malloc(n*sizeof(int));   
  cout<<"输入增量序列:"<<endl;   
  for(int   i=0;i<n;i++)   
  cin>>dlta[i];   
  time=ShellSort(L,dlta,n);*/   
  //希尔排序   
    
  //time=QuickSort(L);   
  //快速排序   
    
  //time=SelectSort(L);   
  //简单选择排序   
    
  //time=HeapSort(L);   
  //堆排序   
    
  //time=BallSort(L);
  //其泡排序
  time=QuickSort(L);
     
  Print(L);   
  Print_time(time);   
  }