在不import任何东西并且限制交换次数的情况下做HeapSort和MergeSort？

Question

在不import任何东西的情况下如何在有限制的情况下做HeapSort和MergeSort

比如说我的开头是

public static void heapSort(int[] a, int d)

a做为一个随机的一组array只会有int在里面d作为Locality-aware value意味着这这个array a里面每个element不能移动超过d位

如图所示。

而且会发生d的值比arr的长度长的情况。

同理MergeSort又要怎么实现呢？

public static void mergeSort(int[] a, int d)

以下为具体要求（可自行翻译）：

Guidelines for in-place Heapsort:
● If you do this in place, the overall algorithm becomes a little trickier. You can use
the sliding window idea, but this time everything in the window should be sorted
before you move on to the next window.
● You need to consider how big the window should be.
● You also need to consider how far to “slide” the window after you’re done sorting
it.
● Since this is done in place, you will not need both sink and swim because you
can do your heap construction bottom up using sink, which is also used in
sortDown. To get all the extra credit, you should do it this way, which is more
efficient than doing top-down heap construction.
● The runtime of this implementation should not be worse than O（N/d log d)

Locality-Aware Mergesort. In regular Mergesort, we divide the array into smaller
arrays (until we only have 1-element arrays, which are sorted), then merge the smaller
arrays together. This is a recursive algorithm. If the array is locality-aware, you don’t
have to sort the entire array all at once. Instead, you can use the “sliding window”
method where you sort part of the array, then slide the window and sort the next set of
elements. The questions you need to consider are: How big should the sliding window
be? and How much do I slide the window by after sorting?
Guidelines for Mergesort:
● The runtime for this implementation should not be worse than O(Nlogd).
● To get full credit here, you should only use one temporary array for the whole
method. Do not create new arrays each time you call Mergesort.

 

Answer 1

import java.util.Random;

public class ArrayGen {
    public static int[] genSortAsc(int n) {
	Random gen = new Random(System.currentTimeMillis());
	int[] array = new int[n];
	int val = gen.nextInt(10);
	array[0] = val;
	for(int i = 1; i < n; i++) 
	    array[i] = array[i-1] + gen.nextInt(10);
	return array;
    }

    public static int[] genSortDesc(int n) {
	Random gen = new Random(System.currentTimeMillis());
	int[] array = new int[n];
	int val = gen.nextInt(1000) - 500;
	array[0] = val;
	for(int i = 1; i < n; i++)
	    array[i] = array[i-1] - gen.nextInt(10);
	return array;
    }

    public static int[] getRand(int n, int d) {
	int[] array = genSortAsc(n);
	shuffle(array, d);
	return array;
    }

    private static void shuffle(int[] array, int d) {
	boolean[] moved = new boolean[array.length];
	Random gen = new Random(System.currentTimeMillis());
	for(int i = 0; i < array.length; i++) {
	    int shift = gen.nextInt(2*d+1) - d;
	    if(shift != 0 && i + shift >= 0 && i + shift < array.length && !moved[i] && !moved[i+shift]) {
		swap(array, i, i + shift);
		moved[i] = true;
		moved[i+shift] = true;
	    }
	}
    }

    private static void swap(int[] array, int i, int j) {
	if (i != j) {
	    int temp = array[i];
	    array[i] = array[j];
	    array[j] = temp;
	}
    }
}

此程序可以自动生成Arr

import java.util.Arrays;
import java.util.Random;

public class LocSortTest {
    //test values
    private static int[] sizes = new int[] {10, 25, 100, 250, 1250, 5000, 10000, 50, 15000, 20000};
    private static int[] dVals = new int[] {3, 7, 15, 30, 10, 50, 10, 55, 15, 25};

    private static int singleTest = 2;
    
    public static void main(String[] args) {
	int score = 0;
	score += testHeapSort();
	score += testMergeSort();
	System.out.println("\n\nExpected Score: " + score);
    }


    private static int testHeapSort() {
	System.out.println("\n***Testing HeapSort***");
	int score = 0;
	for(int i = 0; i < sizes.length; i++) {
	    System.out.println("\nTesting on array of size " + sizes[i] + " with d = " + dVals[i] + "...");
	    int[] array = ArrayGen.getRand(sizes[i], dVals[i]);
	    int[] copy = copyArray(array);
	    Arrays.sort(copy);
	    LocSort.heapSort(array, dVals[i]);
	    if(isSorted(array, copy))
		score += singleTest;
	}
	return score;
    }

    private static int testMergeSort() {
	System.out.println("\n***Testing MergeSort***");
	int score = 0;
	for(int i = 0; i < sizes.length; i++) {
	    System.out.println("\nTesting on array of size " + sizes[i] + " with d = " + dVals[i] + "...");
	    int[] array = ArrayGen.getRand(sizes[i], dVals[i]);
	    int[] copy = copyArray(array);
	    Arrays.sort(copy);
	    LocSort.mergeSort(array, dVals[i]);
	    if(isSorted(array, copy))
		score += singleTest;
	}
	return score;
    }

    private static int[] copyArray(int[] array) {
	int[] a = new int[array.length];
	for(int i = 0; i < array.length; i++)
	    a[i] = array[i];
	return a;
    }

    private static boolean isSorted(int[] array1, int[] array2) {
	System.out.println("Comparing the contents of the array to the expected contents...");
	if(array1.length != array2.length) {
	    System.out.println("Array lengths do not match.");
	    return false;
	}
	for(int i = 0; i < array1.length; i++) {
	    if(array1[i] != array2[i]) {
		System.out.println("Elements do not match at index " + i + ".");
		System.out.println("Expected: " + array2[i]);
		System.out.println("Actual: " + array1[i]);
		return false;
	    }
	}
	System.out.println("Arrays match!");
	return true;
    }
}

此程序可以检测对错