问题
创建一个程序来对链表执行归并排序。
规范
- 创建一个包含 1-1000 范围内的 100 个随机整数的链表。
- 在 10 x 10 的表格中显示未排序的链表。
使用合并排序例程对链表进行排序:
- 将链表转换为数组。
- 对数组执行递归合并排序。
- 当分区的大小低于某个阈值时，将合并排序算法更改为使用非递归算法(选择排序、插入排序)。
- 在合并排序例程中插入一条评论，解释您选择选择排序、插入排序或其他一些非递归算法的原因，以及您如何决定(经验证据)阈值。
- 排序完成后，将数组转换回链表。
- 在 10 x 10 的表格中显示排序后的链表。
到目前为止我的代码:
public class MergeSort{
LinkedQueue<Integer> list = new LinkedQueue<Integer>();
Integer[] a = new Integer[100];
public MergeSort() {
for(int i=0; i<100; i++)
{
list.enqueue(StdRandom.uniform(999)+1);
}
}
private static boolean less(Comparable v, Comparable w)
{
return (v.compareTo(w) < 0);
}
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 sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
if((hi-lo) <= 6)
{
Comparable[] b = new Comparable[hi-lo];
for(int i=0; i<b.length; i++)
{
b[i] = a[lo+i];
}
Selection.sort(b);
for(int i=0; i<(hi-lo); i++)
{
a[lo+i] = b[i];
}
return;
}
int mid = lo + (hi - lo)/2;
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);
}
public void sort(Comparable[] a)
{
Comparable[] aux = new Comparable[a.length];
sort(a, aux, 0, a.length-1);
}
public static void main(String[] args)
{
MergeSort merge = new MergeSort();
StdOut.println("Unsorted: ");
for(int i=0; i<10; i++)
{
for(int j=0; j<10; j++)
{
StdOut.print(merge.list.peek() + " ");
merge.a[i*10 + j] = merge.list.dequeue();
}
StdOut.println();
}
StdOut.println();
merge.sort(merge.a);
for(int i=0; i<100; i++)
{
merge.list.enqueue(merge.a[i]);
}
StdOut.println("Sorted: ");
for(int i=0; i<10; i++)
{
for(int j=0; j<10; j++)
{
StdOut.print(merge.list.dequeue() + " ");
}
StdOut.println();
}
}
}
我的问题是数组似乎只得到了部分排序。前半部分排序很好，但在后半部分左右，它开始只对所有其他项目进行排序，而其他项目似乎是随机的。这是一个输出示例:
Unsorted:
580 314 331 643 597 587 798 980 87 53
526 787 993 336 552 338 950 460 441 566
428 115 670 28 384 596 781 489 630 91
272 563 428 644 696 120 538 729 477 637
196 564 784 770 702 56 992 413 753 266
847 751 659 426 59 738 185 589 650 636
849 437 361 519 980 723 973 217 414 548
337 935 656 944 485 233 431 170 327 832
53 236 447 184 842 286 303 153 697 713
303 64 268 725 229 127 517 15 427 372
Sorted:
15 28 53 53 56 59 64 87 91 115
120 127 170 184 196 217 229 233 268 272
286 303 303 314 327 331 336 337 338 413
426 427 428 428 431 437 447 460 477 489
517 372 519 526 538 548 552 564 566 580
587 589 596 597 630 636 637 643 644 650
656 659 670 384 696 697 702 713 723 725
729 738 751 753 781 563 784 770 787 798
832 236 842 153 847 185 849 361 935 944
485 950 441 973 980 980 414 992 266 993
我相信我已经将问题缩小到递归排序方法的基本情况:
if((hi-lo) <= 6)
{
Comparable[] b = new Comparable[hi-lo];
for(int i=0; i<b.length; i++)
{
b[i] = a[lo+i];
}
Selection.sort(b);
for(int i=0; i<(hi-lo); i++)
{
a[lo+i] = b[i];
}
return;
}
每当我用 if(hi <= lo) return 替换它时；基本合并排序标准的基本情况，一切正常。那么，任何人都可以帮助我解决这个问题，或者发现代码中的错误吗？此外，如果您能就为什么我应该在选择上使用另一种非递归排序方法这一问题给我任何建议，我们将不胜感激。
根据 Kraskevich 的要求，选择类的源代码:
import java.util.Comparator;
/**
* The <tt>Selection</tt> class provides static methods for sorting an
* array using selection sort.
* <p>
* For additional documentation, see <a href="http://algs4.cs.princeton.edu/21elementary">Section 2.1</a> of
* <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class Selection {
// This class should not be instantiated.
private Selection() { }
/**
* Rearranges the array in ascending order, using the natural order.
* @param a the array to be sorted
*/
public static void sort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int min = i;
for (int j = i+1; j < N; j++) {
if (less(a[j], a[min])) min = j;
}
exch(a, i, min);
assert isSorted(a, 0, i);
}
assert isSorted(a);
}
/**
* Rearranges the array in ascending order, using a comparator.
* @param a the array
* @param c the comparator specifying the order
*/
public static void sort(Object[] a, Comparator c) {
int N = a.length;
for (int i = 0; i < N; i++) {
int min = i;
for (int j = i+1; j < N; j++) {
if (less(c, a[j], a[min])) min = j;
}
exch(a, i, min);
assert isSorted(a, c, 0, i);
}
assert isSorted(a, c);
}
/***********************************************************************
* Helper sorting functions
***********************************************************************/
// is v < w ?
private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}
// is v < w ?
private static boolean less(Comparator c, Object v, Object w) {
return (c.compare(v, w) < 0);
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
/***********************************************************************
* Check if array is sorted - useful for debugging
***********************************************************************/
// is the array a[] sorted?
private static boolean isSorted(Comparable[] a) {
return isSorted(a, 0, a.length - 1);
}
// is the array sorted from a[lo] to a[hi]
private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}
// is the array a[] sorted?
private static boolean isSorted(Object[] a, Comparator c) {
return isSorted(a, c, 0, a.length - 1);
}
// is the array sorted from a[lo] to a[hi]
private static boolean isSorted(Object[] a, Comparator c, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(c, a[i], a[i-1])) return false;
return true;
}
// print array to standard output
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
StdOut.println(a[i]);
}
}
/**
* Reads in a sequence of strings from standard input; selection sorts them;
* and prints them to standard output in ascending order.
*/
public static void main(String[] args) {
String[] a = StdIn.readAllStrings();
Selection.sort(a);
show(a);
}
}
最佳答案
错误很简单:lo 和 hi 索引包含在内。这就是为什么它应该是:
if (hi - lo) <= 6) {
Comparable[] b = new Comparable[hi - lo + 1];
// ^^^^
// We need plus one here.
for (int i = 0; i < b.length; i++) {
b[i] = a[lo + i];
}
Selection.sort(b);
for (int i = 0; i < b.length; i++) {
// ^^^^
// We should either iterate to hi - lo + 1 or b.length.
a[lo + i] = b[i];
}
return;
}
关于java - 使用非递归排序阈值的合并排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28751926/