一：问题描述
Description: Given an unsorted array, find the maximum difference between the successive elements in its sorted form. Try to solve it in linear time/space. You may assume all elements in the array are non-negative integers and the length of the array is no less than 2. The input is a line containing an unsorted array, and the output is the maximum difference you find, for example:
Given [3 4 8 13 2 7 15], return 5
二：斟酌题意
题意就是 希望我们用O(n)的时间解决这样一个问题：对给定的不定长的数字，找到排序后 前后差值最大的差值。
如[3 4 8 13 2 7 15] ，排序后为 2 3 4 7 8 13 15，那么最大的差距为 13-8=5。如此而已。
三：思路
我们可以先将 数组利用 计数排序，然后遍历同时计算最大的差值即可，so easy!
四：C代码
/* 1.运行环境：windows 7 + 32位系统 + vs2013 2.无差错控制，无安全检查，无特殊处理。 3.带刺的银杏 2015.05.17夜 于 苏州 */
#include <stdio.h>
#define max_value 300 //待输入的数组中数字最大值不超过max_value
#define max_arr 50 //输入元素个数
void print_arr(int arr[],int n) //打印数组
{
int i;
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
void count_sort(int arr[], int sorted_arr[], int n) //计数排序，原理参见 《算法导论》第二版 P99
{
int count_arr[max_value];
int i;
for(i = 0; i<max_value; i++)
count_arr[i] = 0;
for(i = 0;i<n;i++)
count_arr[arr[i]]++;
for(i = 1; i<max_value; i++)
count_arr[i] += count_arr[i-1];
for(i = n; i>0; i--)
{
sorted_arr[count_arr[arr[i-1]]-1] = arr[i-1];
count_arr[arr[i-1]]--;
}
}
int count_max_diff(int arr[],int length) //计算差值
{
int i,max = 0;
for(i = 1; i < length;i++)
max = (arr[i] - arr[i-1]) > max ? (arr[i] - arr[i-1]): max ;
printf("%d",max);
}
int main() {
int length,i=0;
int arr[max_arr] ;
int sorted[max_arr];
char temp;
temp = getchar(); //输入的左括号
while(1)
{
scanf("%d%c",&arr[i++],&temp);
if(temp == ']') //收到输入的右括号，终止输入
break;
}
length = i;
// print_arr(arr, length);
count_sort(arr,sorted, length);
// printf ("排序后的数组：");
print_arr(sorted, length);
count_max_diff(sorted,length);
return 0;
}五：小结
由于计数排序不是稳定的，所以建议还是 桶排序比较好。