用JAVA实现的8种排序算法

《用JAVA实现的8种排序算法》由会员分享，可在线阅读，更多相关《用JAVA实现的8种排序算法（32页珍藏版）》请在装配图网上搜索。

1、0.排序基类/*为了后面排序算法扩展的方便，引入一个基础类Sorter*/package com.javasort;/*任何排序算法都继承此公共抽象基类Sorter* author Daniel Cheng*/public abstract class SorterE extends Comparable /* 任何排序算法都重写此抽象方法* param array:欲排序的数组* param from: 元素的起始下标* param len: 数组的长度*/public abstract void sort(E array, int from, int len);/* 测试排序用例时调用此方

2、法* param array*/public final void sort(E array) sort(array, 0, array.length);/* 需要交换元素顺序时调用此方法* param array* param from* param to*/protected final void swap(E array, int from, int to) E tmp = arrayfrom;arrayfrom = arrayto;arrayto = tmp;/* 打印排序后数组元素时调用此方法* param array*/public final void printResult(E

3、 array)for(int i=0;iarray.length;i+)System.out.print(arrayi+,);1. 冒泡排序package com.javasort.bubblesorter;/* 冒泡排序:最简单的排序算法了，算法思想是每次从数组末端开始比较相邻两元素，*把第i小的冒泡到数组的第i个位置。i从0 直到N-1从而完成排序。* (当然也可以从数组开始端开始比较相邻两元素，把第i大的冒泡到数组的第N-i个位置。* i从0 直到N-1从而完成排序。)*/import com.javasort.Sorter;/* author Daniel Cheng*/public

4、class BubbleSorterE extends Comparable extends Sorter private static boolean DOWN = true;Overrideif (DOWN) bubble_down(array, from, len); else bubble_up(array, from, len);private final void bubble_down(E array, int from, int len) for(int i=from;ii;j-)if(pareTo(arrayj-1)=from;i-)for(int j=from;j0)swa

5、p(array, j, j+1);static final void up() DOWN=false;/*/ package com.javasort.bubblesorter;import com.javasort.Sorter;/* author Daniel Cheng*/Comparable array=5,1,13,2,17,9,7,4,0;Sorter bubbleSorter=new BubbleSorter();/BubbleSorter.up();bubbleSorter.sort(array); bubbleSorter.printResult(array);2. 插入法排

6、序package com.javasort.insertsorter;/*插入法排序在数据规模小的时候十分高效，该算法每次插入第k+1个元素到*前k个有序数组中一个合适的的位置(k=O.N-l)，从而完成排序。*/import com.javasort.Sorter;/* author Daniel Cheng*/public class InsertSorterE extends Comparable extends Sorter OverrideE temp=null;for(int i=from+1;ifrom;j-)if(pareTo(arrayj-1)0)arrayj=arrayj-

7、1;elsebreak;arrayj=temp; package com.javasort.insertsorter;public class InsertSorterTest public static void main(String args) Comparable array=5,1,13,2,14,9,7,4,0;Sorter insertSort=new InsertSorter();insertSort.sort(array);insertSort.printResult(array);3. 快速排序package com.javasort.quicksorter;/* 快速排序

8、是目前使用可能最广泛的排序算法.一般分如下步骤：* 1)选择一个枢纽元素(有很对选法，我的实现里采用去中间元素的简单方法)* 2)使用该枢纽元素分割数组，使得比该元素小的元素在它的左边，比它大的在右边。并把枢纽元素放在合适的位置。* 3)根据枢纽元素最后确定的位置，把数组分成三部分，左边的，右边的，枢纽元素自己，对左边的，右边的分别递归调用快速排序 算法即可。* 快速排序的核心在于分割算法，也可以说是最有技巧的部分。*/* author Daniel Cheng*/ public class QuickSorterE extends Comparable extends Sorter Over

9、ridepublic void sort(E array, int from, int len) q_sort(array, from, from + len - 1);private final void q_sort(E array, int from, int to) if (to - from 1)return;int pivot = selectPivot(array, from, to);pivot = partion(array, from, to, pivot);q_sort(array, from, pivot - 1);q_sort(array, pivot + 1, to

10、);private int partion(E array, int from, int to, int pivot) E tmp = arraypivot;arraypivot = arrayto;/ now tos position is availablewhile (from != to) while (from to & pareTo(tmp) = 0)from+;if (from to) arrayto = arrayfrom;/ now froms position is available to-;while (from = 0)to-;if (from to) arrayfr

11、om = arrayto;/ now tos position is available now from+;arrayfrom = tmp;return from;private int selectPivot(E array, int from, int to) return (from + to) / 2;/*/ package com.javasort.quicksorter;import com.javasort.Sorter;import com.javasort.insertsorter.InsertSorter;/* author Daniel Cheng*/ public c

