老婆决定要考同济大学的研究生,所以我就复习了数据结构,准备为她答疑。学习之后,我觉得应该把排序算法系统的整理一下,于是用JAVA把《Data Structure and Algoritm Analysis in C》里面的排序算法实现了。现在贴出来希望有人能帮我指正一下里面的错误。 整个结构我使用的是Strategy模式,这是一种很显然的选择。由Sort类扮演环境角色,SortStrategy扮演抽象策略角色。具体策略角色有六个,分别是InsertSort、BubbleSort、ChooseSort、ShellSort、MergeSort、QuickSort。分别是插入排序、冒泡排序、选择排序、希尔排序、归并排序和快速排序。还有堆排序、双向冒泡排序等我还没有写,写好了再贴上来。 因为代码量比较大,所以我分为几次贴出,这次只贴出Sort和SortStrategy的代码。
SortStratey接口:
package Utils.Sort;
/** *排序算法的接口 */ interface SortStrategy { /** *利用各种算法对实现了Comparable接口的数组进行升序排列 */ public void sort(Comparable[] obj); }
Sort类:
package Utils.Sort; /** *排序类,通过此类的sort()可以对实现了Comparable接口的数组进行升序排序 */ public class Sort { private SortStrategy strategy;
/** *构造方法,由type决定由什么算法进行排序,排序方法的单词守字母要大字,如对于快速排序应该是 uickSort *@param type 排序算法的类型 */ public Sort(String type) { try { type = "Utils.Sort." + type.trim(); Class c = Class.forName(type); strategy = (SortStrategy)c.newInstance(); } catch (Exception e) { e.printStackTrace(); } }
/** *排序方法,要求待排序的数组必须实现Comparable接口 */ public void sort(Comparable[] obj) { strategy.sort(obj); } }
其余的几个类的链接分别是: 插入排序:http://blog.csdn.net/Linyco/archive/2005/10/10/498735.aspx 冒泡排序:http://blog.csdn.net/Linyco/archive/2005/10/10/498736.aspx 选择排序:http://blog.csdn.net/Linyco/archive/2005/10/10/498742.aspx 归并排序:http://blog.csdn.net/Linyco/archive/2005/10/10/498746.aspx 希尔排序:http://blog.csdn.net/Linyco/archive/2005/10/10/498764.aspx 快速排序:http://blog.csdn.net/Linyco/archive/2005/10/10/498759.aspx |
|