设有n个-100~100之间的随机数组储存于数组S中,写出算法 Rearrange(s,h,n),使得负数排在非负数前.帮个忙啦,帖子在问问里
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/30 17:56:16
![设有n个-100~100之间的随机数组储存于数组S中,写出算法 Rearrange(s,h,n),使得负数排在非负数前.帮个忙啦,帖子在问问里](/uploads/image/z/7093023-15-3.jpg?t=%E8%AE%BE%E6%9C%89n%E4%B8%AA-100%7E100%E4%B9%8B%E9%97%B4%E7%9A%84%E9%9A%8F%E6%9C%BA%E6%95%B0%E7%BB%84%E5%82%A8%E5%AD%98%E4%BA%8E%E6%95%B0%E7%BB%84S%E4%B8%AD%2C%E5%86%99%E5%87%BA%E7%AE%97%E6%B3%95+Rearrange%28s%2Ch%2Cn%29%2C%E4%BD%BF%E5%BE%97%E8%B4%9F%E6%95%B0%E6%8E%92%E5%9C%A8%E9%9D%9E%E8%B4%9F%E6%95%B0%E5%89%8D.%E5%B8%AE%E4%B8%AA%E5%BF%99%E5%95%A6%2C%E5%B8%96%E5%AD%90%E5%9C%A8%E9%97%AE%E9%97%AE%E9%87%8C)
设有n个-100~100之间的随机数组储存于数组S中,写出算法 Rearrange(s,h,n),使得负数排在非负数前.帮个忙啦,帖子在问问里
设有n个-100~100之间的随机数组储存于数组S中,写出算法 Rearrange(s,h,n),使得负数排在非负数前.
帮个忙啦,帖子在问问里
设有n个-100~100之间的随机数组储存于数组S中,写出算法 Rearrange(s,h,n),使得负数排在非负数前.帮个忙啦,帖子在问问里
既然已经知道是-100到100之间,那就非常简单了
void rearrange(int s[],in h[],int n) { //s为原数组,h为目标数组,n为原数组长度
int numbers[201] = {0};//用来标示-100~100对应的位置
const int SHIFT = 100; //偏移量
int index = 0,numbers_index = 0;
for (; index != n; ++index) {
++numbers[s[index] + SHIFT]; //每个整数值加偏移调整后存入numbers
}
index = 0;
for (; numbers_index != 201; ) { //遍历每一个numbers[]的值
int temp_index = 0; // 用于遍历重复的某一个值
int count = numbers[index]; // 用于标示某一个值重复了几次
for (; temp_index != count; ++temp_index) {
h[index] = numbers[numbers_index]; // 每一个h[]的元素从小到大依次赋值
++index;
}
++numbers_index;
}
}
不是什么高手,也就看了些书而已,算法应该是很直观的,虽然你可以使用普通的排序算法,诸如最简单的冒泡排序,不过那样就没有充分利用已知的值在一个区间内的条件!
你可以这样想,既然每个值都在区间内,那么就相当于一个数轴,每一个值肯定对应一个点,比如85就在85那个点,-20就在-20那个点,把每一个值这样一一对应好,h然后从小到大开始查看数轴,比如34这个点上显示有两个对应,那就说明原数组内有两个34,就要输出34两次!另外由于数组索引都是从0开始,所以定义了常量SHIFT用来修正偏移!