1

好的，这是一个数据结构类。任务是编写一个程序，从 txt 文件中获取 100 个整数的列表，获取 2 组不同的 4 个间隔进行 shell 排序，然后对 100 个数字进行排序，1）通过插入排序，2）通过 shell 排序，首先4 个数字作为间隔，3）shell 按秒 100 作为间隔排序，将排序后的列表输出到 txt 文件，打印每个排序中发生的赋值操作的数量（还没有完成这部分）。

当我编译并运行其中一种 shell 排序时，尽管它已部分排序，但通常不能完全工作。没有完全排序的 shell 排序可能是任何一种排序，所以我假设程序以特定间隔工作，但不是其他时间间隔，这不好 :)。谁能帮忙

/**
 * @(#)Savit5.java
 *
 * Savit5 application
 *
 * @author
 * @version 1.00 2011/12/8
 */
 import java.util.*;
 import java.lang.*;
 import java.io.*;

public class Savit5 {

public static void main(String[] args) {

try {
    Scanner keyboardScanner = new Scanner(System.in);
    System.out.println("Please input the input file location:");
    String filePath = keyboardScanner.nextLine();
    Scanner scanner = new Scanner(new File(filePath));
    System.out.println("Please input 4 increment values for the first Shell Sort:");
    String shellOne = keyboardScanner.nextLine();
    System.out.println("Please input 4 increment values for the Second Shell Sort:");
    String shellTwo = keyboardScanner.nextLine();
    Scanner scanOne = new Scanner(shellOne);
    Scanner scanTwo = new Scanner(shellTwo);
    System.out.println("Please input the output file location:");
    String out = keyboardScanner.nextLine();
    int[] inc1 = new int[4];
        int q = 0;
        while (scanOne.hasNextInt()){
            inc1[q++] = scanOne.nextInt();
        }

    int[] inc2 = new int[4];
        int r = 0;
        while (scanTwo.hasNextInt()){
            inc2[r++] = scanTwo.nextInt();
        }

        int [] anArray = new int [100];
        int z = 0;
            while(scanner.hasNextInt()){
                anArray[z++] = scanner.nextInt();
            }
    int[] anArray2 = (int[])anArray.clone();
    int[] anArray3 = (int[])anArray.clone();
    int[] count = {0, 0, 0};
    int cnt=0;

    insertionSort(anArray, count, cnt);
    System.out.println("Assignment count:" + count[cnt]);
    cnt=1;
    shellSort(anArray2, inc1, count, cnt);
    System.out.println("Assignment count:" + count[cnt]);

    FileWriter output = new FileWriter(out);
    PrintWriter out2 = new PrintWriter(output);
    out2.println("Insertion Sort:");

    for (int i =0; i<anArray.length; i++) {
        out2.println(anArray[i]);
    }


    out2.println("Shell Sort 1:");
    for (int i =0; i<anArray2.length; i++) {
        out2.println(anArray2[i]);
    }

    out2.println("Shell Sort 2:");
    for (int i =0; i<anArray3.length; i++) {
        out2.println(anArray3[i]);
    }
    out2.close();
}
catch (IOException e)
{
    System.out.println (e);
}
}

public static void insertionSort(int[] a, int[] count, int cnt) {
    for (int i=1, j; i < a.length; i++) {
        int tmp = a[i];
        count[cnt] += 1;
        for (j = i - 1; j >= 0; j--) {
            if (a[j] <= tmp) break;
            a[j + 1] = a[j];
            count[cnt] += 1;
        }
        a[j + 1] = tmp;
        count[cnt] += 1;
    }
}


public static void shellSort(int[] a, int[] inc, int[] count, int cnt) {
for (int k =0; k<inc.length; k++) {
for (int i= inc[k], j; i < a.length; i+=inc[k]) {
    int tmp = a[i];
    count[cnt] +=1;
    for (j = i - inc[k]; j >= 0; j -= inc[k]) {
        if (a[j] <= tmp) break;
        a[j + inc[k]] = a[j];
        count[cnt] +=1;
    }
    a[j + inc[k]] = tmp;
    count[cnt] +=1;
   }
}
}


}
4

1 回答 1

1

我认为问题在于“inc”（如inc1）向量可能并不总是以1结尾。算法需要这一步，因为最后一次迭代应该像正常的插入排序（但要快得多，因为有几个元素会已经排序）。

如果是这种情况，您可以在代码中添加额外的检查。如果不是，请举个例子。

于 2011-12-09T18:01:53.837 回答