磕磕绊绊，跌跌撞撞，终于看完了《CLRS》第6部分，第7部分就先不看了。接下来就好好复习一遍，练习做一做，书上的算法实现一下。
以后贴的就是自己实现的算法了。
这一张是引导性的，介绍了两个排序算法来介绍算法的分析和设计的一些基本知识。
由于关于排序的算法很多，因此我用了一个Strategy Pattern来将它们组织起来，以下的代码用Java实现。
//这是一个排序算法接口，所有排序算法均要实现它 package com.zy.sortalgorithms; public interface SortAlgorithm { public void sort(int [] a); } //插入算法，很简单，也不多解释 package com.zy.sortalgorithms; public class InsertionSort implements SortAlgorithm{ @Override public void sort(int[] a) { // TODO Auto-generated method stub insertionSort(a); } //排入排序 private void insertionSort(int[] a) { // TODO Auto-generated method stub int len = a.length; int key; int j; for(int i=1; i<len; i++){ key = a[i]; j = i-1; while(j>=0&&a[j]>key) { a[j+1] = a[j]; j--; } a[j+1] = key; } } } //归并算法，也很简单，也不多解释 package com.zy.sortalgorithms; public class MergeSort implements SortAlgorithm{ @Override public void sort(int[] a) { // TODO Auto-generated method stub mergeSort(a, 0, a.length-1); } private void mergeSort(int[] a, int i, int length) { // TODO Auto-generated method stub if(i<length) { int m = (i+length)/2; mergeSort(a, i, m); mergeSort(a, m+1, length); merge(a, i, m, length); } } //merge a[begin,...,mid] and a[mid+1,...,end]; private void merge(int[] a, int begin, int mid, int end) { // TODO Auto-generated method stub int lenlow = mid - begin + 1; int lenhigh = end - mid; //new两个数组来存放数据 int[] arrlow = new int[lenlow]; int[] arrhigh = new int[lenhigh]; //将a[begin,...,mid] and a[mid+1,...,end]分别copy进arrlow和arrhigh int j=0, k=0; for(j=0; j<lenlow; j++) { arrlow[j] = a[begin+j]; } for(k=0; k<lenhigh; k++) { arrhigh[k] = a[k+mid+1]; } //合并的工作 j = 0; k = 0; int i = 0; while(j<lenlow&&k<lenhigh) { if(arrlow[j]<=arrhigh[k]) { a[begin+i] = arrlow[j]; i++; j++; } else { a[begin+i] = arrhigh[k]; i++; k++; } } //将剩下的数据copy进原来的数组 if(j>=lenlow&&k<lenhigh) { while(k<lenhigh) { a[begin+i] = arrhigh[k]; i++; k++; } } else if(j<lenlow&&k>=lenhigh) { while(j<lenlow) { a[begin+i] = arrlow[j]; i++; j++; } } } } //下面这个类包含了要进行排序的数据，它还有一个SortAlgorithm变量，可以指定具体执//行排序的算法 package com.zy.sorting; import com.zy.sortalgorithms.SortAlgorithm; public class SortArray { private int[] data; private int length; private SortAlgorithm sortAlg; //构造函数，指定长度 public SortArray(int length) { this.length = length; data = new int[length]; } //another构造函数，指定长度和对它排序的算法 public SortArray(int length, SortAlgorithm sortAlg) { this.length = length; this.sortAlg = sortAlg; } //初始化数据包含0~length-1的有序整数 public void initData() { for(int i=0; i<length; i++) { data[i] = i+1; } } //将数据进行随机化，即打乱数据的顺序 public void dataRandomize() { RandomHelper.RandomizeArray(data); } //指定对数据进行排序的算法 public void setSortAlg(SortAlgorithm sortAlg) { this.sortAlg = sortAlg; } //使用指定的算法进行排序 public void performSort() { sortAlg.sort(data); } //打印数据 public void printData() { for(int i=0; i<length; i++) { System.out.print(data[i]+"/t"); } } }
