快速排序.cpp

来自「快速排序。通过C语言实现。能正常运行。但需要帐户才能下载。请见谅。」· C++ 代码 · 共 65 行

#include<stdio.h>
#include<stdlib.h> 
#include<malloc.h>
#define MAXSIZE 100

typedef struct{
	int *elem;
	int length;
}SqList;

int Partition(SqList &L,int low,int high)
{

  L.elem[0]=L.elem[low];                              //用表的第一个记录作枢轴记录
  while(low<high){                                    //从表的两段向中间扫描
	  while(low<high&&L.elem[high]>=L.elem[0])
		  --high;                                     //比枢轴记录小的记录移到低端
	  L.elem[low]=L.elem[high];
	  while(low<high&&L.elem[low]<=L.elem[0])
		  ++low;                                      //比枢轴记录大的记录移到高端
	  L.elem[high]=L.elem[low];
  }
  L.elem[low]=L.elem[0];
  return low;                                         //返回枢轴所在位置
}


void QSort(SqList &L,int low,int high){
	int pivotloc;
	if(low<high){                                     //长度大于1
		pivotloc=Partition(L,low,high);
		QSort(L,low,pivotloc-1);                      //对低子表进行递归排序
		QSort(L,pivotloc+1,high);                     //对高子表递归排序
	}
}




void main()
{
  SqList L;
  int n,i;
  L.elem=(int*)malloc(MAXSIZE*sizeof(int));
  if(!L.elem)
  {
	  printf("分配空间失败\n");
      return;
  }
  printf("请输入随机生成数的个数(不大于100个):");
  scanf("%d",&n);
  L.length=n;
  printf("随机生成%d个的数为:\n",n);
  for(i=1;i<=n;i++)
  { 
      L.elem[i]=rand()%1000;
	  printf("%5d",L.elem[i]);
  }
  QSort(L,1,L.length);
  printf("\n经过快速排序后由小到大的顺序为:\n");
  for(i=1;i<=L.length;i++)
	 printf("%5d",L.elem[i]);
  printf("\n");
  return;
}