一个线性表种的元素为正整数或负整数，分开的题目。

来源：百度知道 编辑：UC知道 时间：2024/06/05 13:21:57
题目：一个线性表种的元素为正整数或负整数。设计一个算法将正整数和负整数分开，使线性表的前半部分为负整数，后一半为正整数。注意，不要求对这些元素排序，但要求尽量减少比较的次数。

数据结构的一道习题，望知道的老大们指点一下，需要步骤，谢谢。

我的思路是把这个线性表分成2个表，然后再把2个表合并，希望能看到更好的算法。

不需要把线性表分成2个表，你可以对线性表（数组）进行两遍扫描就行。

1.第一遍统计正整数和负整数的数目。

2.第二遍 从前往后找正整数、同时从后往前找负整数，找到后进行交换即可。

如果元素不是非常大的话，使用哈希表就可以了
先读一遍数据，每读一个数对应的哈希表赋为true
然后从最小数到最大数搜一遍即可