| 得2004年，我用c++按照算法书上介绍，实现了一些算法，比如排序、查
找、二叉树、AVL、红黑树等。那些代码随着一次次的搬家也不知所踪，也许在原来公司的产品中有它的身影吧。前几天，无聊时翻出了《编程珠玑》这本书，是
一本非常经典的算法书。该书只有200页，花一个下午就能看完大部分内容，还是很值得的。
现在在使用Java语言，也许用Java实现一些算法也是一件很有趣的事情哦。也算是温故而知新吧。
首先还是实现一些简单的排序算法吧。为了简单起见，只实现了升序排序。在我的机器上用QuickSort排序100万个随机整数花费1.6秒左右
package cn.tenyears.demo;
/**
* implements some typical sort algorithms. includes selection sort, bubble
* sort, insertion sort, quicksort.
* @author taolue
*/
public class Sort {
private Sort() {
}
private static <T> void swap(T[] a, int first, int second) {
T temp = a[first];
a[first] = a[second];
a[second] = temp;
}
@SuppressWarnings("unchecked")
public static void selectionSort(Comparable[] a) {
int size = a.length;
for (int index = 0; index < size - 1; index++) {
int small = index;
for (int index2 = index + 1; index2 < size; index2++) {
if (a[index2].compareTo(a[small]) < 0)
small = index2;
}
swap(a, index, small);
}
}
@SuppressWarnings("unchecked")
public static void bubbleSort(Comparable[] a) {
int size = a.length;
for (int index = 0; index < size - 1; index++) {
for (int index2 = index + 1; index2 < size; index2++) {
if (a[index].compareTo(a[index2]) > 0) {
swap(a, index, index2);
}
}
}
}
@SuppressWarnings("unchecked")
public static void insertionSort(Comparable[] a) {
int size = a.length;
int index2;
Comparable temp;
for (int index = 1; index < size; index++) {
index2 = index;
temp = a[index];
while (index2 > 0 && temp.compareTo(a[index2 - 1]) < 0) {
swap(a, index2, index2 - 1);
index2--;
}
}
}
public static void quickSort(Comparable[] a) {
quickSortInternal(a, 0, a.length - 1);
}
@SuppressWarnings("unchecked")
private static void quickSortInternal(Comparable[] a, int low, int high) {
Comparable pivot;
int scanUp, scanDown;
int mid;
if (high - low <= 0)
return;
if (high - low <= 1) {
if (a[high].compareTo(a[low]) < 0)
swap(a, high, low);
return;
}
mid = (low + high) / 2;
pivot = a[mid];
swap(a, mid, low);
scanUp = low + 1;
scanDown = high;
do {
while (scanUp <= scanDown && a[scanUp].compareTo(pivot) < 0)
scanUp++;
while (scanDown >= scanUp && pivot.compareTo(a[scanDown]) <= 0)
scanDown--;
if (scanUp < scanDown)
swap(a, scanUp, scanDown);
} while (scanUp < scanDown);
a[low] = a[scanDown];
a[scanDown] = pivot;
if (low < scanDown - 1)
quickSortInternal(a, low, scanDown - 1);
if (scanDown + 1 < high)
quickSortInternal(a, scanDown + 1, high);
}
public static <T> void printA(T[] a) {
for (int i = 0; i < a.length; i++) {
if (i != 0 && i % 20 == 0)
System.out.println();
System.out.print(a[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
int size = 1000000;
Integer[] a = new Integer[size];
for (int i = 0; i < size; i++)
a[i] = Integer.valueOf((int) Math.round(Math.random() * size));
long start = System.currentTimeMillis();
quickSort(a);
long end = System.currentTimeMillis();
System.out.println("Last: " + (end - start) + " ms");
}
} |
