在顺序存储模式下将所有的负数放到正数前面的三种算法

来源:岁月联盟 编辑:猪蛋儿 时间:2012-11-17
test1的时间复杂度最高,test2的时间复杂度优于test1,test3的时间复杂度最小,所用的时间最少
[cpp] 
/************************************test1**********************/ 
//程序功能:在顺序存储模式下将所有的负数放到整数前面 
#include<iostream> 
using namespace std; 
/*
*算法描述:找到负数并用临时变量存上,先将负数之前的所有的数向后移一位,然后将负数放在最前面。
*/ 
int main() 

    int Array[10] = {2,-3,4,-5,6,-7,8,-9,10,-11}; 
    for(int i =0;i < 10;i++) 
    { 
        int temp1;//temp1用于存放找到的负数 
        if(Array[i]< 0) 
        { 
            temp1 = Array[i]; 
            for(int j =i;j>0;j--) 
            { 
                Array[j] = Array[j-1]; 
            } 
            Array[0] = temp1; 
        } 
    } 
    for(int k = 0;k < 10;k++) 
    { 
        cout<<Array[k]<<"   "; 
    } 
 

/***********************************test2**********************************/ 
//程序功能:在顺序存储模式下将所有的负数放到整数前面 
#include<iostream> 
using namespace std; 
/*
*算法描述:用一个变量存储数组前面负数的位置。
*/ 
int main() 

    int Array[10] = {2,-3,4,-5,6,-7,8,-9,10,-11},k =0; 
    for(int i =0;i < 10;i++) 
    { 
        int temp1;//temp1用于交换数据的临时变量 
        if(Array[i]< 0) 
        { 
            temp1 = Array[i]; 
            Array[i] = Array[k]; 
            Array[k] = temp1; 
            k++; 
        } 
         
    } 
    for(int k = 0;k < 10;k++) 
    { 
        cout<<Array[k]<<"   "; 
    } 
 

/*****************************************test3*******************************************/ 
//程序功能:在顺序存储模式下将所有的负数放到整数前面 
#include<iostream> 
using namespace std; 
/*
*算法描述:相当于俩个指针分别指向表头和表尾。
*/ 
int main() 

    int Array[10] = {2,-3,4,-5,6,-7,8,-9,10,-11},k =0; 
    for(int i =9;i >k;i--) 
    { 
        int temp1;//temp1用于存放交换的临时变量 
        if(Array[i]< 0&&Array[k] < 0) 
        { 
            k++; 
            i++; 
        } 
        if(Array[i]< 0&&Array[k] > 0) 
        { 
            temp1 = Array[i]; 
            Array[i] = Array[k]; 
            Array[k] = temp1; 
            k++; 
        } 
        if(Array[i]> 0&&Array[k] > 0) 
        {} 
        if(Array[i]> 0&&Array[k] < 0) 
        {} 
         
    } 
    for(int k = 0;k < 10;k++) 
    { 
        cout<<Array[k]<<"   "; 
    }