数据结构C语言快速排序法.doc

《数据结构C语言快速排序法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构C语言---快速排序法数据结构C语言---快速排序法从空树出发，将关键字序列{45，24，53，45，12，24，90}依次插入生成一棵二叉排序树，然后在建立的二叉排序树中分别查找关键字24和70，返回查找成功或失败信息，并显示查找所进行的比较次数。算法描述1首先提示用户输入要进行排序的数目；2进行for()循环语句，将用户要排序的数字用线性表的函数：　　　ListInsert_Sq(SqList*L,inti,ElemTypee)　　插入进线性表存储单元中；3开始进行快速排序法排序：　主要函数为Partition()。算法为：要用到下标地址low和high位置，以及设置一个枢

2、轴pivotkey（这里取为第一个要排序的数即elem[1]）；先从high所指位置向前搜索，找到第一个比枢轴小的数与之交换；再从low所指位置向后搜索，找到第一个比枢轴大的数与之交换；重复这两步直到low=high为止。　此时排序结束。4调用线性表的基本操作函数将排序好的线性表输出来即可以！#include#include#defineOK1#defineERROR0#defineOVERFLOW-1#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefintStatus;typedefintK

3、eyType;typedefstruct{KeyTypekey;}ElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;StatusInitList_Sq(SqList*L){L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L->elem)exit(OVERFLOW);L->length=0;L->listsize=LIST_INIT_SIZE;returnOK;}StatusListInsert_Sq(SqList*L,inti

4、,ElemTypee){ElemType*newbase,*p,*q;if(i<1

5、

6、i>L->length+1)returnERROR;if(L->length>=L->listsize){newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L->elem=newbase;L->listsize+=LISTINCREMENT;}q=&(L->elem[i-1]);for(p=&(L->elem[L->length-1]);

7、p>=q;p--)*(p+1)=*p;*q=e;++L->length;returnOK;}voidDisp_Sq(SqList*L){inti;for(i=1;ilength;i++){printf("%d",(L->elem[i]).key);if(ilength-1)printf("->");}printf("");}StatusPartition(SqList*L,intlow,inthigh){intpivotkey;L->elem[0]=L->elem[low];pivotkey=L->elem[low].key;while(low

8、e(lowelem[high].key>=pivotkey)--high;L->elem[low]=L->elem[high];while(lowelem[low].key<=pivotkey)++low;L->elem[high]=L->elem[low];}L->elem[low]=L->elem[0];returnlow;}/*Partition*/voidQSort(SqList*L,intlow,inthigh){intpivotloc;if(low

9、q(L);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);}}/*QSort*/voidQuickSort(SqList*L){QSort(L,1,L->length-1);}/*QuickSort*/main(){SqList*L;intn,m=0;charc;ElemType*temp;temp=(ElemType*)malloc(1*sizeof(KeyType));temp->key=0