c语言各种排序举例

#include

#define MAXSIZE 20 //排序表的最大容量 typedef struct //定义排序表的结构 {int elemword[MAXSIZE]; //数据元素关键字 int count; //表中当前元素的个数 }SqList;

void InitialSqList(SqList&); //初始化排序表 void QuickSort(SqList &); //快速排序

void QSort(SqList &,int,int); //子序列快速排序 int Partition(SqList &,int,int); //一趟快速排序 void PrintSqList(SqList); //显示表中的所有元素 void main()

{SqList L; //声明表L

char j='y';

//-------------------------程序说明------------------------------- printf(\本程序将演示快速排序的操作。\\n\

//---------------------------------------------------------------- while(j!='n'&&j!='N')

{InitialSqList(L); //待排序列初始化 QuickSort(L); //快速排序

PrintSqList(L); //显示排序结果

printf(\继续进行下一次排序吗?(Y/N)\scanf(\}

printf(\程序运行结束!\\n按任意键关闭窗口!\\n\getchar();getchar(); }

void InitialSqList(SqList &L) {//表初始化 int i;

printf(\请输入待排序的记录的个数:\scanf(\

printf(\请输入待排序的记录的关键字(整型数):\\n\for(i=1;i<=L.count;i++) scanf(\}

void QuickSort(SqList &L) {//对顺序表L做快速排序。 QSort(L,1,L.count); }

void QSort(SqList &L,int low,int high)

{//对顺序表中的子序列L.r[low..high]作快速排序 int pivotloc;

if(low

{pivotloc=Partition(L,low,high); //将L.elemword[low..high]一分为二 QSort(L,low,pivotloc-1); //对低子表递归排序,pivotloc是枢轴位置 QSort(L,pivotloc+1,high); //对高子表递归排序 } }

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

{//交换顺序表L中子表r[low..high]的记录，枢轴记录到位，并返回其所在位置，此时 //在它之前(后)的记录均不大(小)于它 int pivotkey;

pivotkey=L.elemword[low]; //用子表的第一个记录作枢轴记录 while(low=pivotkey) --high;

L.elemword[low]=L.elemword[high];//将比枢轴记录小的记录移到低端 while(low

L.elemword[high]=L.elemword[low]; //将比枢轴记录大的记录移到高端 }

L.elemword[low]=pivotkey; //枢轴记录到位 return low; //返回枢轴记录 }

void PrintSqList(SqList L) {//显示表中所有元素 int i;

printf(\已排好序的序列如下：\\n\for(i=1;i<=L.count;i++)

printf(\printf(\}

***************************************************************************

6.堆排序的程序实现 :

//* * * * * * * * * * * * * * * * * * * * * * * * //*PROGRAM :堆排序 * //*CONTENT :堆排序 *

//* * * * * * * * * * * * * * * * * * * * * * * * #include

#include #include #include #include

#define MAXSIZE 20 //排序表的最大容量 typedef struct //定义排序表的结构 {int elemword[MAXSIZE]; //数据元素关键字 int length; //表中当前元素的个数 }SqList;

void InitialSqList(SqList&); //初始化排序表 void HeapSort(SqList &); //堆排序

void HeapAdjust(SqList &,int,int); //堆调整 void PrintSqList(SqList); //显示表中的所有元素 void main()

{SqList L; //声明表L char j='y';

//-------------------------程序说明------------------------------- printf(\本程序将演示堆排序的操作。\\n\

//---------------------------------------------------------------- while(j!='n'&&j!='N')

{InitialSqList(L); //待排序列初始化 HeapSort(L); //堆排序

PrintSqList(L); //显示排序结果 printf(\继续进行下一次排序吗?(Y/N)\scanf(\}

printf(\程序运行结束!\\n按任意键关闭窗口!\\n\getchar();getchar(); }

void InitialSqList(SqList &L) {//表初始化 int i;

printf(\请输入待排序的记录的个数:\scanf(\

printf(\请输入待排序的记录的关键字(整型数):\\n\for(i=1;i<=L.length;i++)

scanf(\}

void HeapSort(SqList &L) {//对顺序表L做堆排序。 int i,j,t;

for(i=L.length/2;i>0;--i) //把L.elemword[1..L.length]建成大顶堆 HeapAdjust(L,i,L.length); for(i=L.length;i>1;--i)

{t=L.elemword[1]; //将堆顶记录和当前未经排序子序列L.elemword[1..i] L.elemword[1]=L.elemword[i]; //中的最后一个记录相互交换 L.elemword[i]=t;

HeapAdjust(L,1,i-1); //将L.r[1..i-1]重新调整为大顶堆 } }

void HeapAdjust(SqList &H,int s,int m)

{//已知H.elemword[s..m]中除H.elemword[s]之外均满足堆的定义,本函数调整H.elemword[s]

//使H.elemword[s..m]成为一个大顶堆 int j,rc; rc=H.elemword[s];

for(j=2*s;j<=m;j*=2) //沿关键字叫大的结点向下筛选

{if(j=H.elemword[j]) break; //rc应插入在位置s上 H.elemword[s]=H.elemword[j]; s=j; }

H.elemword[s]=rc; //插入 }

void PrintSqList(SqList L) {//显示表中所有元素 int i;

printf(\已排好序的序列如下：\\n\for(i=1;i<=L.length;i++) printf(\printf(\}