Source: http://www.cnblogs.com/everhad/p/6246880.html
一些約定
java命令行程序
算法的學習和語言無關，下面使用一個java命令行程序來作為實例程序。一個算法一個類
排序算法使用一個方法就可以表示，不需要是一個對象。但為了讓各種排序算法的表示相互獨立，接下來分別為它們定義不同的類型，并提供一些工具類來產生隨機數序列，打印數字序列，對數列進行校驗等。以整數序列升序為例
對應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;
}
}printNumbers(int[] numbers)
用來打印輸出numbers，方面查看。Log.print()方法簡單封裝了下顯示打印的邏輯。isAscending(int[] numbers)
用來校驗指定序列numbers是否為升序。testSort()
測試method所表示的某種排序算法，對于將要學習的各種不同排序算法，測試的過程是一樣的。
先隨機生成numberSize大小的int[]數組，然后排序前后分別打印輸出數組各項，并且對數組是否為升序進行驗證。
冒泡排序
先從一個簡單的“冒泡排序”開始，實際上即使冒泡排序也有許多高級的變種，這里僅實現基礎的算法。
算法思路
假設是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（本文使用Atom編寫）
 |
不含病毒。www.avast.com |
留言列表
