关闭

关闭

封号提示

内容

首页 java排序算法大全.doc

java排序算法大全.doc

java排序算法大全.doc

上传者: 人依旧 2011-05-03 评分 5 0 158 22 717 暂无简介 简介 举报

简介:本文档为《java排序算法大全doc》,可适用于IT/计算机领域,主题内容包含java排序算法大全为了便于管理先引入个基础类:package algorithmspublic abstract class Sorter

java排序算法大全为了便于管理先引入个基础类:package algorithmspublic abstract class Sorter<E extends Comparable<E>> {        public abstract void sort(E array,int from ,int len)        public final void sort(E array)    {        sort(array,,arraylength)    }    protected final void swap(E array,int from ,int to)    {        E tmp=arrayfrom        arrayfrom=arrayto        arrayto=tmp    }}一插入排序该算法在数据规模小的时候十分高效该算法每次插入第K到前K个有序数组中一个合适位置K从开始到N,从而完成排序:package algorithms** * author yovn *public class InsertSorter<E extends Comparable<E>> extends Sorter<E> {    * (nonJavadoc)     * see algorithmsSorter#sort(E, int, int)     *    public void sort(E array, int from, int len) {         E tmp=          for(int i=fromi<fromleni)          {              tmp=arrayi              int j=i              for(j>fromj)              {                  if(tmpcompareTo(arrayj)<)                  {                      arrayj=arrayj                  }                  else break              }              arrayj=tmp          }    }        }二冒泡排序这可能是最简单的排序算法了算法思想是每次从数组末端开始比较相邻两元素把第i小的冒泡到数组的第i个位置。i从一直到N从而完成排序。(当然也可以从数组开始端开始比较相邻两元素把第i大的冒泡到数组的第Ni个位置。i从一直到N从而完成排序。)package algorithms** * author yovn * *public class BubbleSorter<E extends Comparable<E>> extends Sorter<E> {    private static  boolean DWON=true        public final void bubbledown(E array, int from, int len)    {        for(int i=fromi<fromleni)        {            for(int j=fromlenj>ij)            {                if(arrayjcompareTo(arrayj)<)                {                    swap(array,j,j)                }            }        }    }        public final void bubbleup(E array, int from, int len)    {        for(int i=fromleni>=fromi)        {            for(int j=fromj<ij)            {                if(arrayjcompareTo(arrayj)>)                {                    swap(array,j,j)                }            }        }    }    Override    public void sort(E array, int from, int len) {                if(DWON)        {            bubbledown(array,from,len)        }        else        {            bubbleup(array,from,len)        }    }    }三选择排序选择排序相对于冒泡来说它不是每次发现逆序都交换而是在找到全局第i小的时候记下该元素位置最后跟第i个元素交换从而保证数组最终的有序。相对与插入排序来说选择排序每次选出的都是全局第i小的不会调整前i个元素了。package algorithms** * author yovn * *public class SelectSorter<E extends Comparable<E>> extends Sorter<E> {    * (nonJavadoc)     * see algorithmsSorter#sort(E, int, int)     *    Override    public void sort(E array, int from, int len) {        for(int i=i<leni)        {            int smallest=i            int j=ifrom            for(j<fromlenj)            {                if(arrayjcompareTo(arraysmallest)<)                {                    smallest=j                }            }            swap(array,i,smallest)                          }    } }四Shell排序Shell排序可以理解为插入排序的变种它充分利用了插入排序的两个特点:)当数据规模小的时候非常高效)当给定数据已经有序时的时间代价为O(N)所以Shell排序每次把数据分成若个小块来使用插入排序而且之后在这若个小块排好序的情况下把它们合成大一点的小块继续使用插入排序不停的合并小块知道最后成一个块并使用插入排序。这里每次分成若干小块是通过“增量”来控制的开始时增量交大接近N,从而使得分割出来接近N个小块逐渐的减小“增量“最终到减小到。一直较好的增量序列是^k,^(k),,,,这样可使Shell排序时间复杂度达到O(N^)所以我在实现Shell排序的时候采用该增量序列package algorithms** * author yovn *public class ShellSorter<E extends Comparable<E>> extends Sorter<E>  {    * (nonJavadoc)     * Our delta value choose ^k,^(k),,,     * complexity is O(n^)     * see algorithmsSorter#sort(E, int, int)     *    Override    public void sort(E array, int from, int len) {                calculate  the first delta value        int value=        while((value)*<len)        {            value=(value)*                }            for(int delta=valuedelta>=delta=(delta))        {            for(int i=i<deltai)            {                modifyinsertsort(array,fromi,leni,delta)            }        }    }        private final  void modifyinsertsort(E array, int from, int len,int delta) {          if(len<=)return          E tmp=          for(int i=fromdeltai<fromleni=delta)          {              tmp=arrayi              int j=i              for(j>fromj=delta)              {                  if(tmpcompareTo(arrayjdelta)<)                  {                      arrayj=arrayjdelta                  }                  else break              }              arrayj=tmp          }    }}五快速排序快速排序是目前使用可能最广泛的排序算法了。一般分如下步骤:)选择一个枢纽元素(有很对选法我的实现里采用去中间元素的简单方法))使用该枢纽元素分割数组使得比该元素小的元素在它的左边比它大的在右边。并把枢纽元素放在合适的位置。)根据枢纽元素最后确定的位置把数组分成三部分左边的右边的枢纽元素自己对左边的右边的分别递归调用快速排序算法即可。快速排序的核心在于分割算法也可以说是最有技巧的部分。package algorithms** * author yovn * *public class QuickSorter<E extends Comparable<E>> extends Sorter<E> {    * (nonJavadoc)     * see algorithmsSorter#sort(E, int, int)     *    Override    public void sort(E array, int from, int len) {        qsort(array,from,fromlen)    }        private final void qsort(E array, int from, int to) {        if(tofrom<)return        int pivot=selectPivot(array,from,to)                        pivot=partion(array,from,to,pivot)                qsort(array,from,pivot)        qsort(array,pivot,to)            }    private int partion(E array, int from, int to, int pivot) {        E tmp=arraypivot        arraypivot=arraytonow to's position is available                while(from!=to)        {            while(from<toarrayfromcompareTo(tmp)<=)from            if(from<to)            {                arrayto=arrayfromnow from's position is available                to            }            while(from<toarraytocompareTo(tmp)>=)to            if(from<to)            {                arrayfrom=arraytonow to's position is available now                 from            }        }        arrayfrom=tmp        return from    }    private int selectPivot(E array, int from, int to) {            return (fromto)    }}六归并排序算法思想是每次把待排序列分成两部分分别对这两部分递归地用归并排序完成后把这两个子部分合并成一个序列。归并排序借助一个全局性临时数组来方便对子序列的归并该算法核心在于归并。package algorithmsimport javalangreflectArray** * author yovn * *public class MergeSorter<E extends Comparable<E>> extends Sorter<E>  {    * (nonJavadoc)     * see algorithmsSorter#sort(E, int, int)     *    SuppressWarnings("unchecked")    Override    public void sort(E array, int from, int len) {        if(len<=)return        E temporary=(E)ArraynewInstance(arraygetClass(),len)        mergesort(array,from,fromlen,temporary)    }    private final void mergesort(E array, int from, int to, E temporary) {        if(to<=from)        {            return        }        int middle=(fromto)        mergesort(array,from,middle,temporary)        mergesort(array,middle,to,temporary)        merge(array,from,to,middle,temporary)    }    private final void merge(E array, int from, int to, int middle, E temporary) {        int k=,leftIndex=,rightIndex=tofrom        Systemarraycopy(array, from, temporary, , middlefrom)        for(int i=i<tomiddlei)        {            temporarytofromi=arraymiddlei        }        while(k<tofrom)        {            if(temporaryleftIndexcompareTo(temporaryrightIndex)<)            {                arraykfrom=temporaryleftIndex                            }            else            {                arraykfrom=temporaryrightIndex            }            k        }            }}七堆排序堆是一种完全二叉树一般使用数组来实现。堆主要有两种核心操作)从指定节点向上调整(shiftUp))从指定节点向下调整(shiftDown)建堆以及删除堆定节点使用shiftDwon,而在插入节点时一般结合两种操作一起使用。堆排序借助最大值堆来实现第i次从堆顶移除最大值放到数组的倒数第i个位置然后shiftDown到倒数第i个位置,一共执行N此调整即完成排序。显然堆排序也是一种选择性的排序每次选择第i大的元素。package algorithms** * author yovn * *public class HeapSorter<E extends Comparable<E>> extends Sorter<E>  {    * (nonJavadoc)     * see algorithmsSorter#sort(E, int, int)     *    Override    public void sort(E array, int from, int len) {        buildheap(array,from,len)        for(int i=i<leni)        {            swap max value to the (leni)th position            swap(array,from,fromleni)            shiftdown(array,from,leni,)always shiftDown from         }    }    privatefinalvoid buildheap(E array, int from, int len) {        int pos=(len)we start from (len), because branch's node =leaf's node, and all leaf node is already a heap        for(int i=posi>=i)        {            shiftdown(array,from,len,i)        }            }        private final void shiftdown(E array,int from, int len, int pos)    {                E tmp=arrayfrompos        int index=pos*use left child        while(index<len)until no child        {            if(index<lenarrayfromindexcompareTo(arrayfromindex)<)right child is bigger            {                index=switch to right child            }            if(tmpcompareTo(arrayfromindex)<)            {                arrayfrompos=arrayfromindex                pos=index                index=pos*                            }            else            {                break            }                    }        arrayfrompos=tmp               }    }八桶式排序桶式排序不再是基于比较的了它和基数排序同属于分配类的排序这类排序的特点是事先要知道待排序列的一些特征。桶式排序事先要知道待排序列在一个范围内而且这个范围应该不是很大的。比如知道待排序列在,M)内那么可以分配M个桶第I个桶记录I的出现情况最后根据每个桶收到的位置信息把数据输出成有序的形式。这里我们用两个临时性数组一个用于记录位置信息一个用于方便输出数据成有序方式另外我们假设数据落在到MAX,如果所给数据不是从开始你可以把每个数减去最小的数。package algorithms** * author yovn * *public class BucketSorter {            public void sort(int keys,int from,int len,int max)    {        int temp=new intlen        int count=new intmax                        for(int i=i<leni)        {            countkeysfromi        }        calculate position info        for(int i=i<maxi)        {            counti=counticountithis means how many number which is less or equals than i,thus it is also position           }                Systemarraycopy(keys, from, temp, , len)        for(int k=lenk>=k)fromtheendingtobeginningcankeepthestability        {            keyscounttempk=tempk position  =count        }    }    **     * param args     *    public static void main(String args) {        int a={,,,,,,,,,,,,,,,,,,,}        BucketSorter sorter=new BucketSorter()        sortersort(a,,alength,)actually is , but  will also work                        for(int i=i<alengthi)        {            Systemoutprint(ai",")        }    }}九基数排序基数排序可以说是扩展了的桶式排序比如当待排序列在一个很大的范围内比如到内那么用桶式排序是很浪费空间的。而基数排序把每个排序码拆成由d个排序码比如任何一个位数(不满六位前面补)拆成个排序码分别是个位的十位的百位的。。。。排序时分次完成每次按第i个排序码来排。一般有两种方式:)高位优先(MSD):从高位到低位依次对序列排序)低位优先(LSD):从低位到高位依次对序列排序计算机一般采用低位优先法(人类一般使用高位优先)但是采用低位优先时要确保排序算法的稳定性。基数排序借助桶式排序每次按第N位排序时采用桶式排序。对于如何安排每次落入同一个桶中的数据有两种安排方法:)顺序存储:每次使用桶式排序放入r个桶中相同时增加计数。)链式存储:每个桶通过一个静态队列来跟踪。package algorithmsimport javautilArrays** * author yovn * *public class RadixSorter {        public static boolean USELINK=true        **     *      * param keys     * param from     * param len     * param radix  key's radix     * param d      how many sub keys should one key divide to     *    public void sort(int keys,int from ,int len,int radix, int d)    {        if(USELINK)        {            linkradixsort(keys,from,len,radix,d)        }        else        {            arrayradixsort(keys,from,len,radix,d)        }            }            private final void arrayradixsort(int keys, int from, int len, int radix,            int d)     {        int temporary=new intlen        int count=new intradix        int R=                for(int i=i<di)        {            Systemarraycopy(keys, from, temporary, , len)            Arraysfill(count, )            for(int k=k<lenk)            {                int subkey=(temporarykR)radix                countsubkey            }            for(int j=j<radixj)            {                countj=countjcountj            }            for(int m=lenm>=m)            {                int subkey=(temporarymR)radix                countsubkey                keysfromcountsubkey=temporarym            }            R*=radix        }               }    private static class LinkQueue    {        int head=        int tail=    }    private final void linkradixsort(int keys, int from, int len, int radix, int d) {                int nexts=new intlen                LinkQueue queues=new LinkQueueradix        for(int i=i<radixi)        {            queuesi=new LinkQueue()        }        for(int i=i<leni)        {            nextsi=i        }        nextslen=                int first=        for(int i=i<di)        {            linkradixsortdistribute(keys,from,len,radix,i,nexts,queues,first)            first=linkradixsortcollect(keys,from,len,radix,i,nexts,queues)        }        int tmps=new intlen        int k=        while(first!=)        {                    tmpsk=keysfromfirst            first=nextsfirst        }        Systemarraycopy(tmps, , keys, from, len)                    }    private final void linkradixsortdistribute(int keys, int from, int len,            int radix, int d, int nexts, LinkQueue queues,int first) {                for(int i=i<radixi)queuesihead=queuesitail=        while(first!=)        {            int val=keysfromfirst            for(int j=j<dj)val=radix            val=valradix            if(queuesvalhead==)            {                queuesvalhead=first            }            else             {                nextsqueuesvaltail=first                            }            queuesvaltail=first            first=nextsfirst        }            }    private int linkradixsortcollect(int keys, int from, int len,            int radix, int d, int nexts, LinkQueue queues) {        int first=        int last=        int fromQueue=        for((fromQueue<radix)(queuesfromQueuehead==)fromQueue)        first=queuesfromQueuehead        last=queuesfromQueuetail                while(fromQueue<radixqueuesfromQueuehead!=)        {            fromQueue=            for((fromQueue<radix)(queuesfromQueuehead==)fromQueue)                        nextslast=queuesfromQueuehead            last=queuesfromQueuetail                    }        if(last!=)nextslast=        return first    }        **     * param args     *    public static void main(String args) {        int a={,,,,,,,,,,,,,,,,,,,,,,}        USELINK=true        RadixSorter sorter=new RadixSorter()        sortersort(a,,alength,,)        for(int i=i<alengthi)        {            Systemoutprint(ai",")        }    }}

类似资料

编辑推荐

细说中国人_曾仕强.pdf

未来50年.[美]J·布洛克曼.pdf

经济增长的决定因素:跨国经验研究 (美)罗伯特·J·巴罗着.pdf

泡沫经济的经济对策:复合萧条论 (日)宫崎义一着.pdf

(明)王铎楷书一觉庵铭.pdf

职业精品

精彩专题

上传我的资料

精选资料

热门资料排行换一换

  • 武昌起义档桉资料选编(上卷).p…

  • 辛亥首义回忆录第二辑(湖北文史资…

  • 画线技术精讲从入门到精通 PDF…

  • 英语人称代词和物主代词专项练习(…

  • 论抗日战争胜利的伟大历史意义.d…

  • 哥伦比亚商学院价值投资讲义.pdf

  • 【钱龙股经红皮书系列—股法无边】…

  • 徐勇:非均衡的中国政治-城市与乡…

  • 电化学交流阻抗谱.ppt

  • 资料评价:

    / 16
    所需积分:1 立即下载

    意见
    反馈

    返回
    顶部