java - 按减法排序

Question

所以我正在用java研究这个排序算法，并且想知道是否有人以前见过类似的东西。具体来说，该算法旨在对具有非常小的数字范围的非常大的列表进行排序。如果您看到了这一点或对增强算法有任何建议，您能在下面说些什么吗？我这里有代码:

public static int[] sort(int[] nums)
{   
    int lowest = Integer.MAX_VALUE;

    for (int n : nums)
    {
        if (n < lowest)
            lowest = n;
    }

    int index = 0;

    int down = 0;

    while (index < nums.length)
    {
        for (int i = index; i < nums.length; i++)
        {
            if (nums[i] == lowest)
            {
                int temp = nums[i] + down;
                nums[i] = nums[index];
                nums[index] = temp;

                index++;
            }
            else 
                nums[i]--;
        }
        down++;
    }

    return nums;
}

Answer 1

如果我没记错的话，这就是标准问题的冒泡排序。实现简单，但性能较差:O(n^2)。注意两个嵌套循环:随着数组大小的增加，算法的运行时间将呈指数增长。

之所以命名为冒泡排序，是因为最小值会一次一个地“冒泡”到数组的前面。您可以阅读更多相关信息on Wikipedia .