java命令行程序
来作为实例程序。Comparable<T>
的类型,都是可排序的。所以一个排序方法的签名大致可以是这样的public <T extends Comparable<? super T>> void sort(T[] items)
,不过为了演示的简单,下面使用int[] numbers
作为需要排序的数列,并且排序算法对它进行升序排序。使用下面的接口SortMethod来抽象表达排序算法:
interface SortMethod {
/**
* sort numbers.
*/
void sort(int[] numbers);
}
定义下面的SortingTools类来提供需要的辅助功能。
public final class SortingTools {
private static Random random = new Random();
public static void testSort(SortMethod method, int numberSize) {
int[] numbers = new int[numberSize];
for (int i = 0; i < numbers.length; i++) {
numbers[i] = random.nextInt(1000);
}
SortingTools.printNumbers(numbers);
Log.println("before sort. isAscending = " + SortingTools.isAscending(numbers));
method.sort(numbers);
SortingTools.printNumbers(numbers);
Log.println("after sort. isAscending = " + SortingTools.isAscending(numbers));
}
public static void printNumbers(int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
Log.print(numbers[i] + ", ");
}
Log.print("\n");
}
public static boolean isAscending(int[] numbers) {
int prev = numbers[0];
for (int i = 1; i < numbers.length; i++) {
if (numbers[i] < prev) {
return false;
}
prev = numbers[i];
}
return true;
}
}
Log.print()
方法简单封装了下显示打印的逻辑。先从一个简单的“冒泡排序”开始,实际上即使冒泡排序也有许多高级的变种,这里仅实现基础的算法。
假设是N个数字,要完成升序排列,每次从第一个元素开始,依次将较大数字放置到第N、N-1、N-2...位置处。
下面算法的时间效率属于O(N²):
public class BubbleSort implements SortMethod {
@Override
public void sort(int[] numbers) {
bubbleSort(numbers);
}
public static void bubbleSort(int[] numbers) {
int swap;
for (int end = numbers.length - 1; end > 0; end--) {
for (int i = 0; i < end; i++) {
if (numbers[i] > numbers[i + 1]) {
swap = numbers[i + 1];
numbers[i + 1] = numbers[i];
numbers[i] = swap;
}
}
}
}
}
实际的排序方法可以是静态的,然后重写的sort()方法简单地调用它来完成排序。
在main()方法中:
public static void main(String[] args) {
SortingTools.testSort(new BubbleSort(), 20);
}
一次输出如下:
246, 558, 286, 652, 470, 905, 11, 102, 705, 498, 695, 769, 86, 189, 986, 317, 957, 471, 406, 625,
before sort. isAscending = false
11, 86, 102, 189, 246, 286, 317, 406, 470, 471, 498, 558, 625, 652, 695, 705, 769, 905, 957, 986,
after sort. isAscending = true