查找数字数组中两个最近元素之间的距离

所以我正在自学我购买的这本书中的算法，并且我有一个伪代码用于查找数字数组中两个最近元素之间的距离

MinDistance(a[0...n-1])
Input: Array A of numbers
Output: Minimum Distance between two of its elements
dMin <- maximum integer

for i=0 to n-1 do
   for j=0 to n-1 do
      if i!=j and | A[i] - A[j] | < dMin
        dMin = | A[i]-A[j] |
return dMin

然而，我想对这个算法解决方案进行改进。更改已有的内容，或者一起重写。有人可以帮忙吗？ 我用Java写了函数和类来测试伪代码？那是对的吗？再次，从效率的角度来看，我怎样才能让它变得更好。

//Scanner library allowing the user to input data
import java.lang.Math.*;

public class ArrayTester{
    //algorithm for finding the distance between the two closest elements in an array of numbers
    public int MinDistance(int [] ar){
    int [] a = ar;
    int aSize = a.length;
    int dMin = 0;//MaxInt
    for(int i=0; i< aSize; i++)
    {
        for(int j=i+1; j< aSize;j++)
        {   
            dMin = Math.min(dMin, Math.abs( a[i]-a[j] );
        }
    }
    return dMin;
}

    //MAIN
    public static void main(String[] args){

        ArrayTester at = new ArrayTester();
        int [] someArray = {9,1,2,3,16};
        System.out.println("NOT-OPTIMIZED METHOD");
        System.out.println("Array length = "+ someArray.length);
        System.out.println("The distance between the two closest elements: " + at.MinDistance(someArray));

    } //end MAIN

} //END CLASS

所以我更新了函数以尽量减少调用 Math.abs 两次。我还能做些什么来改进它。如果我用 sort 重写它，它会完全改变我的 for 循环吗？或者它会是相同的，只是理论上运行得更快。

public int MinDistance(int [] ar){
        int [] a = ar;
        int aSize = a.length;
        int dMin = 0;//MaxInt
        for(int i=0; i< aSize; i++)
        {
            for(int j=i+1; j< aSize;j++)
            {   
                dMin = Math.min(dMin, Math.abs( a[i]-a[j] );
            }
        }
        return dMin;
    }

一个明显的效率改进：首先对整数进行排序，然后你可以查看相邻的整数。任何数字都将最接近其邻居，无论是向上还是向下。

That changes the complexity from O(n²) to O(n log n). Admittedly for the small value of n shown it's not going to make a significant difference, but in terms of theoretical complexity it's important.

您可能想要进行的一项微优化：使用局部变量来存储以下结果Math.abs，那么如果结果小于最小值，则无需重新计算它。或者，您可能想使用dMin = Math.min(dMin, Math.abs(a[i] - a[j])).

请注意，您需要注意边界条件 - 如果您允许负数，您的减法可能会溢出。