java - 实现双向选择排序的问题

Question

我正在尝试实现双向选择排序(双选择排序)。双选排序在扫描期间同时找到最小和最大的元素，并将最小的元素交换到第一个位置，将最大的元素交换到最后一个位置。然后算法继续查看第一个和最后一个之间的所有元素。

我能够获得执行任务所需的逻辑。但是，我认为我在比较变量或正确实现可比较方面做错了。

public void sort(T[] input) {

for(int i=0; i<input.length -1; i++){

    int min = i;
    int max = i;

    for(int j=i+1; j<input.length; j++){

        if(input[min].compareTo((input[j])) > 0  )
        {
            min = j;
            T swap = input[min];
            input[min] = input[i];
            input[i] = swap;

        }
    }

    for(int k=i+1; k<input.length; k++){

        if(input[max].compareTo((input[k])) < 0  )
        {
            max = k;
            T swap = input[max];
            input[max] = input[i];
            input[i] = swap;

        }
    }


}


}

/////测试文件

   /** Returns true if the input array is ordered (every element ≤ 
    * the following one.)
    * 
    * @param data Array to check
     * @return     True if array is ordered
     */
    boolean isOrdered(Integer[] data) {
    for(int i = 0; i < data.length - 1; ++i)
        if(data[i] > data[i+1])
            return false;

    return true;
}

/** Counts the number of times x occurs in the array in.
 * 
 * @param in Array
 * @param x  Element to count
 * @return   Count of x's in the array
 */
int countElement(Integer[] in, Integer x) {
    int c = 0;
    for(int i : in) 
        if(i == x)
            c++;

    return c;
}

/** Returns true if both arrays contain the same elements, 
 * disregarding order (i.e., is one a permutation of the other).
 * @param in  Unsorted array
 * @param out Potentially-sorted array to check
 * @return    True if out is a permutation of in
 */
boolean sameElements(Integer[] in, Integer[] out) {
    for(Integer i : in)
        if(countElement(in,i) != countElement(out,i))
            return false;

    return true;
}

/** Creates an array of the given size filled with random values.
 * 
 * @param size Size of the resulting array
 * @return     Array of random values
 */
Integer[] randomArray(int size) {
    Integer[] arr = new Integer[size];
    for(int i = 0; i < size; ++i)
        arr[i] = Math.round((float)Math.random() * Integer.MAX_VALUE);

    return arr;
}

/** Tests the DoubleSelectionSort dss against the unsorted data.
 * 
 * @param dss  Sorter to use
 * @param data Array to sort and check
 */
void testSort(DoubleSelectionSort dss, Integer[] data) {
    Integer[] sorted = Arrays.copyOf(data, data.length);
    dss.sort(sorted);        

    assertTrue("Result of sort is not sorted in order", isOrdered(sorted));
    assertTrue("Result of sort has different elements from input", sameElements(data, sorted));
}

@Test
public void testSort() {
    System.out.println("sort");
    DoubleSelectionSort<Integer> dss = new DoubleSelectionSort<>();

    // Test on arrays size 0 to 100
    for(int i = 0; i <= 100; ++i)
        testSort(dss, randomArray(i));               
  }

}

testSort 失败:排序结果未按顺序排序

Answer 1

您似乎在选择排序的排序逻辑中使用了错误的条件。我在这里给出了具有 generic 类型的 Selection Sort 函数的示例。请看一下这个:

public static <E extends Comparable<E>> void selectionSort(E[] list)
{
    for(int i=0; i<list.length -1; i++)
    {
        int iSmall = i;

        for(int j=i+1; j<list.length; j++)
        {
            if(list[iSmall].compareTo((list[j])) > 0  )
            {
                iSmall = j;
            }
        }
        E iSwap = list[iSmall];
        list[iSmall] = list[i];
        list[i] = iSwap;

    }
}