微软十五道面试题之一 -----有一个整数数组，请求出两两之差绝对值最小的值

问题：有一个整数数组，请求出两两之差绝对值最小的值,记住，只要得出最小值即可，不需要求出是哪两个数。

我的思路：两个数要想差的绝对值最小，肯定是需要两个数大小相近。故有：先将整数数据进行排序，耗时o(N*logN);然然后遍历一遍，相邻的数相减，记录绝对值最小的数。总耗时为：O(N*logN).
实现代码如下：
  

//快速排序
#include<iostream>
using namespace std;


//以最小元为主元
int Partion1(int *arr,int low,int high)
{
    int key=arr[low];
    while(low<high)
    {
     while(low<high && arr[high]>=key)
            high--;
        arr[low]=arr[high];
        while(low<high && arr[low]<=key)
            low++;
        arr[high]=arr[low];
    }
    arr[low]=key;
    return low;
}

//以最大元为主元
int Partion2(int *arr,int low,int high)
{
    int key=arr[high];
    while(low<high)
    {
     while(low<high && arr[low]<=key)
            low++;
        arr[high]=arr[low];
        while(low<high && arr[high]>=key)
            high--;
        arr[low]=arr[high];
    }
    arr[high]=key;
    return high;
}


void QSort(int *arr,int low,int high)
{
    if(low<high)
    {
        int pivoc=Partion1(arr,low,high);

        QSort(arr,low,pivoc-1);
        QSort(arr,pivoc+1,high);
    }
}


void QuickSort(int *arr,int low,int high)
{
    QSort(arr,low,high);
}



int main()
{
    int i;
    int min=65535;
    int a[9]={-1,-1,-1,-1,-1,-2,0,-98,100};
    QuickSort(a,0,8);
    for(i=0;i<9;i++)
        printf("%d ",a[i]);
    cout<<endl;
    for(i=0;i<8;i++)
    {
     int tmp=a[i]-a[i+1];
        if(tmp<0)
            tmp=(-1)*tmp;
        if(tmp<min)
            min=tmp;
    }
    cout<<min<<endl;

    return 0;
}

结果如下：
  

等待更高效的算法。。。。