数据结构-前正后负

喜欢ヅ旅行 2022-05-19 06:40 150阅读 0赞

(**2018吉林大学941**)一个长度为 n 的数组由负数、0、正数组成。编写函数，将其重新排序为前段都是负数，后段均为非负数的结构。要求时间复杂度为 O(n)。

#include<iostream>
    #include<stdlib.h>
    using namespace std;
    
    void SortArray(int data[], int n)
    {
    	int head = 0, rear = n - 1, count = 0; 
    	/*
    		定义两个“指针”，在head之前（包括head）
    		都是小于0数，rear之后（不包括rear）
    		都是大于0的数
    	*/ 
    	int tmp;
    	for(int i = 0; count < n ; count++)
    	{
    		/*
    			判断当前元素
    			--	如果是正数，则与rear所指元素交换，rear前移，计数器+1，指针不加1（因为交换过来的rear没有判断过） 
    			--	如果是负数，则与head所指元素交换，head后移，计数器+1，指针+1 (因为移过来的head一定是小于0的)
    			--	如果是0，则计数器+1，指针+1  
    		*/ 
    		if(data[i] < 0)
    		{
    			tmp = data[head];
    			data[head++] = data[i];
    			data[i++] = tmp;
    		}
    		else if(data[i] > 0)
    		{
    			tmp = data[rear];
    			data[rear--] = data[i];
    			data[i] = tmp;
    		}
    		else
    		{
    			i++;
    		}
    	}
    }
    
    void PrintArray(int data[], int n)
    {
    	for(int i = 0; i < n; i++)
    	{
    		cout<<data[i]<<" ";
    	}
    	cout<<endl;
    }
    
    int main()
    {
    	int data[] = {1, 0, -5, -9, 1, 0, 4, -6};
    	PrintArray(data, 8);
    	SortArray(data, 8);
    	PrintArray(data, 8);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，150人围观）

还没有评论，来说两句吧...

相关阅读

相关 java数据结构之二叉树的前中后遍历

感谢[笃志近思][Link 1]的分享。原文链接地址为：[点击打开链接][Link 2] 二叉树的定义：二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构

分手后的思念是犯贱/ 2022年09月21日 13:08/ 0 赞/ 54 阅读

相关数据结构中序后序求前序

include <stdio.h> include <stdlib.h> include <string.h> void pr

深藏阁楼爱情的钟/ 2022年09月19日 01:53/ 0 赞/ 156 阅读

相关数据结构前序中序求后序

include <stdio.h> include <stdlib.h> include <string.h> void Po

落日映苍穹つ/ 2022年09月19日 01:53/ 0 赞/ 133 阅读

相关正则表达式-正向先行断言-负向先行断言-后向负行断言-正向负行断言

正向先行断言-负向先行断言-后向负行断言-正向负行断言 (?=pattern) 正向先行断言代表字符串中的一个位置，紧接该位置之后的字符序列能够匹配 patter

àì夳堔傛蜴生んèń/ 2022年09月06日 15:20/ 0 赞/ 200 阅读

相关十分钟掌握正则表达式！5_分组匹配_非捕获形分组：前瞻、负前瞻、后顾、负后顾.

javascript正则表达式 1、非捕获\_\_型分组 2.1、前瞻\_\_型分组： 2.2、负前瞻\_\_型分组： 2.3、后顾\_\_型分组

偏执的太偏执、/ 2022年09月04日 09:47/ 0 赞/ 172 阅读

相关数据结构已知中后序列求前序及深度

求二叉树的深度 Time Limit: 1000MS Memory limit: 65536K 题目描述已知一颗二叉树的中序遍历序列和后序遍历序列，

妖狐艹你老母/ 2022年07月19日 02:42/ 0 赞/ 102 阅读

相关记负均正

从输入任意个整型数，统计其中的负数个数并求所有非负数的平均值输入描述: 输入任意个整数输出描述: 输出负数个数以及所有非负数的平均值 import

深藏阁楼爱情的钟/ 2022年06月04日 09:22/ 0 赞/ 185 阅读

相关数据结构-前正后负

(2018吉林大学941)一个长度为 n 的数组由负数、0、正数组成。编写函数，将其重新排序为前段都是负数，后段均为非负数的结构。要求时间复杂度为 O(n)。 inc

喜欢ヅ旅行/ 2022年05月19日 06:40/ 0 赞/ 151 阅读

相关查询最近 n 天前后数据

查询最近 n 天前后数据一,序言在监控模块,

左手的ㄟ右手/ 2022年04月22日 03:00/ 0 赞/ 273 阅读

相关数据结构与算法前置

数据结构绪论学习笔记：简介数据结构是一门研究非等值计算的程序设计问题的操作对象,以及他们之间的关系核操作等相关问题的学科。简而言之数据结构是计算机存储、组织数

港控/mmm°/ 2022年02月05日 05:11/ 0 赞/ 218 阅读