`
YuHuang.Neil
  • 浏览: 186922 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

如何实现数组的高效移位算法

阅读更多
问题:编写一个能够支持数组快速移位的算法,时间复杂度在O(N)以内。

答:要实现在线性的时间内实现数组的快速移动,就要考虑如何使用逆序算法来达到移动的目的。例如,我要移动的数组元素称为A,剩余的部分称为B,那么原来次序为AB,如何变成BA呢?其实根据倒置的算法是可以实现移位操作的,我们先取A'为A的逆序序列,B'为B的逆序序列,进行(A'B')'操作即可得到BA序列。实现算法如下:

//
//  main.cpp
//  MyProjectForCPP
//
//  Created by labuser on 11/2/11.
//  Copyright 2011 __MyCompanyName__. All rights reserved.
//

#include <iostream>
using namespace std;


void ReverseArray(int dataArray[],int start,int end){
    int low=start,high=end;
    
    if(start>end){
        cout<<"Index Error!"<<endl;
        cout<<"start:"<<start<<" end:"<<end;
    }
    
    while(low<high){
        int tempDate = dataArray[low];
        dataArray[low] = dataArray[high];
        dataArray[high] = tempDate;
        ++low;
        --high;
    }
    
}


void QuickShift(int dataArray[],int shift,int n){
    int len =n;
    
    ReverseArray(dataArray, 0, shift-1);
    ReverseArray(dataArray, shift, len-1);
    ReverseArray(dataArray, 0, len-1);
}

int main (int argc, const char * argv[])
{
    int dataArray[10]={1,2,3,4,5,6,7,8,9,10};
    int n = sizeof(dataArray)/sizeof(int);
    
    QuickShift(dataArray, 4,n);
    
    for(int i=0;i<n;++i){
        cout<<dataArray[i]<<" ";
    }
    
    cout<<endl;
    
    return 0;
}





运行的结果为:
GNU gdb 6.3.50-20050815 (Apple version gdb-1705) (Fri Jul  1 10:44:54 UTC 2011)
Copyright 2004 Free Software Foundation, Inc.
GDB is free software, covered by the GNU General Public License, and you are
welcome to change it and/or distribute copies of it under certain conditions.
Type "show copying" to see the conditions.
There is absolutely no warranty for GDB.  Type "show warranty" for details.
This GDB was configured as "x86_64-apple-darwin".tty /dev/ttys002
[Switching to process 17195 thread 0x0]
5 6 7 8 9 10 1 2 3 4
Program ended with exit code: 0
分享到:
评论

相关推荐

    数组循环移位问题的解法的探究

    特别是在涉及到数组元素的移动时,如何高效地进行数组元素的移位操作成为了许多算法研究的重点之一。本文将深入探讨数组循环移位问题的解决方法,并通过对不同解决方案的分析,寻求最优解。 #### 数组循环移位的...

    C语言实现数组的循环移位的方法示例

    这种操作在数据处理、位操作和算法实现等领域都有广泛应用。本篇文章将深入探讨如何用C语言实现数组的循环左移和循环右移。 首先,我们需要理解数组翻转的概念。数组翻转是指将数组中的元素顺序颠倒,即原数组的第...

    字符数组循环位移高效算法

    /* 2010年考研数据结构综合应用的一道题...* 要求将长度为n的数组做p位循环移位,效率应尽量高。例如将ABCDEFG做3位循环移动(向右) * 结果是EFGABCD。 * 下面这个算法时间复杂度为O(n)空间复杂度为O(1)相当高效。 */ //

    VB 数组内平移

    在VB(Visual Basic)编程中,数组是一种存储多个相同类型数据的数据结构。数组内平移的概念,简单来说,就是将数组中的元素按照指定的步长移动,...熟练掌握数组平移技巧对于编写高效算法和解决复杂问题非常有帮助。

    祖冲之密码算法Java实现

    9. **性能优化**:虽然祖冲之算法本身已经设计得很高效,但在Java中实现时,仍需要注意内存管理和计算性能,以适应可能的大规模数据加密需求。 10. **文档编写**:为了方便其他开发者理解和使用你的实现,需要编写...

    循环移位与改进插入排序算法

    #### 算法实现 改进后的插入排序算法主要步骤如下: 1. **初始化**:设定待排序数组为`A`,数组长度为`n`。 2. **遍历数组**:从第二个元素开始遍历数组(即从索引1开始),对于每个元素`A[i]`(`i`从1到`n-1`):...

    约瑟夫环问题(数组实现,链表实现

    该问题通常用于考察计算机科学中的循环移位、数据结构和算法设计。在这个问题中,人们站成一个圈,并按照顺时针或逆时针顺序报数,每数到特定数值的人将退出圈子,接着下一个人继续从1开始报数,直至只剩最后一个人...

    移位寄存器中BM算法

    ### 移位寄存器中的BM算法解析 ...通过对上述代码的理解和分析,我们不仅能够深入掌握BM算法的工作原理,还能够进一步探索其在实际工程中的应用前景,如在通信系统中实现高效的数据传输、错误检测与纠正等。

    VHDL 实现的FFT算法

    位反转可以通过查找表或递归算法实现,VHDL中可以使用数组或移位寄存器来描述。 5. **复数运算**:VHDL需要实现加法、乘法等复数运算。在硬件描述语言中,乘法通常会被转换为多个加法器和延迟线,而复数乘法则需要...

    AES算法快速硬件实现Verilog

    在Verilog中,可以通过二维数组实现S-Box,并定义一个函数来完成字节替换操作。 2. **行移位(ShiftRows)**: 行移位操作是对明文或密文的4x4字节矩阵进行的。每一行按特定的位数向左循环移位,第一行不移位,第二...

    移位循环与改进差值算法

    移位循环与改进差值算法是一种高效的排序算法,它结合了移位循环和改进差值的特性,能够在一定程度上优化排序过程。通过对数组中部分元素进行有效的移位操作,该算法能够显著提高排序速度。本文虽然没有详细解释`...

    数组循环左移

    总之,数组循环左移是编程中的一种基本操作,可以通过原地旋转算法在有限的空间内高效完成。这种技巧不仅适用于一维数组,还可以扩展到多维数组或更复杂的数据结构,对于理解和优化算法有着重要的作用。在实际编程中...

    KECCAK 密码算法的FPGA实现

    - 算法的执行时间为9.967纳秒,表明KECCAK算法在硬件上实现了高效的性能。 6. 硬件实现的意义和应用: - 物联网、无线传感技术等领域的广泛应用要求密码算法能以硬件形式实现。 - 由于KECCAK算法在设计上有别于...

    Grain算法C语言实现

    Grain算法的核心是两个线性反馈移位寄存器(LFSR和NFSR),以及一个非线性函数F。这两个寄存器分别包含80比特和160比特的状态,通过迭代更新状态来生成密钥流,用于数据加密或解密。 1. **初始化阶段**:使用密钥和...

    使用C51实现128位AES加密算法

    在本文中,我们将深入探讨如何使用C51微控制器编程语言来实现128位的高级加密标准(AES)加密...通过精心设计和优化代码,可以在8051微控制器上实现高效且安全的AES加密功能,从而为各种嵌入式系统提供可靠的数据保护。

    约瑟夫环的算法实现

    在这个问题的算法实现中,有几种常见的方法: 1. **链表实现**: - 创建一个双向链表,节点代表每个人,节点的值为编号。 - 按照报数规则删除节点,直到链表只剩下一个节点。 - 这种方法直观且易于理解,但操作...

    利用数组进行千位数据大处理

    【优化算法】为了提高大数运算的效率,可以通过位操作和移位来实现大数的加减乘除,这虽然比字符数组表示的方法更复杂,但能显著提升性能。此外,还可以通过减少循环次数(例如将循环规模控制在32次之内),使得算法...

    c语言的课件 有概述,算法,数据类型,简单程序,选择,循环,数组,函数,预处理,指针,结构体,位运算,文件和常见错误 徐州师范大学计算机科学与技术学院

    课件会教授如何用C语言实现排序、搜索等基本算法,并讲解算法的时间复杂度和空间复杂度分析。 3. **数据类型**:C语言提供了多种基本数据类型,如整型(int)、浮点型(float、double)、字符型(char)和布尔型...

    AES加密算法的实现及应用

    AES加密算法由于其高效性和安全性,在多个领域得到广泛应用: 1. **网络安全**:在互联网通信中,AES用于保护数据传输的安全,防止数据被窃听或篡改。 2. **数据库安全**:在数据库系统中,AES用于加密敏感数据,...

    算法心得:高效算法的奥秘(原书第2版).[美]Henry S.Warren,Jr(带详细书签).pdf

    9.4.1 用硬件实现移位并相减算法 172 9.4.2 用短除法实现无符号长除法 174 9.5 用长除法实现双字除法 176 9.5.1 无符号双字除法 176 9.5.2 带符号双字除法 179 9.6 习题 180 第10章 除数为常量的整数除法 181 ...

Global site tag (gtag.js) - Google Analytics