选择排序变不工作 [英] SelectionSort variation not working

问题描述

我要实现根据这些参数的选择排序在Java中：

  

需要实现为分别位于两个最小和最大的元素在扫描列表中，并在开始和列表的末尾位置。其中，选择排序的变化。在通球王元素X0，...，XN-1进行扫描;上通第二，元件X1，...，XN-2进行扫描;等

我传递的方法大小为32的数组，当我打印数组是没有排序。什么是我的code回事？

 静态无效的选择排序（）{
    争夺（）;
    INT smallIndex = 0; //最小的指数，以测试
    INT largeIndex = array.length  -  1; //最大的指数，以测试
    INT小= 0; //最小
    INT大; //最大
    INT smallLimit = 0; //从这里开始
    INT largeLimit = array.length  -  1; //到此为止
    INT店; //临时存放在这里
    INT商店2;    的for（int i = 0; I＆LT; array.length / 2;我++）{// TODO不工作...
        小=阵列[smallLimit]
        大阵= [largeLimit]
        对于（INT J = smallLimit; J＆LT; = largeLimit; J ++）{
            如果（阵列[J]＆LT;小）{
                smallIndex = j的;
                小=阵列[J]。
            }
            否则，如果（阵列[J]＆GT;大）{
                largeIndex = j的;
                大阵= [J]。
            }
        }
        存储阵列= [smallLimit]
        商店2 =阵列[smallIndex]
        数组[smallLimit] =商店2;
        数组[smallIndex] =店;
        存储阵列= [largeLimit]
        数组[largeLimit] =阵列[largeIndex]
        数组[largeIndex] =店;
        smallLimit ++;
        largeLimit--;
    }
    打印（）;
}
 

解决方案

想想极端的情况：当最大或最小的项目是在 smallLimit 或发现会发生什么 largeLimit 。当发生这种情况，你有两个问题：

1. largeIndex 和 smallIndex 未设置。他们坚持自己的价值观从previous迭代。


2. 交换的最小项目的适当位置移动最大的项目。第二交换移动，其中最大应该最小的项目，并在一个随机位置最大结束。通过在纸上或在调试器中的code步骤，如果你觉得这很难想象。

这些问题都容易解决。你可能避免问题以下几条原则：

• 使用更少的可移动部件。你总是可以得到的小使用 smallIndex ，如果你只是使用 smallIndex 就不会有不同的变量闹翻一步的危险。


• 声明在尽可能小的范围内的变量。如果 smallIndex 在循环体被宣布，而不是外部的编译器会告诉你有它不交换之前设置一个机会。

喜欢这里的第一个交换
• 破坏性的更新总是可以使一个previous计算过时。当你不能避免这种情况发生，想办法两个更新可以在对方的脚趾一步。

I have to implement a Selection Sort in Java according to these parameters:

Implement a variation to the SelectionSort that locates both the smallest and largest elements while scanning the list and positions them at the beginning and the end of the list, respectively. On pass number one, elements x0,...,xn-1 are scanned; on pass number two, elements x1,...,xn-2 are scanned; and so on.

I am passing the method an array of size 32, and when I print the array it is not sorted. What's the matter with my code?

static void selectionSort() {
    scramble();
    int smallIndex = 0;  //index of smallest to test
    int largeIndex = array.length - 1;  //index of largest to test
    int small = 0;  //smallest
    int large;  //largest
    int smallLimit = 0;  //starts from here
    int largeLimit = array.length - 1;  //ends here
    int store;  //temp stored here
    int store2;

    for(int i = 0; i < array.length/2; i++) {  //TODO not working...
        small = array[smallLimit];
        large = array[largeLimit];
        for(int j = smallLimit; j <= largeLimit; j++) {
            if(array[j] < small) {
                smallIndex = j;
                small = array[j];
            }
            else if(array[j] > large) {
                largeIndex = j;
                large = array[j];
            }
        }
        store = array[smallLimit];
        store2 = array[smallIndex];
        array[smallLimit] = store2;
        array[smallIndex] = store;
        store = array[largeLimit];
        array[largeLimit] = array[largeIndex];
        array[largeIndex] = store;
        smallLimit++;
        largeLimit--;
    }
    print();    
}

解决方案

Think about the extreme cases: what happens when the largest or smallest item is found at smallLimit or largeLimit. When that happens you have two problems:

1. largeIndex and smallIndex are not set. They maintain their values from a previous iteration.
2. Swapping the smallest item to its correct place moves the largest item. The second swap moves the smallest item where the largest should go, and the largest ends up in a random location. Step through the code on paper or in a debugger if you find this hard to visualize.

These problems are easy to fix. You could have avoided the problem following a few guidelines:

• Use fewer moving parts. You can always get the value of small using smallIndex, if you just used smallIndex there would be no danger of different variables falling out of step.
• Declare the variables in the smallest possible scope. If smallIndex was declared in the loop body and not outside the compiler would have told you there's a chance it was not set before the swap.
• Destructive updates like the first swap here can always make a previous calculation obsolete. When you can't avoid this from happening, look for ways two updates can step on each other's toes.

这篇关于选择排序变不工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！