squall.cpp

快速排序源码下载

#include<stdio.h>
#define MAXSIZE 20
#define N 8

typedef int KeyType;
typedef int InfoType;
 struct RedType
 {
   KeyType key; 
   InfoType otherinfo; 
 };

 struct SqList 
 {
   RedType r[MAXSIZE+1]; 
   int length; 
 };

 int Partition(SqList &L,int low,int high)
 { 
   KeyType pivotkey;
   L.r[0]=L.r[low]; 
   pivotkey=L.r[low].key; 
   while(low< high)
   { 
     while(low<high&&L.r[high].key>=pivotkey)
       --high;
     L.r[low]=L.r[high]; 
     while(low<high&&L.r[low].key<=pivotkey)
       ++low;
     L.r[high]=L.r[low]; 
   }
   L.r[low]=L.r[0]; 
   return low; 
 }

  void QSort(SqList &L,int low,int high)
 { 
   int pivotloc;
   if(low<high)
   { 
     pivotloc=Partition(L,low,high); 
     QSort(L,low,pivotloc-1); 
     QSort(L,pivotloc+1,high); 
   }
 }

 void QuickSort(SqList &L)
 { 
   QSort(L,1,L.length);
 }

 void print(SqList L)
 {
   int i;
   for(i=1;i<=L.length;i++)
     printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
   printf("\n");
 }

  void main()
 {
   RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
   SqList l;
   int i;
   for(i=0;i<N;i++)
     l.r[i+1]=d[i];
   l.length=N;
   printf("排序前:\n");
   print(l);
   QuickSort(l);
   printf("排序后:\n");
   print(l);
 }