In-place有不止一个定义。一 严格定义 是
null
就地算法是一种不需要额外空间的算法，它通过变换“就地”输入，在包含数据的同一内存中生成输出。但是，允许为变量使用一个小的常量额外空间。
更多 广义定义 是
就地意味着算法不使用额外的空间来操作输入，但可能需要一个较小但非恒定的额外空间来操作。通常，这个空间是O（对数n），尽管有时O（n）（小于线性）中的任何东西都是允许的。
A. 不到位 数组反转的实现
C++
// An Not in-place C++ program to reverse an array #include <bits/stdc++.h> using namespace std; /* Function to reverse arr[] from start to end*/ void reverseArray( int arr[], int n) { // Create a copy array and store reversed // elements int rev[n]; for ( int i=0; i<n; i++) rev[n-i-1] = arr[i]; // Now copy reversed elements back to arr[] for ( int i=0; i<n; i++) arr[i] = rev[i]; } /* Utility function to print an array */ void printArray( int arr[], int size) { for ( int i = 0; i < size; i++) cout << arr[i] << " " ; cout << endl; } /* Driver function to test above functions */ int main() { int arr[] = {1, 2, 3, 4, 5, 6}; int n = sizeof (arr)/ sizeof (arr[0]); printArray(arr, n); reverseArray(arr, n); cout << "Reversed array is" << endl; printArray(arr, n); return 0; } |
JAVA
// An Not in-place Java program // to reverse an array import java.util.*; class GFG { /* Function to reverse arr[] from start to end*/ public static void reverseArray( int []arr, int n) { // Create a copy array // and store reversed // elements int []rev = new int [n]; for ( int i = 0 ; i < n; i++) rev[n - i - 1 ] = arr[i]; // Now copy reversed // elements back to arr[] for ( int i = 0 ; i < n; i++) arr[i] = rev[i]; } /* Utility function to print an array */ public static void printArray( int []arr, int size) { for ( int i = 0 ; i < size; i++) System.out.print(arr[i] + " " ); System.out.println( "" ); } // Driver code public static void main(String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 }; int n = arr.length; printArray(arr, n); reverseArray(arr, n); System.out.println( "Reversed array is" ); printArray(arr, n); } } // This code is contributed // by Harshit Saini |
Python3
# An Not in-place Python program # to reverse an array ''' Function to reverse arr[] from start to end ''' def reverseArray(arr, n): # Create a copy array # and store reversed # elements rev = n * [ 0 ] for i in range ( 0 , n): rev[n - i - 1 ] = arr[i] # Now copy reversed # elements back to arr[] for i in range ( 0 , n): arr[i] = rev[i] # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] n = len (arr) print ( * arr) reverseArray(arr, n); print ( "Reversed array is" ) print ( * arr) # This code is contributed # by Harshit Saini |
C#
// An Not in-place C# program // to reverse an array using System; class GFG { /* Function to reverse arr[] from start to end*/ public static void reverseArray( int [] arr, int n) { // Create a copy array // and store reversed // elements int [] rev = new int [n]; for ( int i = 0; i < n; i++) rev[n - i - 1] = arr[i]; // Now copy reversed // elements back to arr[] for ( int i = 0; i < n; i++) arr[i] = rev[i]; } /* Utility function to print an array */ public static void printArray( int [] arr, int size) { for ( int i = 0; i < size; i++) Console.Write(arr[i] + " " ); Console.Write( "" ); } // Driver code public static void Main() { int [] arr = {1, 2, 3, 4, 5, 6}; int n = arr.Length; printArray(arr, n); reverseArray(arr, n); Console.WriteLine( "Reversed array is" ); printArray(arr, n); } } // This code is contributed by Ita_c. |
Javascript
<script> // An Not in-place Javascript program // to reverse an array /* Function to reverse arr[] from start to end*/ function reverseArray(arr,n) { // Create a copy array // and store reversed // elements let rev = new Array(n); for (let i = 0; i < n; i++) rev[n - i - 1] = arr[i]; // Now copy reversed // elements back to arr[] for (let i = 0; i < n; i++) arr[i] = rev[i]; } /* Utility function to print an array */ function printArray(arr,size) { for (let i = 0; i < size; i++) document.write(arr[i] + " " ); document.write( "<br>" ); } // Driver code let arr=[1, 2, 3, 4, 5, 6]; let n = arr.length; printArray(arr, n); reverseArray(arr, n); document.write( "Reversed array is<br>" ); printArray(arr, n); // This code is contributed by rag2127 </script> |
输出：
1 2 3 4 5 6 Reversed array is6 5 4 3 2 1
这需要O（n）额外的空间，这是一个非就地算法的例子。 一 到位 反转数组的实现。
C++
// An in-place C++ program to reverse an array #include <bits/stdc++.h> using namespace std; /* Function to reverse arr[] from start to end*/ void reverseArray( int arr[], int n) { for ( int i=0; i<n/2; i++) swap(arr[i], arr[n-i-1]); } /* Utility function to print an array */ void printArray( int arr[], int size) { for ( int i = 0; i < size; i++) cout << arr[i] << " " ; cout << endl; } /* Driver function to test above functions */ int main() { int arr[] = {1, 2, 3, 4, 5, 6}; int n = sizeof (arr)/ sizeof (arr[0]); printArray(arr, n); reverseArray(arr, n); cout << "Reversed array is" << endl; printArray(arr, n); return 0; } |
JAVA
// An in-place Java program // to reverse an array import java.util.*; class GFG { public static int __( int x, int y) { return x;} /* Function to reverse arr[] from start to end*/ public static void reverseArray( int []arr, int n) { for ( int i = 0 ; i < n / 2 ; i++) arr[i] = __(arr[n - i - 1 ], arr[n - i - 1 ] = arr[i]); } /* Utility function to print an array */ public static void printArray( int []arr, int size) { for ( int i = 0 ; i < size; i++) System.out.print(Integer.toString(arr[i]) + " " ); System.out.println( "" ); } // Driver code public static void main(String[] args) { int []arr = new int []{ 1 , 2 , 3 , 4 , 5 , 6 }; int n = arr.length; printArray(arr, n); reverseArray(arr, n); System.out.println( "Reversed array is" ); printArray(arr, n); } } // This code is contributed // by Harshit Saini |
Python3
# An in-place Python program # to reverse an array ''' Function to reverse arr[] from start to end''' def reverseArray(arr, n): for i in range ( 0 , int (n / 2 )): arr[i], arr[n - i - 1 ] = arr[n - i - 1 ], arr[i] # Driver code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] n = len (arr) print ( * arr) reverseArray(arr, n) print ( "Reversed array is" ) print ( * arr) # This code is contributed # by Harshit Saini |
C#
// An in-place C# program // to reverse an array using System; class GFG { public static int __( int x, int y) { return x;} /* Function to reverse arr[] from start to end*/ public static void reverseArray( int []arr, int n) { for ( int i = 0; i < n / 2; i++) arr[i] = __(arr[n - i - 1], arr[n - i - 1] = arr[i]); } /* Utility function to print an array */ public static void printArray( int []arr, int size) { for ( int i = 0; i < size; i++) Console.Write(arr[i] + " " ); Console.WriteLine( "" ); } // Driver code public static void Main(String[] args) { int []arr = new int []{1, 2, 3, 4, 5, 6}; int n = arr.Length; printArray(arr, n); reverseArray(arr, n); Console.WriteLine( "Reversed array is" ); printArray(arr, n); } } /* This code is contributed by PrinciRaj1992 */ |
Javascript
<script> // An in-place Javascript program // to reverse an array function __(x,y) { return x; } /* Function to reverse arr[] from start to end*/ function reverseArray(arr,n) { for (let i = 0; i < n / 2; i++) arr[i] = __(arr[n - i - 1], arr[n - i - 1] = arr[i]); } /* Utility function to print an array */ function printArray(arr,size) { for (let i = 0; i < size; i++) document.write(arr[i] + " " ); document.write( "<br>" ); } // Driver code let arr=[1, 2, 3, 4, 5, 6]; let n = arr.length; printArray(arr, n); reverseArray(arr, n); document.write( "Reversed array is<br>" ); printArray(arr, n); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
1 2 3 4 5 6 Reversed array is6 5 4 3 2 1
这需要O（1）个额外的空间来交换元素，这是就地算法的一个例子。 哪些排序算法到位，哪些没有到位？ 到位： 气泡排序 , 选择排序 , 插入排序 , 希普索尔 . 不到位： 合并排序 .请注意，合并排序需要O（n）额外的空间。 那么…怎么样 快速排序 ? 为什么它被称为“就地”？ 快速排序为递归函数调用使用额外的空间。根据广义定义，它被就地调用，因为所需的额外空间不用于操作输入，而仅用于递归调用。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
