问题描述

数据结构 习题答案

若一个线性表L采用顺序存储结构存储，其中所有元素为整数，设计一个算法，将所有小于0的元素面前，要求算法的时间复杂度为O（n）,空间复杂度为O（l）

解决方案

 #include <stdio.h>

void swp(int& a, int& b)
{
    int c = a;
    a = b;
    b = c;
}

int main()
{
    int z = 0, i = 0;
    int data[] = {2,-1,0,5,-3,8,-2,-9,0,8};
    for (i = 0; i < 10; i++)
    {
        if (data[i] < 0)
        {
            swp(data[i], data[z]);
            z++;
        }
    }
    for (i = 0; i < 10; i++) printf("%d ", data[i]);
}

-1 -3 -2 -9 2 8 0 5 0 8

解决方案二：

顺便说下，空间复杂度是O(1)，不是O(l)。题目会不会做先不说，起码把题目什么意思得搞清楚。

解决方案三：

数据结构实践（有的数据结构课后习题答案），红色是答案
数据结构习题答案(全部算法)---严蔚敏版
数据结构习题之线性表

解决方案四：

实现方法跟快速排序一样，
int index=-1;
for(int i=0;i<length;i++)
{
if(array[i]<0)
{
++index；
swap(array[i],array[index]);
}
}