12、lass QuickSorterTest public static void main(String args) Comparable array=5,1,13,2,14,9,7,4,0;Sorter quickSorter=new QuickSorter();quickSorter.sort(array);quickSorter.printResult(array);4. 选择排序 package com.javasort.selectsorter;/* 选择排序:相对于冒泡来说，它不是每次发现逆序都交换，而是*在找到全局第i小的时候记下该元素位置，最后跟第i个元素交换，* 从而保证数组最

13、终的有序。*相对与插入排序来说，选择排序每次选出的都是全局第i小的，*不会调整前i个元素了。*/import com.javasort.Sorter;/* author Daniel Cheng*/public class SelectSorterE extends Comparable extends Sorter Overridepublic void sort(E array, int from, int len) for (int i = 0; i len; i+) int smallest = i;int j = i + from;for (; j from + len; j+) i

14、f (pareTo(arraysmallest) 0) smallest = j;swap(array, i, smallest); package com.javasort.selectsorter;import com.javasort.Sorter;import com.javasort.bubblesorter.BubbleSorter;public class SelectSorterTest public static void main(String args) Comparable array=5,1,13,2,17,9,7,4,0;Sorter selectSorter=ne

15、w SelectSorter();selectSorter.sort(array);selectSorter.printResult(array);5.Shell 排序package com.javasort.shellsorter;/* Shell 排序可以理解为插入排序的变种，它充分利用了插入排序的两个特点：1 )当数据规模小的时候非常高效2 )当给定数据已经有序时的时间代价为 O(N)所以，Shell排序每次把数据分成若个小块，来使用插入排序，而且之后在这若个小块排好序的情况下把它们合成大一点的小块，继续使 用插入排序，不停的合并小块，知道最后成一个块，并使用插入排序。这里每次分成若干小

16、块是通过“增量”来控制的，开始时增量交大，接近N/2,从而使得分割出来接近N/2个小块，逐渐的减小“增量“最终 到减小到 1。一直较好的增量序列是2Ak-1,2A(k-1)-1,.7,3丄这样可使Shell排序时间复杂度达到0(NT.5)所以我在实现Shell排序的时候采用该增量序列*/import com.javasort.Sorter;/* author Daniel Cheng* param */ public class ShellSorterE extends Comparable extends Sorter Overridepublic void sort(E array, in

17、t from, int len) /1.calculate( 计算) first delta valueint value=1;while(value+1)*2=1;delta=(delta+1)/2-1)for(int i=0;idelta;i+)modify_insert_sort(array,from+i,len-i,delta);private final void modify_insert_sort(E array, int from, int len, int delta) if(len=1)return;E tmp=null;for(int i=from+delta;ifrom

18、;j-=delta)if(pareTo(arrayj-delta)0) arrayj=arrayj-delta;else break;arrayj=tmp;package com.javasort.shellsorter;import com.javasort.Sorter;public class ShellSorterTest public static void main(String args) Comparable array=5,1,13,2,17,9,7,4,0;Sorter shellSorter=new ShellSorter();shellSorter.sort(array

19、);shellSorter.printResult(array);6.堆排序package com.javasort.heapsorter;/* 堆排序 :堆是一种完全二叉树，一般使用数组来实现。* 堆主要有两种核心操作，* 1)从指定节点向上调整 (shiftUp)* 2)从指定节点向下调整 (shiftDown)* 建堆，以及删除堆定节点使用 shiftDwon, 而在插入节点时一般结合两种操作一起使用。* 堆排序借助最大值堆来实现，第 i 次从堆顶移除最大值放到数组的倒数第 i 个位置，* 然后 shiftDown 到倒数第 i+1 个位置 ,一共执行 N 次调整，即完成排序。* 显然，

20、堆排序也是一种选择性的排序，每次选择第 i 大的元素。*/import com.javasort.Sorter;/* author Daniel Cheng*/ public class HeapSorterE extends Comparable extends Sorter Overridepublic void sort(E array, int from, int len) build_heap(array,from,len);for(int i=0;i=0;i-)shift_down(array,from,len,i);private final void shift_down(E

21、array, int from, int len, int pos) E tmp=arrayfrom+pos;int index=pos*2+l;用左孩子结点while(indexvlen)/直到没有孩子结点if(index+llen&arrayfrom+pareTo(arrayfrom+index+l)0) 右孩子结点是较大的index+=l;切换到右孩子结点if(pareTo(arrayfrom+index)0)arrayfrom+pos=arrayfrom+index;pos=index;index=pos*2+1;elsebreak;arrayfrom+pos=tmp;/*/packa

22、ge com.javasort.heapsorter;import com.javasort.Sorter;/* author Daniel Cheng*/public class HeapSorterTest public static void main(String args) Comparable array = 5, 1, 13, 2, 17, 9, 7, 4, 0 ;Sorter heapSorter=new HeapSorter();heapSorter.sort(array);heapSorter.printResult(array);7. 桶式排序/* 桶式排序 :* 桶式排

23、序不再是基于比较的了，它和基数排序同属于分配类的排序* 这类排序的特点是事先要知道待排 序列的一些特征。* 桶式排序事先要知道待排 序列在一个范围内，而且这个范围应该不是很大的。* 比如知道待排序列在 0,M )内，那么可以分配 M 个桶，第 I 个桶记录 I 的出现情况，* 最后根据每个桶收到的位置信息把数据输出成有序的形式。* 这里我们用两个临时性数组，一个用于记录位置信息，一个用于方便输出数据成有序方式，* 另外我们假设数据落在 0 到 MAX, 如果所给数据不是从 0 开始，你可以把每个数减去最小的数。*/package com.javasort.bucketsorter;/* aut

24、hor Daniel Cheng*/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=0;ilen;i+)countkeysfrom+i+;/calculate position infofor(int i=1;i=0;k-)/从最末到开头保持稳定性keys-counttempk=tempk;/ position +1 =count/* param args*/public static v

