设计算法求数组中相差最小的两个元素（称为最接近数）的差。要求分别给出伪代码和C++描述。

冷不防 2021-07-25 00:01 444阅读 0赞

## 1.题目 ##

## 2.算法分析思路： ##

1.对数组先进行快速排序，使数组有序

2.依次比较相邻两数的差,更新最小值

## 3.快速排序模板: ##

void quick_sort(int q[], int l, int r)
    { 
        //递归的终止情况
        if(l >= r) return;
        //第一步：分成子问题
        int i = l - 1, j = r + 1, x = q[l + r >> 1];
        while(i < j)
        { 
            do i++; while(q[i] < x);
            do j--; while(q[j] > x);
            if(i < j) swap(q[i], q[j]);
        }
        //第二步：递归处理子问题
        quick_sort(q, l, j), quick_sort(q, j + 1, r);
    }

## 4.时间复杂度分析 ##

快速排序`O(nlog2n)` 更新最小值 `for`循环 `O(n)`  
最终时间复杂度：`O(nlog2n)`

## 5.测试数据： ##

**样例输入**  
11  
0 2 32 43 23 45 36 57 14 27 39  
**样例输出**  
2

## 6.完整程序 ##

#include<stdio.h>
    
    const int N = 1e5 + 10;
    int q[N];
    //快速排序模板
    void quick_sort(int q[], int l, int r)
    { 
        //递归的终止情况
        if(l >= r) return;
        //第一步：分成子问题
        int i = l - 1, j = r + 1, x = q[l + r >> 1];
        while(i < j)
        { 
            do i++; while(q[i] < x);
            do j--; while(q[j] > x);
            if(i < j) 
            {  
                int temp = q[i];
    			q[i] = q[j];
    			q[j] = temp; 
    		} 
        }
        //第二步：递归处理子问题
        quick_sort(q, l, j), quick_sort(q, j + 1, r);
    }
    int main()
    { 
    	int n;
    	scanf("%d",&n);
    	for(int i = 0; i < n ; i++) scanf("%d",&q[i]);
    	quick_sort(q,0,n-1);
    	int minv = 1e9 + 10;  //记录最小值答案
    	for(int i = 0; i < n - 1; i++)
    	{ 
    	   if(q[i+1]-q[i] < minv ) //更新最小值
    	   { 
    	      minv = q[i+1]-q[i];	
    	   }
    	} 
    	printf("%d\n",minv);
    	return 0;
    }

## 7.总结反思 ##

排序算法是为了让无序的数据组合变成有序的数z据组合。有序的数据组合最大的优势是在于当你进行数据定位和采用时，会非常方便，因为这个数据是有序的从而在代码设计的时候会让你避免很多不必要的麻烦，因为无序数据你在进行推断数据前后关系的时候会显示很繁琐，快速排序是排序中的一种，它在最差情况下和别的排序相差不大而在最优，一般情况下，会比一般的排序方法更节省时间。