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

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

2、为第一个要排序的数即elem1）；先从high所指位置向前搜索，找到第一个比枢轴小的数与之交换；再从low所指位置向后搜索，找到第一个比枢轴大的数与之交换；重复这两步直到low=high为止。此时排序结束。4调用线性表的基本操作函数将排序好的线性表输出来即可以！ #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int Status; typedef int KeyType; typedef

3、struct KeyType key; ElemType; typedef struct ElemType *elem; int length; int listsize; SqList; Status InitList_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; return OK; Status ListInsert_Sq(SqList *L,int i,

4、ElemType e) ElemType *newbase,*p,*q; if (iL-length+1) return ERROR; 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-elemi-1); for (p=&(L-elemL-length-1);p=q;p-) *(

5、p+1)=*p; *q=e; +L-length; return OK; void Disp_Sq(SqList *L) int i; for (i=1;ilength;i+) printf(%d,(L-elemi).key); if(ilength-1) printf(-); printf(n); Status Partition(SqList *L,int low,int high) int pivotkey; L-elem0=L-elemlow; pivotkey=L-elemlow.key; while(lowhigh) while(lowelemhigh.key=pivotkey)

6、-high; L-elemlow=L-elemhigh; while(lowelemlow.keyelemhigh=L-elemlow; L-elemlow=L-elem0; return low; /* Partition */void QSort(SqList *L,int low,int high) int pivotloc; if(lowlength-1); /* QuickSort */main() SqList *L; int n,m=0; char c; ElemType *temp; temp=(ElemType *)malloc(1*sizeof(KeyType); temp-key=0; L=NULL; clrscr(); do InitList_Sq(L); printf(How many numbers do you want to sort?); scanf(%d,&n); ListInsert_Sq(L,m+1,*temp); for(m=1;mkey=num; ListInsert_Sq(L,m+1,*temp); printf(Before sorting List is:n,L-length); Disp_Sq(L); printf(Start sort:n); QuickSort(L);