25、oid main(String args) int a=1,4,8,3,2,9,5,0,7,6,9,10,9,13,14,15,11,12,17,16;BucketSorter bucketSorter=new BucketSorter();bucketSorter.sort(a,0,a.length,20);/actually is 18, but 20 will also workfor(int i=0;ia.length;i+)System.out.print(ai+,);8. 基数排序/* 基数排序 :基数排序可以说是扩展了的桶式排序，* 比如当待排序列在一个很大的范围内，比如 0 到

26、 999999 内，那么用桶式排序是很浪费空间的。* 而基数排序把每个排序码拆成由 d 个排序码，比如任何一个 6 位数（不满六位前面补 0 ）拆成 6 个排序码* 分别是个位的，十位的，百位的。* 排序时，分 6 次完成，每次按第 i 个排序码来排。* 一般有两种方式 :* 1） 高位优先 （MSD） ： 从高位到低位依次对序列排序* 2）低位优先（LSD）：从低位到高位依次对序列排序* 计算机一般采用低位优先法（人类一般使用高位优先），但是采用低位优先时要确保排序算法的稳定性。* 基数排序借助桶式排序，每次按第 N 位排序时，采用桶式排序。* 对于如何安排每次落入同一个桶中的数据有两种安排

27、方法：* 1）顺序存储：每次使用桶式排序，放入r个桶中，相同时增加计数。* 2）链式存储：每个桶通过一个静态队列来跟踪。*/package com.javasort.radixsorter;import java.util.Arrays;/* author Daniel Cheng*/public class RadixSorter public static boolean USE_LINK=true;/* param keys* param from* param len* param radix keys radix* param dhow many sub keys should on

28、e key divide to*/public void sort(int keys,int from ,int len,int radix, int d)if(USE_LINK)link_radix_sort(keys,from,len,radix,d);elsearray_radix_sort(keys,from,len,radix,d);private final void array_radix_sort(int keys, int from, int len, int radix, int d)int temporary=new intlen;int count=new intrad

29、ix;int R=1;for(int i=0;id;i+)System.arraycopy(keys, from, temporary, 0, len);Arrays.fill(count, 0);for(int k=0;klen;k+)int subkey=(temporaryk/R)%radix; countsubkey+;for(int j=1;j=0;m-)int subkey=(temporarym/R)%radix;-countsubkey;keysfrom+countsubkey=temporarym;R*=radix;private static class LinkQueue

30、int head=-1;int tail=-1;private final void link_radix_sort(int keys, int from, int len, int radix, int d) int nexts=new intlen;LinkQueue queues=new LinkQueueradix;for(int i=0;iradix;i+)queuesi=new LinkQueue();for(int i=0;ilen-1;i+)nextsi=i+1;nextslen-1=-1;int first=0;for(int i=0;id;i+)link_radix_sor

31、t_distribute(keys,from,len,radix,i,nexts,queues,first); first=link_radix_sort_collect(keys,from,len,radix,i,nexts,queues);int tmps=new intlen;int k=0;while(first!=-1)tmpsk+=keysfrom+first;first=nextsfirst;System.arraycopy(tmps, 0, keys, from, len);private final void link_radix_sort_distribute(int ke

32、ys, int from, int len, int radix, int d, int nexts, LinkQueue queues,int first) for(int i=0;iradix;i+)queuesi.head=queuesi.tail=-1;while(first!=-1)int val=keysfrom+first;for(int j=0;jd;j+)val/=radix;val=val%radix;if(queuesval.head=-1)queuesval.head=first;elsenextsqueuesval.tail=first;queuesval.tail=

33、first;first=nextsfirst;private int link_radix_sort_collect(int keys, int from, int len,int radix, int d, int nexts, LinkQueue queues) int first=0;int last=0;int fromQueue=0;for(;(fromQueueradix-1)&(queuesfromQueue.head=-1);fromQueue+);first=queuesfromQueue.head;last=queuesfromQueue.tail;while(fromQu

34、eueradix-1&queuesfromQueue.head!=-1)fromQueue+=1; for(;(fromQueueradix-1)&(queuesfromQueue.head=-1);fromQueue+);nextslast=queuesfromQueue.head;last=queuesfromQueue.tail;if(last!=-1)nextslast=-1;return first;public static void main(String args) int a=1,4,8,3,2,9,5,0,7,6,9,10,9,135,14,15,11,33,999999999,222222222,1111111111,12,17,45,16;USE_LINK=true;RadixSorter sorter=new RadixSorter();sorter.sort(a,0,a.length,10,10);for(int i=0;ia.length;i+)System.out.print(ai+,);