dsal 数组旋转的块交换算法

数组旋转的块交换算法

原文： https://www.geeksforgeeks.org/block-swap-algorithm-for-array-rotation/

编写一个函数turn(ar[], d, n)，该函数将大小为n的arr[]旋转d个元素。

Array

将上面的数组旋转 2 将产生数组：

ArrayRotation1

算法：

Initialize A = arr[0..d-1] and B = arr[d..n-1]
1) Do following until size of A is equal to size of B

  a)  If A is shorter, divide B into Bl and Br such that Br is of same 
       length as A. Swap A and Br to change ABlBr into BrBlA. Now A
       is at its final place, so recur on pieces of B.  

   b)  If A is longer, divide A into Al and Ar such that Al is of same 
       length as B Swap Al and B to change AlArB into BArAl. Now B
       is at its final place, so recur on pieces of A.

2)  Finally when A and B are of equal size, block swap them.

递归实现：

C++

#include <bits/stdc++.h> 
using namespace std; 

/*Prototype for utility functions */
void printArray(int arr[], int size);  
void swap(int arr[], int fi, int si, int d);  

void leftRotate(int arr[], int d, int n)  
{  
    /* Return If number of elements to be rotated   
    is zero or equal to array size */
    if(d == 0 || d == n)  
        return;  

    /*If number of elements to be rotated  
    is exactly half of array size */
    if(n - d == d)  
    {  
        swap(arr, 0, n - d, d);  
        return;  
    }  

    /* If A is shorter*/        
    if(d < n - d)  
    {  
        swap(arr, 0, n - d, d);  
        leftRotate(arr, d, n - d);      
    }  
    else /* If B is shorter*/        
    {  
        swap(arr, 0, d, n - d);  
        leftRotate(arr + n - d, 2 * d - n, d); /*This is tricky*/
    }  
}  

/*UTILITY FUNCTIONS*/
/* function to print an array */
void printArray(int arr[], int size)  
{  
    int i;  
    for(i = 0; i < size; i++)  
        cout << arr[i] << " ";  
    cout << endl;  
}  

/*This function swaps d elements starting at index fi  
with d elements starting at index si */
void swap(int arr[], int fi, int si, int d)  
{  
    int i, temp;  
    for(i = 0; i < d; i++)  
    {  
        temp = arr[fi + i];  
        arr[fi + i] = arr[si + i];  
        arr[si + i] = temp;  
    }  
}  

// Driver Code 
int main()  
{  
    int arr[] = {1, 2, 3, 4, 5, 6, 7};  
    leftRotate(arr, 2, 7);  
    printArray(arr, 7);  
    return 0;  
}  

// This code is contributed by rathbhupendra

C

#include<stdio.h>

/*Prototype for utility functions */
void printArray(int arr[], int size);
void swap(int arr[], int fi, int si, int d);

void leftRotate(int arr[], int d, int n)
{ 
  /* Return If number of elements to be rotated is 
    zero or equal to array size */ 
  if(d == 0 || d == n)
    return;

  /*If number of elements to be rotated is exactly 
    half of array size */ 
  if(n-d == d)
  {
    swap(arr, 0, n-d, d);   
    return;
  }  

 /* If A is shorter*/             
  if(d < n-d)
  {  
    swap(arr, 0, n-d, d);
    leftRotate(arr, d, n-d);    
  }    
  else /* If B is shorter*/             
  {
    swap(arr, 0, d, n-d);
    leftRotate(arr+n-d, 2*d-n, d); /*This is tricky*/
  }
}

/*UTILITY FUNCTIONS*/
/* function to print an array */
void printArray(int arr[], int size)
{
  int i;
  for(i = 0; i < size; i++)
    printf("%d ", arr[i]);
  printf("\n ");
} 

/*This function swaps d elements starting at index fi
  with d elements starting at index si */
void swap(int arr[], int fi, int si, int d)
{
   int i, temp;
   for(i = 0; i<d; i++)   
   {
     temp = arr[fi + i];
     arr[fi + i] = arr[si + i];
     arr[si + i] = temp;
   }     
}     

/* Driver program to test above functions */
int main()
{
   int arr[] = {1, 2, 3, 4, 5, 6, 7};
   leftRotate(arr, 2, 7);
   printArray(arr, 7);
   getchar();
   return 0;
}

