-6

我想到了新的排序算法，但我无法理解明显解决方案中的问题：

public int[] sort(int[] arr){

    //Find the biggest number in the array
    int max=1;
    for(int i : arr)
        if(i>max)
            max=i;

    //Sorting the figures into big array
    int[] LongSorted= new int[max+1];
    for(int i=1; i<LongSorted.length; i++)
        LongSorted[i]=0;
    for(int i : arr)
        LongSorted[i]+=i;

    //Transfer the sorted figures into the original array
    int index=0;
    for(int i=0; i<arr.length; i++){
        while(LongSorted[index]==0){
            index++;
        }
        arr[i]=index;
        if(LongSorted[index]!=(index)){
            for(int j=0; j<(LongSorted[index]/index)-1; j++){
                i++;
                arr[i]=index;
            }
        }
        index++;
    }

    return arr;
}

基本上，该算法使用图形的值作为索引。

如果您想使用此方法，请注意不考虑数字“0”。
您可以按照以下说明进行更正：
1。将 LongSorted 类型更改为“整数”。
2 . 将 LongSorted 的初始化“for”中的“i”的值更改为“1”。
3 . 在最后一个“for”之前的前一行，添加以下条件：

       if(LongSorted[0]!=null)
          arr[0]=0;

4 . 将最后一个“for”中的“i”的值更改为“1”。
天呐！

4

2 回答 2

3

如果这应该是有效的 - 它不是。首先，您多次循环遍历各种数组。其中一些不是必需的，它们会减慢算法处理大量数据的速度。

其次，如果您尝试对以下列表进行排序会发生什么？[1; 1000000000]

您最终将创建一个大小为 10 亿+1 的数组，只是为了对两个数字进行排序。那是 40 亿字节。

最后，如果有重复的元素会发生什么？

然后正如评论中指出的那样，这将在负数上失败。

如果您完全是自己提出这个想法，并且是编程新手，那么您实际上走在了真正重要的正确轨道上——一个Hashtable。

于 2012-12-15T22:13:37.580 回答
0

我必须出手相救：

诚然，这取决于该算法是否有效，并且它仅涵盖 > 0 的正值。但这是一个好主意，并且在边界情况下可能非常有效。

我重写了它，使其更易于阅读，仍然使用就地排序：

public static int[] sort(int[] arr) {

    // Find the biggest number in the array
    int max = 1;
    for (int i : arr) {
        if (i > max) {
            max = i;
        }
    }

    // Sorting the figures into big array
    // indexOccurrences[i] is how often the value i occures in arr.
    int[] indexOccurrences = new int[max + 1];
    for (int i : arr) {
        ++indexOccurrences[i];
    }

    // Transfer the sorted figures into the original array
    int arrIndex = 0;
    for (int j = 1; j < indexOccurrences.length; ++j) {
        for (int k = 0; k < indexOccurrences[j]; ++k) {
            arr[arrIndex] = j;
            ++arrIndex;
        }
    }
    assert arrIndex == arr.length;
    return arr;
}

public static void main(String[] args) {
    int[] values = new int[] { 23, 6, 67, 6, 6, 45, 3 };
    values = sort(values);
    System.out.println(Arrays.toString(values));
}

[3、6、6、6、23、45、67]

顺便说一句，这个想法并不新鲜，但这可能被视为对它的支持。

于 2012-12-15T22:38:20.767 回答