实现双向选择排序的问题
Problem with implementing bi-directional selection sort
我正在尝试实现双向选择排序(双重选择排序)。
双选排序在其扫描过程中同时找到最小和最大元素,并将最小元素交换到第一个位置,将最大元素交换到最后一个位置。然后算法继续查看第一个和最后一个之间的所有元素。
我能够获得执行 task.But 所需的逻辑,我认为我在比较变量或可能正确实施可比较方面做错了。
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 失败:排序结果未按顺序排序
您似乎在 Selection Sort
的排序逻辑中使用了错误的条件。
我在这里给出了 Selection Sort
函数和 generic
类型的例子。请看这个:
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;
}
}
我正在尝试实现双向选择排序(双重选择排序)。 双选排序在其扫描过程中同时找到最小和最大元素,并将最小元素交换到第一个位置,将最大元素交换到最后一个位置。然后算法继续查看第一个和最后一个之间的所有元素。
我能够获得执行 task.But 所需的逻辑,我认为我在比较变量或可能正确实施可比较方面做错了。
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 失败:排序结果未按顺序排序
您似乎在 Selection Sort
的排序逻辑中使用了错误的条件。
我在这里给出了 Selection Sort
函数和 generic
类型的例子。请看这个:
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;
}
}