Java

import java.util.*;

class GFG 
{
    // Wrapper over the recursive function leftRotateRec()
    // It left rotates arr[] by d.
    public static void leftRotate(int arr[], int d, 
                                                int n)
    {
        leftRotateRec(arr, 0, d, n);
    }

    public static void leftRotateRec(int arr[], int i, 
                                  int d, int n)
    {
        /* Return If number of elements to be rotated 
        is zero or equal to array size */
        if(d == 0 || d == n) 
            return; 

        /*If number of elements to be rotated 
        is exactly half of array size */
        if(n - d == d) 
        { 
            swap(arr, i, n - d + i, d); 
            return; 
        } 

        /* If A is shorter*/   
        if(d < n - d) 
        { 
            swap(arr, i, n - d + i, d); 
            leftRotateRec(arr, i, d, n - d);     
        } 
        else /* If B is shorter*/   
        { 
            swap(arr, i, d, n - d); 
            leftRotateRec(arr, n - d + i, 2 * d - n, d); /*This is tricky*/
        } 
    }

/*UTILITY FUNCTIONS*/
/* function to print an array */
public static void printArray(int arr[], int size) 
{ 
    int i; 
    for(i = 0; i < size; i++) 
        System.out.print(arr[i] + " "); 
    System.out.println(); 
} 

/*This function swaps d elements 
starting at index fi with d elements
starting at index si */
public static void swap(int arr[], int fi,
                        int si, int d) 
{ 
    int i, temp; 
    for(i = 0; i < d; i++) 
    { 
        temp = arr[fi + i]; 
        arr[fi + i] = arr[si + i]; 
        arr[si + i] = temp; 
    } 
} 

// Driver Code
public static void main (String[] args) 
{
    int arr[] = {1, 2, 3, 4, 5, 6, 7}; 
    leftRotate(arr, 2, 7); 
    printArray(arr, 7);     
}
}

// This code is contributed by codeseeker

Python3

# Wrapper over the recursive function leftRotateRec()
# It left rotates arr by d.
def leftRotate(arr, d, n):
    leftRotateRec(arr, 0, d, n);

def leftRotateRec(arr, i, d, n):
    '''
     * Return If number of elements to be 
     rotated is zero or equal to array size
     '''
    if (d == 0 or d == n):
        return;

    '''
     * If number of elements to be rotated 
     is exactly half of array size
     '''
    if (n - d == d):
        swap(arr, i, n - d + i, d);
        return;

    ''' If A is shorter '''
    if (d < n - d):
        swap(arr, i, n - d + i, d);
        leftRotateRec(arr, i, d, n - d);
        ''' If B is shorter '''
    else:
        swap(arr, i, d, n - d);

        ''' This is tricky '''
        leftRotateRec(arr, n - d + i, 2 * d - n, d); 

''' UTILITY FUNCTIONS '''
''' function to pran array '''
def printArray(arr, size):
    for i in range(size):
        print(arr[i], end = " ");
    print();

'''
 * This function swaps d elements starting at 
 * index fi with d elements starting at index si
 '''
def swap(arr, fi, si, d):
    for i in range(d):
        temp = arr[fi + i];
        arr[fi + i] = arr[si + i];
        arr[si + i] = temp;

# Driver Code
if __name__ == '__main__':
    arr = [1, 2, 3, 4, 5, 6, 7];
    leftRotate(arr, 2, 7);
    printArray(arr, 7);

# This code is contributed by Rohit_ranjan

C

using System;

