数据结构课程设计排序算法总结

high--; L.elem[0]=L.elem[low]; L.elem[low]=L.elem[high]; L.elem[high]=L.elem[0];

while(low

return low; }

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

//对顺序表L中的子序列L.elem[low...high]进行快速排序 int pivot=0; if(low

void QuickSort(SqList &L) {

QSort(L,1,L.length); }

//堆排

void HeapAdjust(SqList &L,int s,int m) {

int j=0;

L.elem[0]=L.elem[s]; for(j=2*s;j<=m;j*=2) { if(j

s=j; }

L.elem[s]=L.elem[0]; }

void HeapSort(SqList &L) {

int i=0;

for(i=L.length/2;i>0;i--)

HeapAdjust(L,i,L.length); for(i=L.length;i>1;i--) {

L.elem[0]=L.elem[1]; L.elem[1]=L.elem[i]; L.elem[i]=L.elem[0]; HeapAdjust(L,1,i-1); } }

//归并

void Merge(SqList L,SqList &L1,int i,int m,int n) {

int j=0,k=0,p=0,q=0;

for(j=m+1,k=i;i<=m&&j<=n;++k) { if(L.elem[i]

if(i<=m) for(p=k,q=i;q<=m;p++,q++) L1.elem[p]=L.elem[q]; if(j<=n) for(p=k,q=j;q<=n;p++,q++) L1.elem[p]=L.elem[q]; }

void MSort(SqList L,SqList &L1,int s,int t) {

SqList L2; int * p;

if((p=(int *)malloc((t-s+1)*sizeof(int)))==0) 序表存储空间

//动态分配顺 { printf(\.\\n\ exit(1); }

L2.elem=p;

L2.length=t-s+1;

int m=0; if(s==t) L1.elem[s]=L.elem[s]; else { m=(s+t)/2; MSort(L,L2,s,m); MSort(L,L2,m+1,t); Merge(L2,L1,s,m,t); } }

void MergeSort(SqList &L) {

MSort(L,L,1,L.length); }