设有n个-100~100之间的随机数组储存于数组S中,写出算法 Rearrange(s,h,n),使得负数排在非负数前.帮个忙啦,帖子在问问里
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/15 19:57:46
设有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用来修正偏移!