class GFG{

// Wrapper over the recursive function
// leftRotateRec() 
// It left rotates []arr by d.
public static void leftRotate(int []arr, 
                              int d, int n)
{
    leftRotateRec(arr, 0, d, n);
}

public static void leftRotateRec(int []arr, int i, 
                                 int d, int n)
{

    // Return If number of elements 
    // to be rotated is zero or equal
    // to array size
    if(d == 0 || d == n) 
        return; 

    // If number of elements to be rotated 
    // is exactly half of array size 
    if(n - d == d) 
    { 
        swap(arr, i, n - d + i, d); 
        return; 
    } 

    // If A is shorter
    if(d < n - d) 
    { 
        swap(arr, i, n - d + i, d); 
        leftRotateRec(arr, i, d, n - d);     
    } 

    // If B is shorter
    else
    { 
        swap(arr, i, d, n - d); 

        // This is tricky
        leftRotateRec(arr, n - d + i, 
                       2 * d - n, d); 
    } 
}

// UTILITY FUNCTIONS
// Function to print an array 
public static void printArray(int []arr,
                              int size) 
{ 
    int i; 
    for(i = 0; i < size; i++) 
        Console.Write(arr[i] + " "); 

    Console.WriteLine(); 
} 

// This function swaps d elements 
// starting at index fi with d elements
// starting at index si 
public static void swap(int []arr, int fi,
                        int si, int d) 
{ 
    int i, temp; 
    for(i = 0; i < d; i++) 
    { 
        temp = arr[fi + i]; 
        arr[fi + i] = arr[si + i]; 
        arr[si + i] = temp; 
    } 
} 

// Driver Code
public static void Main(String[] args) 
{
    int []arr = { 1, 2, 3, 4, 5, 6, 7 }; 

    leftRotate(arr, 2, 7); 
    printArray(arr, 7);     
}
}

// This code is contributed by amal kumar choubey

迭代实现：

这是相同算法的迭代实现。此处使用相同的工具函数swap()。

C

void leftRotate(int arr[], int d, int n)
{
  int i, j;
  if(d == 0 || d == n)
    return;
  i = d;
  j = n - d;
  while (i != j)
  {
    if(i < j) /*A is shorter*/
    {
      swap(arr, d-i, d+j-i, i);
      j -= i;
    }
    else /*B is shorter*/
    {
      swap(arr, d-i, d, j);
      i -= j;
    }
    // printArray(arr, 7);
  }
  /*Finally, block swap A and B*/
  swap(arr, d-i, d, i);
}

Java

//Java code for above implementation
static void leftRotate(int arr[], int d, int n) 
{ 
int i, j; 
if(d == 0 || d == n) 
    return; 
i = d; 
j = n - d; 
while (i != j) 
{ 
    if(i < j) /*A is shorter*/
    { 
    swap(arr, d-i, d+j-i, i); 
    j -= i; 
    } 
    else /*B is shorter*/
    { 
    swap(arr, d-i, d, j); 
    i -= j; 
    } 
    // printArray(arr, 7); 
} 
/*Finally, block swap A and B*/
swap(arr, d-i, d, i); 
}

Python

# Python3 code for above implementation

def leftRotate(arr, d, n): 
    if(d == 0 or d == n): 
        return; 
    i = d 
    j = n - d 
    while (i != j): 

        if(i < j): # A is shorter
            swap(arr, d - i, d + j - i, i) 
            j -= i 

        else: # B is shorter
            swap(arr, d - i, d, j) 
            i -= j 

    swap(arr, d - i, d, i)

# This code is contributed 
# by Adarsh_Verma

C

// C# code for above implementation 
static void leftRotate(int []arr, int d, int n) 
{ 
    int i, j; 
    if(d == 0 || d == n) 
        return; 
    i = d; 
    j = n - d; 
    while (i != j) 
    { 
        if(i < j) /*A is shorter*/
        { 
            swap(arr, d-i, d+j-i, i); 
            j -= i; 
        } 
        else /*B is shorter*/
        { 
            swap(arr, d-i, d, j); 
            i -= j; 
        } 

    } 

    /*Finally, block swap A and B*/
    swap(arr, d-i, d, i); 
} 

// This code is contributed by Rajput-Ji

时间复杂度：O(n)。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://www.moonapi.com/news/30939.html

dsal 查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-09-27》

分类

最近更新

dsal 数组旋转的块交换算法

数组旋转的块交换算法

C++

C

Java

Python3

C

C

Java

Python

C

留言

联系客服

数据知识

系统公告

开发文档

dsal查看更多书籍

《GeeksForGeeks 数据结构和算法中文教程 2022-09-27》

dsal 数组旋转的块交换算法

数组旋转的块交换算法

C++

C

Java

Python3

C

C

Java

Python

C

留言

联系客服

dsal 查看更多书籍