设任意n个整数存放于数组a[1..n]中,编写算法,将所有正数排在所有负数前面。
时间: 2023-04-27 17:03:25 浏览: 195
算法思路:
1. 定义两个指针i和j,分别指向数组的第一个元素和最后一个元素。
2. 当i<j时,循环执行以下操作:
a. 如果a[i]为正数,则i指针向后移动一位。
b. 如果a[i]为负数,则将a[i]和a[j]交换,j指针向前移动一位。
c. 如果a[j]为负数,则j指针向前移动一位。
d. 如果a[j]为正数,则将a[i]和a[j]交换,i指针向后移动一位。
3. 当i>=j时,排序完成。
算法实现:
```
void sort(int a[], int n) {
int i = , j = n - 1;
while (i < j) {
while (i < j && a[i] > ) i++;
while (i < j && a[j] < ) j--;
if (i < j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
}
```
算法分析:
时间复杂度为O(n),空间复杂度为O(1)。
相关问题
数据结构中设任意n个整数存放于数组A(1:n)中,试编写算法,将所有正数排在所有负数面前
好的,这是一个关于数据结构的问题,我会尽力回答。可以使用双指针的方法,一个指向数组的开头,一个指向数组的结尾,从两端开始遍历数组,如果左边是负数,右边是正数,则交换它们的位置。重复这个过程直至两个指针相遇。以下是具体的实现代码:
```python
def rearrange_array(arr):
left = 0
right = len(arr) - 1
while left < right:
while arr[left] < 0:
left += 1
while arr[right] >= 0:
right -= 1
if left < right:
arr[left], arr[right] = arr[right], arr[left]
return arr
```
这个算法的时间复杂度为O(n),因为只需要遍历整个数组一次。
设任意n个整数存放于数组A[1..n]中,试编写算法,将所有整数排在所有负数前面(要求:算法时间复杂度为O(n))。
可以使用双指针法,一个指向数组的头部,一个指向数组的尾部,分别向中间移动。具体步骤如下:
1. 初始化两个指针i和j,i指向数组的头部,j指向数组的尾部。
2. 当i<j时,执行以下操作:
(1)如果A[i]为负数,则将i向后移动一位;
(2)如果A[i]为正数,则判断A[j]的符号:
a. 如果A[j]为负数,则将A[i]和A[j]交换,然后将i向后移动一位,j向前移动一位;
b. 如果A[j]为正数,则将j向前移动一位。
3. 当i>=j时,算法结束。
代码实现如下:
```
void moveNegative(int A[], int n){
int i = 0, j = n - 1;
while(i < j){
if(A[i] < 0){
i++;
}
else{
if(A[j] < 0){
//swap A[i] and A[j]
int temp = A[i];
A[i] = A[j];
A[j] = temp;
i++;
j--;
}
else{
j--;
}
}
}
}
```
时间复杂度为O(n),空间复杂度为O(1)。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)