▶ 书中第二章部分程序，加上自己补充的代码，包括若干种归并排序，以及利用归并排序计算数组逆序数
● 归并排序
package package01; import java.util.Comparator;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut; public class class01
{
private class01() {} private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) // 归并两个排好序的子数组
{
for (int k = lo; k <= hi; k++)
aux[k] = a[k]; int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++)
{
if (i > mid) // 后段剩余
a[k] = aux[j++];
else if (j > hi) // 前段剩余
a[k] = aux[i++];
else if (less(aux[j], aux[i])) // 比较
a[k] = aux[j++];
else
a[k] = aux[i++];
}
} private static void sortTDKernel(Comparable[] a, Comparable[] aux, int lo, int hi) // 排序递归内核
{
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
sortTDKernel(a, aux, lo, mid);
sortTDKernel(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
} public static void sortTD(Comparable[] a) // 自顶向下的归并排序
{
Comparable[] aux = new Comparable[a.length]; // 统一分配临时内存
sortTDKernel(a, aux, 0, a.length - 1);
} private static void indexMerge(Comparable[] a, int[] index, int[] aux, int lo, int mid, int hi) // 间接排序的归并
{
for (int k = lo; k <= hi; k++)
aux[k] = index[k]; int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++)
{
if (i > mid)
index[k] = aux[j++];
else if (j > hi)
index[k] = aux[i++];
else if (less(a[aux[j]], a[aux[i]]))
index[k] = aux[j++];
else
index[k] = aux[i++];
}
} private static void indexSortTDKernel(Comparable[] a, int[] index, int[] aux, int lo, int hi) // 间接排序递归内核
{
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
indexSortTDKernel(a, index, aux, lo, mid);
indexSortTDKernel(a, index, aux, mid + 1, hi);
indexMerge(a, index, aux, lo, mid, hi);
} public static int[] indexSortTD(Comparable[] a) // 自顶向下的间接归并排序
{
int n = a.length;
int[] aux = new int[n];
int[] index = new int[n];
for (int i = 0; i < n; i++)
index[i] = i; indexSortTDKernel(a, index, aux, 0, n - 1);
return index;
} public static void sortBU(Comparable[] a) // 自底向上的归并排序，不需要递归，合并子数组的函数与前面相同
{
int n = a.length;
Comparable[] aux = new Comparable[n];
for (int len = 1; len < n; len *= 2)
{
for (int lo = 0; lo < n - len; lo += len + len)
{
int mid = lo + len - 1;
int hi = Math.min(lo + len + len - 1, n - 1);
merge(a, aux, lo, mid, hi);
}
}
} // 改良版本
private static final int CUTOFF = 7; // 小于该尺寸的数组使用插入排序 private static void merge2(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) // 区分原数组和目标数组，减少拷贝
{
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++)
{
if (i > mid)
dst[k] = src[j++];
else if (j > hi)
dst[k] = src[i++];
else if (less(src[j], src[i]))
dst[k] = src[j++];
else
dst[k] = src[i++];
}
} private static void sort2TDKernel(Comparable[] src, Comparable[] dst, int lo, int hi)
{
if (hi <= lo + CUTOFF) // 数据较少时使用插入排序
{
insertionSort(dst, lo, hi);
return;
}
int mid = lo + (hi - lo) / 2;
sort2TDKernel(dst, src, lo, mid);
sort2TDKernel(dst, src, mid + 1, hi); if (!less(src[mid + 1], src[mid])) // src[mid+1] >= src[mid]，不用归并了
System.arraycopy(src, lo, dst, lo, hi - lo + 1); // 数组拷贝，快于 for (int i = lo; i <= hi; i++) dst[i] = src[i];
else
merge2(src, dst, lo, mid, hi);
} public static void sort2TD(Comparable[] a)
{
Comparable[] aux = a.clone();
sort2TDKernel(aux, a, 0, a.length - 1);
} private static void insertionSort(Comparable[] a, int lo, int hi)
{
for (int i = lo; i <= hi; i++)
{
for (int j = i; j > lo && less(a[j], a[j - 1]); j--)
exch(a, j, j - 1);
}
} private static void exch(Comparable[] a, int i, int j) // 插入排序用到的交换
{
Comparable swap = a[i];
a[i] = a[j];
a[j] = swap;
} private static void merge2(Object[] src, Object[] dst, int lo, int mid, int hi, Comparator comparator) // 自定义类型的版本（同上 5 个函数）
{
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++)
{
if (i > mid)
dst[k] = src[j++];
else if (j > hi)
dst[k] = src[i++];
else if (less(src[j], src[i], comparator))
dst[k] = src[j++];
else
dst[k] = src[i++];
}
} private static void sort2TDKernel(Object[] src, Object[] dst, int lo, int hi, Comparator comparator)
{
if (hi <= lo + CUTOFF)
{
insertionSort(dst, lo, hi, comparator);
return;
} int mid = lo + (hi - lo) / 2;
sort2TDKernel(dst, src, lo, mid, comparator);
sort2TDKernel(dst, src, mid + 1, hi, comparator); if (!less(src[mid + 1], src[mid], comparator))
System.arraycopy(src, lo, dst, lo, hi - lo + 1);
else
merge2(src, dst, lo, mid, hi, comparator);
} public static void sort2TD(Object[] a, Comparator comparator)
{
Object[] aux = a.clone();
sort2TDKernel(aux, a, 0, a.length - 1, comparator);
} private static void insertionSort(Object[] a, int lo, int hi, Comparator comparator)
{
for (int i = lo; i <= hi; i++)
{
for (int j = i; j > lo && less(a[j], a[j - 1], comparator); j--)
exch(a, j, j - 1);
}
} private static void exch(Object[] a, int i, int j)
{
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
} private static boolean less(Comparable a, Comparable b) // 各排序都用到的比较函数
{
return a.compareTo(b) < 0;
} private static boolean less(Object a, Object b, Comparator comparator) // 自定义类型的比较函数
{
return comparator.compare(a, b) < 0;
} private static void show(Comparable[] a)
{
for (int i = 0; i < a.length; i++)
StdOut.println(a[i]);
} public static void main(String[] args)
{
String[] a = StdIn.readAllStrings();
//int[] index = class01.indexSortTD(a); class01.sortTD(a);
//class01.sortBU(a);
//class01.sort2TD(a);
//for (int i = 0; i<a.length; i++)
// StdOut.println(index[i]);
System.out.printf("\nFinish!\n");
}
}
● 利用归并排序来计算数组的逆序数，只注释了与归并排序不一样的地方
package package01; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut; public class class01
{
private class01() {} private static long merge(int[] a, int[] aux, int lo, int mid, int hi) // 限定输入为 int 数组
{
long inversions = 0; for (int k = lo; k <= hi; k++)
aux[k] = a[k]; int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++)
{
if (i > mid)
a[k] = aux[j++];
else if (j > hi)
a[k] = aux[i++];
else if (aux[j] < aux[i]) // 算术比较
{
a[k] = aux[j++];
inversions += (mid - i + 1); // 多了一步计算
}
else
a[k] = aux[i++];
}
return inversions; // 返回逆序数
} private static long count(int[] a, int[] b, int[] aux, int lo, int hi) // 部分计数函数
{
long inversions = 0;
if (hi <= lo)
return 0;
int mid = lo + (hi - lo) / 2;
inversions += count(a, b, aux, lo, mid); // 分治和归并的部分补上计算
inversions += count(a, b, aux, mid + 1, hi);
inversions += merge(b, aux, lo, mid, hi);
return inversions;
} public static long count(int[] a) // 可调用的计数函数
{
int[] b = new int[a.length];
int[] aux = new int[a.length];
for (int i = 0; i < a.length; i++)
b[i] = a[i];
return count(a, b, aux, 0, a.length - 1);
} private static long brute(int[] a, int lo, int hi) // 枚举方法计算逆序数
{
long inversions = 0;
for (int i = lo; i <= hi; i++)
{
for (int j = i + 1; j <= hi; j++)
if (a[j] < a[i])
inversions++;
}
return inversions;
} // 自定义类型版本
private static <Key extends Comparable<Key>> long merge(Key[] a, Key[] aux, int lo, int mid, int hi)
{
long inversions = 0; for (int k = lo; k <= hi; k++)
aux[k] = a[k]; int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++)
{
if (i > mid)
a[k] = aux[j++];
else if (j > hi)
a[k] = aux[i++];
else if (less(aux[j], aux[i])) // 比较方法改回去了
{
a[k] = aux[j++];
inversions += (mid - i + 1);
}
else
a[k] = aux[i++];
}
return inversions;
} private static <Key extends Comparable<Key>> boolean less(Key v, Key w)
{
return (v.compareTo(w) < 0);
} private static <Key extends Comparable<Key>> long count(Key[] a, Key[] b, Key[] aux, int lo, int hi)
{
long inversions = 0;
if (hi <= lo)
return 0;
int mid = lo + (hi - lo) / 2;
inversions += count(a, b, aux, lo, mid);
inversions += count(a, b, aux, mid + 1, hi);
inversions += merge(b, aux, lo, mid, hi);
return inversions;
} public static <Key extends Comparable<Key>> long count(Key[] a)
{
Key[] b = a.clone();
Key[] aux = a.clone();
return count(a, b, aux, 0, a.length - 1);
} private static <Key extends Comparable<Key>> long brute(Key[] a, int lo, int hi)
{
long inversions = 0;
for (int i = lo; i <= hi; i++)
{
for (int j = i + 1; j <= hi; j++)
if (less(a[j], a[i]))
inversions++;
}
return inversions;
} public static void main(String[] args) // 使用文件名而不是重定向来作为输入
{
In in = new In(args[0]);
int[] a = in.readAllInts();
int n = a.length;
int[] b = new int[n];
for (int i = 0; i<n; i++)
b[i] = a[i]; StdOut.println(class01.count(a));
StdOut.println(class01.count(b));
}
}