基于算法第四版，语言是Java。
public class Example {
public static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public static void exch(Comparable[] a, int i, int j) {
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
public static void show(Comparable[] a) {
for(int i = 0; i < a.length; i++) {
StdOut.print(a[i] + " ");
}
StdOut.println();
}
public static boolean isSorted(Comparable[] a) {
for(int i = 0; i < a.length; i++) {
if (less(a[i], a[i - 1])) {
return false;
}
}
return true;
}
}
选择排序
public class Selection {
public static void sort(Comparable[] a) {
for(int i = 0; i < a.length; i++) {
int min = i;
for (int j = i + 1; j < a.length; j++) {
if (Example.less(a[j], a[min])) {
min = j;
}
}
Example.exch(a, i, min);
}
}
}
//[NOTE:] 大致思路。 每次循环i时min = i，j = i + 1，
//再比较i 和 j的大小，若a[j] < a[i]，则min = j。在结束j循环时进行交换。
插入排序
public class Insertion {
public static void sort(Comparable[] a) {
for(int i = 1; i < a.length; i++) {
for(int j = i; j > 0 && Example.less(a[j], a[j - 1]); j--) {
Example.exch(a, j, j - 1);
}
}
}
}
//[NOTE:] 大致思路。先进行i循环，如果a[i] < a[i - 1]，则把a[i] = a[0]。
//再进行j循环j = i - 1，如果a[j] > a[0]，则a[j + 1] = a[j]，在i循环内将a[0]赋值给a[j+ 1]。
希尔排序
public class Shell {
public static void sort(Comparable[] a) {
int N = a.length;
int h = 1;
while (h < N / 3) {
h = 3 * h + 1;
}
while (h >= 1) { // 1, 4, 13, 40, 121, 364, 1093.....
for(int i = h; i < N; i++) { //将数组变为h有序
//将a[i]插入到a[i - h], a[i - 2 * h], a[i - 3 * h]
for(int j = i; j > 0 && Example.less(a[j], a[j - h]); j -= h) {
Example.exch(a, j, j - h);
}
}
h = h / 3;
}
}
}
归并排序
public class Merge {
private static Comparable[] aux;
public static void sort(Comparable[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) { return; }
int mid = lo + (hi - lo) / 2;
sort(a, lo, mid);
sort(a, mid + 1, hi);
merge(a, lo, mid, hi);
}
public static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo, j = mid + 1;
for(int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (Example.less(aux[j], aux[i])) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
}
快速排序
public class Quick {
static int M = 7; //5~15之间的任意值在大多数情况下都能令人满意
public static void sort(Comparable[] a) {
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo + M) {
Insertion.sort(a);
return;
}
int j = partition(a, lo, hi);
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo, j = hi + 1;
Comparable v = a[lo];
while(true) {
while(Example.less(a[++i], v)) {
if (i == hi) { break; }
}
while(Example.less(v, a[--j])) {
if (j == lo) { break; }
}
if (i >= j) {
break;
}
}
Example.exch(a, lo, hi);
return j;
}
}
三向分切的快速排序
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo + M) {
Insertion.sort(a);
return;
}
int lt = lo, i= lo + 1, gt = hi;
Comparable v = a[lo];
while(i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0) {
Example.exch(a, lt++, i++);
} else if (cmp > 0) {
Example.exch(a, i, gt--);
} else {
i++;
}
}
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}
优先队列和堆排序
基于堆的优先序列
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq;
private int N = 0;
private boolean less(int i, int j) {
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i, int j) {
Key t = pq[i];
pq[i] = pq[j];
pq[j] = t;
}
private void swim(int k) {
while(k > 1 && less(k / 2, k)) {
exch(k / 2, k);
}
}
private void sink(int k) {
while(2 * k <= N) {
int j = 2 * k;
if (j < N && less(j, j + 1)) {
j++;
}
if (!less(k, j)) { break; }
k = j;
}
}
public MaxPQ(int maxN) {
pq = (Key[]) new Comparable[maxN + 1];
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void insert(Key v) {
pq[++N] = v;
swim(N);
}
public Key delMax() {
Key max = pq[1];
exch(1, N--);
pq[N + 1] = null;
sink(1);
return max;
}
}
优先队列的多向归并
public class Multiway {
public static void merge(In[] streams) {
int N = streams.length;
IndexMinPQ<String> pq = new IndexMinPQ<String>(N);
for(int i = 0; i < N; i++) {
if (!streams[i].isEmpty()) {
pq.insert(i, streams[i].readString());
}
}
while(!pq.isEmpty()) {
// StdOut.println(pq.min());
int i = pq.delMin();
if (!streams[i].isEmpty()) {
pq.insert(i, streams[i].readString());
}
}
}
public static void main(String[] args) {
int N = args.length;
In[] streams = new In[N];
for(int i = 0; i < N; i++) {
streams[i] = new In(args[i]);
}
merge(streams);
}
}
网友评论