排序.txt

Prolog开发的简单的几个人工智能方面的程序.含问题分析报告.

      归并排序法与快速排序法   
      归并排序法与快速排序法的思想中都有分治的成分，一般用到了递归，因而这两种排序算法用prolog实现还是比较自然的
      归并排序法
      采用2分归并，每次把表分为等长的两部分，分别对其进行排序，再将结果合并——于是涉及到表的分割(split)、合并(merge)
      split(array H,array T,array R)将表H等分为T和R
      merge(array H,array T,array R)则将表H和T合并为R，与append不同的是合并是按元素大小顺序的
      msort(array H,array T)将表H排序成为表T，则：
      msort([],[]).    % 对空表的处理
      msort([X],[X]).  % 单个元素的处理
      msort([X,Y|H],T):-  % 两个以上元素的处理
        split([X,Y|H],L,R),
        msort(L,SL),
        msort(R,SR),
        merge(SL,SR,T).
      即可完成排序。
      split用到了另一个谓词splitby(integer N,array H,array L,array 
      R)即将表H的前N的元素分到表，剩下的分到R中。
      split(H,L,R):-
        S = size(H) div 2,  % 一半
        splitby(S,H,L,R).
      splitby(0,X,[],X).  % 特殊情况的处理
      splitby(N,[X|H],[X|L],R):-
        N ＞ 0,
        N1 = N - 1,
        splitby(N1,H,L,R).
      现在可以把表分开了！
      merge实际上是排序的核心
      merge([],R,R).
      merge(L,[],L).
      merge([X|L],[Y|R],[X|T]):-
        X ＜= Y,
        merge(L,[Y|R],T).
      merge([X|L],[Y|R],[Y|T]):-
        X ＞ Y,
        merge([X|L],R,T).
      现在可以排序了
      msort([4,3,2,1],X),write(X),nl,readln(Q).
      快速排序法
      也是分治策略，对于待排序的表，把它以某一元素X谓标准，分成小于（等于）X、大于X两部分，设谓词为partition(element X,array 
      H,array L,array R)将表H依X分成表L和表R，则
      qsort([],[]).
      qsort([X],[X]).
      qsort([X|H],T):-
        partition(X,[X|H],L,R),
        qsort(L,SL),
        qsort(R,SR),
        append(SL,SR,T).
      下面讨论partition
      partition(X,[],[],[]).
      partition(X,[Y|H],[Y|L],R):-  % 小于（等于）X的元素放入表L
        Y ＜= X,
        partition(X,H,L,R).
      partition(X,[Y|H],L,[Y|R]):-  % 大于X的元素放入表R
        Y ＞ X,
        partition(X,H,L,R).
      测试一下：
        qsort([4,56,1,3,67],X),write(X),readln(Q).