考研数据结构温习-快速排序
C++版本,比较繁琐,但比较节省空间
int SplitArray(ElementType A[], int low, int high)
{
ElementType basic=A[low];
while(low<high)
{
while(low<high && basic<=A[high])high--;
A[low]=A[high];
while(low<high && basic>=A[low])low++;
A[high]=A[low];
}
A[low]=basic;
return low;
}
void QuickSort(ElementType A[],int low,int high)
{
if(low<high)
{
int basicIndex=SplitArray(A,low,high);
QuickSort(A,low,basicIndex-1);
QuickSort(A,basicIndex+1,high);
}
}
在Erlang中实现快速排序,只需两行代码:
qsort([])->[];
qsort([P|T])->qsort([X||X<-T,X<P]) ++[P]++ qsort([X||X<-T,X>=P]).
用Python做类似的表达:
def sort(data: list):
return sort([data[i] for i in range(len(data)) if data[i] < data[0] and i != 0]) + \
[data[0]] + \
sort([data[i] for i in range(len(data)) if data[i] >= data[0] and i != 0]) \
if len(data) > 0 else data
而作为Erlang的父语言的Prolog实现起来则繁琐一丢丢:
qsort([X|Xs],Ys) :- partition(Xs,X,Left,Right), qsort(Left,Ls), qsort(Right,Rs),
append(Ls,[X|Rs],Ys).
qsort([],[]).
partition([X|Xs],Y,[X|Ls],Rs) :- X <= Y, partition(Xs,Y,Ls,Rs).
partition([X|Xs],Y,Ls,[X|Rs]) :- X > Y, partition(Xs,Y,Ls,Rs).
partition([],Y,[],[]).
append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :- append(Xs,Ys,Zs).
不过也比较简洁了.