合并排序算法不适用于大型数据集

Question

我正在研究合并排序算法，但找不到我的错误。输出大部分是排序的，直到它随机列出几个整数的末尾：

1 2 3 4 5 6 7 8 9 10 11 12 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 31 32 33 34 35 36 37 38 39 40 41 42 43 44 47 486 4 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 84 85 86 87 88 89 90 91 92 93 95 96 97 98 99 100 30 13 14 83 94

    

    public static void main(String args[]) throws IOException {



        Scanner scan = new Scanner(System.in);
        System.out.println("Enter dataset size: ");
        int size = scan.nextInt();
        String file = "" + size + ".txt";
        
        scan.close();
        Scanner scanner = new Scanner(new File(file));
        
        
        

        // read numbers from text file into the array
        // set array size to the user input size
        // while loop reads text file until each int is read
        int array[] = new int[size];
        int i = 0;
        while(scanner.hasNext()) {
            array[i++] = scanner.nextInt();
        }
        scanner.close();
        
        
        
        
        // create 4 copies of the array to test each in a separate algorithm
        int array1[] = new int[size];
        int array2[] = new int[size];
        int array3[] = new int[size];
        int array4[] = new int[size];
        for (int j = 0; j < array.length; j++) {
            array1[j] = array[j];
            array2[j] = array[j];
            array3[j] = array[j];
            array4[j] = array[j];
        }
        
        

        
        // test bubble sort
        // this inputs the array and outputs time taken to compute
        bubbleSort(array1);
        

        // test selection sort
        // this inputs the array and outputs time taken to compute
        selectionSort(array2);


        
        
        //quickSort(array3, 0, array3[array3.length-1]);
        
        // test merge sorting algorithm

        mergeSort(array4, 0, array4[array4.length-1]);

        

        System.out.println();
        for (int k = 0; k<array4.length; k++) {
            System.out.print(array4[k] + " ");
        }

        
        

    }

public static void mergeSort(int arr[], int start, int end) {
        if (start < end) {
            int mid = (start + end)/2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid+1, end);
            merge(arr, start, mid, end);
        }

    }
    
    
    private static void merge(int arr[], int start, int mid, int end) {
        int n1 = mid - start + 1;
        int n2 = end - mid;
        int left[] = new int[n1];
        int right[] = new int[n2];
        for (int i = 0; i <n1; i++) {
            left[i] = arr[start+i];
        }
        for (int j = 0; j < n2; j++) {
            right[j] = arr[mid + 1 + j];
        }
        
        int i = 0; 
        int j = 0; 
        int k = start;
        
        while (i < n1 && j < n2) {
            if (left[i] <= right[j]) {
                arr[k] = left[i];
                i++;
            } else {
                arr[k] = right[j];
                j++;
            }
            k++;
        }
        
        while (i < n1) {
            arr[k] = left[i];
            i++;
            k++;
        }
        
        while (j < n2) {
            arr[k] = right[j];
            j++;
            k++;
        }

    }

Answer 1

问题在于您如何调用 mergeSort:

// test merge sorting algorithm
mergeSort(array4, 0, array4[array4.length-1]);

尝试将 array4[array4.length-1] 替换为 array4.length-1。

合并排序算法不适用于大型数据集

Mergesort Algorithm isn't working for large datasets

java

sorting

algorithm

merge

mergesort