排序是计算机数据处理中的一项最基本的操作。研究高效率的排序方法是数据结构的一个重要内容。假设n个记录的序列为{R1,R2,…Rn}，其相应的排序码为{K1，K2，…，Kn}。所谓排序就是将记录按排序码非递减（或非递增）的次序排列起来，形成新的有序序列。
本文用java语言实现了8种最基本的排序算法，并对相关算法的实现和复杂度进行了分析。
排序类
public abstract class Sort {
public final void sort(Comparable<Object>[] a) {
sort(a, 0, a.length - 1);
print(a);
}
public abstract void sort(Comparable<Object>[] a, int l, int r);
public final void swap(Comparable<Object>[] a, int i, int j) {
if (i == j)
return;
Comparable<Object> tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
public final void print(Comparable<Object>[] a) {
for (Comparable<Object> elem : a) {
System.out.print(elem + " ");
}
System.out.println();
}
}
选择排序 时O(n
2) 空O(1)
// 选择排序
class SelectionSort extends Sort {
@Override
public void sort(Comparable<Object>[] a, int l, int r) {
System.out.println("Selection Sort:");
for (int i = l; i < r; i++) {
int min = i;
for (int j = i + 1; j <= r; j++)
if (a[j].compareTo(a[min]) < 0)
min = j;
swap(a, i, min);
}
}
}
插入排序 时O(n
2) 空O(1)
// 插入排序
class InsertionSort extends Sort {
@Override
public void sort(Comparable<Object>[] a, int l, int r) {
System.out.println("Insertion Sort:");
for (int i = l + 1; i <= r; i++) {
int j = i;
Comparable<Object> e = a[i];
while (j > 0 && e.compareTo(a[j - 1]) < 0) {
a[j] = a[j - 1];
j--;
}
a[j] = e;
}
}
}
冒泡排序 时O(n
2) 空O(1)
// 冒泡排序
class BubbleSort extends Sort {
@Override
public void sort(Comparable<Object>[] a, int l, int r) {
System.out.println("Bubble Sort:");
for (int i = l; i < r; i++)
for (int j = r; j > i; j--)
if (a[j].compareTo(a[j - 1]) < 0)
swap(a, j - 1, j);
}
}
希尔排序 时O(n
1+h) 空O(1)
// 希尔排序
class ShellSort extends Sort {
@Override
public void sort(Comparable<Object>[] a, int l, int r) {
System.out.println("Shell Sort:");
int h;
for (h = 1; h <= (r - l) / 9; h = 3 * h + 1)
;
for (; h > 0; h /= 3)
for (int i = l + h; i <= r; i++) {
int j = i;
Comparable<Object> e = a[i];
while (j >= l + h && e.compareTo(a[j - h]) < 0) {
a[j] = a[j - h];
j -= h;
}
a[j] = e;
}
}
}
快速排序 时O(nlogn) 空O(logn)
// 快速排序
class QuickSort extends Sort {
@Override
public void sort(Comparable<Object>[] a, int l, int r) {
System.out.println("Quick Sort:");
qSort(a, l, r);
}
public void qSort(Comparable<Object>[] a, int l, int r) {
if (r <= l)
return;
int i = partition(a, l, r);
qSort(a, l, i - 1);
qSort(a, i + 1, r);
}
public int partition(Comparable<Object>[] a, int l, int r) {
int i = l - 1;
int j = r;
Comparable<Object> e = a[r];
for (;;) {
while (a[++i].compareTo(e) < 0)
;
while (e.compareTo(a[--j]) < 0)
if (j == l)
break;
if (i >= j)
break;
swap(a, i, j);
}
swap(a, i, r);
return i;
}
}
归并排序 时O(nlogn) 空O(n)
// 归并排序
class MergeSort extends Sort {
@Override
public void sort(Comparable<Object>[] a, int l, int r) {
System.out.println("Merge Sort:");
mSort(a, l, r);
}
public void mSort(Comparable<Object>[] a, int l, int r) {
if (r <= l)
return;
int m = (r + l) / 2;
mSort(a, l, m);
mSort(a, m + 1, r);
merge(a, l, m, r);
}
@SuppressWarnings("unchecked")
public void merge(Comparable<Object>[] a, int l, int m, int r) {
int i, j, k;
Comparable<Object>[] aux1 = new Comparable[m - l + 1];
Comparable<Object>[] aux2 = new Comparable[r - m];
for (i = l; i <= m; i++)
aux1[i - l] = a[i];
for (j = m + 1; j <= r; j++)
aux2[j - m - 1] = a[j];
i = j = 0;
k = l;
while (i < m - l + 1 && j < r - m) {
if (aux2[j].compareTo(aux1[i]) >= 0)
a[k++] = aux1[i++];
else
a[k++] = aux2[j++];
}
while (i < m - l + 1)
a[k++] = aux1[i++];
while (j < r - m)
a[k++] = aux2[j++];
}
}
堆排序 时O(nlogn) 空O(1)
// 堆排序
class HeapSort extends Sort {
@Override
public void sort(Comparable<Object>[] a, int l, int r) {
System.out.println("Heap Sort:");
int n = r - l;
for (int k = n / 2; k >= 0; k--)
heapify(a, k, n);
for (int i = n; i > 0; i--) {
swap(a, 0, i);
heapify(a, 0, i - 1);
}
}
public void heapify(Comparable<Object>[] a, int k, int n) {
for (int j = 2 * k; j <= n; j *= 2) {
if (j < n && a[j].compareTo(a[j + 1]) < 0)
j++;
if (a[k].compareTo(a[j]) >= 0)
break;
swap(a, k, j);
k = j;
}
}
}
基数排序
可排序元素类
class Index implements Comparable<Object> {
Index(int index, String str) {
this.index = index;
this.str = str;
}
private int index;
private String str;
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
public String getStr() {
return str;
}
public void setStr(String str) {
this.str = str;
}
@Override
public int compareTo(Object o) {
if (o instanceof Index) {
if (index < ((Index) o).getIndex())
return -1;
else if (index > ((Index) o).getIndex())
return 1;
else
return 0;
} else
throw new ClassCastException("Can't compare!");
}
@Override
public String toString() {
return index + ":" + str;
}
}
测试类
public class Main {
public static void main(String[] args) {
Sort[] sorts = new Sort[7];
sorts[0] = new SelectionSort();
sorts[1] = new InsertionSort();
sorts[2] = new BubbleSort();
sorts[3] = new ShellSort();
sorts[4] = new QuickSort();
sorts[5] = new MergeSort();
sorts[6] = new HeapSort();
for (Sort s : sorts) {
Index[] indices = { new Index(8, "eight1"), new Index(3, "three1"),
new Index(5, "five"), new Index(3, "three2"),
new Index(8, "eight2"), new Index(8, "eight3"),
new Index(8, "eight4"), new Index(8, "eight5"),
new Index(11, "eleven"), new Index(6, "six1"),
new Index(1, "one"), new Index(4, "four"),
new Index(2, "two"), new Index(7, "seven"),
new Index(9, "nine"), new Index(6, "six2"),
new Index(12, "twelve"), new Index(8, "eight6"),
new Index(14, "fourteen"), new Index(13, "thirteen"),
new Index(10, "ten") };
s.sort(indices);
}
}
}
算法稳定性分析
以下是程序执行结果：
Selection Sort:
1:one 2:two 3:three2 3:three1 4:four 5:five 6:six1 6:six2 7:seven 8:eight4 8:eight1 8:eight2 8:eight3 8:eight5 8:eight6 9:nine 10:ten 11:eleven 12:twelve 13:thirteen 14:fourteen
Insertion Sort:
1:one 2:two 3:three1 3:three2 4:four 5:five 6:six1 6:six2 7:seven 8:eight1 8:eight2 8:eight3 8:eight4 8:eight5 8:eight6 9:nine 10:ten 11:eleven 12:twelve 13:thirteen 14:fourteen
Bubble Sort:
1:one 2:two 3:three1 3:three2 4:four 5:five 6:six1 6:six2 7:seven 8:eight1 8:eight2 8:eight3 8:eight4 8:eight5 8:eight6 9:nine 10:ten 11:eleven 12:twelve 13:thirteen 14:fourteen
Shell Sort:
1:one 2:two 3:three1 3:three2 4:four 5:five 6:six1 6:six2 7:seven 8:eight1 8:eight2 8:eight4 8:eight3 8:eight5 8:eight6 9:nine 10:ten 11:eleven 12:twelve 13:thirteen 14:fourteen
Quick Sort:
1:one 2:two 3:three2 3:three1 4:four 5:five 6:six1 6:six2 7:seven 8:eight2 8:eight1 8:eight5 8:eight6 8:eight3 8:eight4 9:nine 10:ten 11:eleven 12:twelve 13:thirteen 14:fourteen
Merge Sort:
1:one 2:two 3:three1 3:three2 4:four 5:five 6:six1 6:six2 7:seven 8:eight1 8:eight2 8:eight3 8:eight4 8:eight5 8:eight6 9:nine 10:ten 11:eleven 12:twelve 13:thirteen 14:fourteen
Heap Sort:
1:one 2:two 3:three2 3:three1 4:four 5:five 6:six1 6:six2 7:seven 8:eight5 8:eight4 8:eight3 8:eight2 8:eight6 8:eight1 9:nine 10:ten 11:eleven 12:twelve 13:thirteen 14:fourteen
可见，所有算法都能依据关键字进行正确排序。其中，插入、冒泡、归并排序是稳定的，而其他排序如选择、希尔、快速、堆排序是不稳定的。
可以从
这里下载本文源码。
posted on 2009-06-01 14:24
chenkkkabc 阅读(97)
评论(0) 编辑 收藏 所属分类:
算法