对 0、1 和 2 的数组进行排序

2025年3月17日 | 阅读 21 分钟

数组是一种线性数据结构，包含存储在连续内存位置的元素。它主要存储相同数据类型的元素。这些连续内存位置之间的差异取决于我们使用的数据类型，例如 **int、float、double、char、long** 等。位于连续内存位置的元素使我们能够轻松地跟踪元素。与链表、队列、堆栈等其他数据结构以及树和图等非线性数据结构相比，它还降低了搜索元素的复杂度。

可以轻松选择数组的基索引。通常，允许 n 索引的编程语言也允许负索引值，而其他标量数据类型，如枚举或字符，可用作数组索引。数组包含索引，从 0 开始，一直到数组大小减一。如果我们有一个包含 12 个元素的数组，那么数组的索引将从 0 开始，一直到索引号 11。

排序数组意味着数组中的元素必须以特定顺序存在，无论是升序还是降序。例如，如果我们有一个包含 5 个元素的数组，如下所示：4、2、3、10、5。现在，如果我希望这个数组被排序，它将默认按升序排列，结果将是 - 2、3、4、5、10。我们将使用各种排序方法来对数组元素进行排序，例如 **冒泡排序、插入排序、快速排序和归并排序**。在这些复杂度中，快速排序和归并排序在排序方法中起着非常重要的作用。

什么是包含 0、1 和 2 的数组？

正如我们已经看到的，数组是一种线性数据结构，包含存储在连续内存位置的相同数据类型的数据。在这里，在包含 0、1 和 2 的数组中，我们将仅以 0、1 和 2 的形式存储数据。例如，一个包含 11 个元素的数组，这些元素如下 - 0、1、1、2、2、1、0、2、1、0、0。

如果我们谈论排序包含 0、1 和 2 形式元素的数组，则意味着 **排列数组中的元素** 按升序或降序。在这里，我们将升序视为默认情况。让我们看一个包含 10 个元素的数组，该数组包含 0、1 和 2 形式的元素。

我们需要执行的主要任务是排序数组，以便所有 0 都排在所有 1 之前，所有 1 都排在所有 2 之前，最后，所有 2 将填充剩余的数组。

A = { 0, 1, 2, 2, 0, 1, 0, 2, 1, 0 }

数组 **A 的排序版本 = { 0, 0, 0, 0, 1, 1, 1, 2, 2, 2 }**

B = { 0, 1, 2, 1, 0, 1, 0, 2, 1, 0 }

数组 **B 的排序版本 = { 0, 0, 0, 0, 1, 1, 1, 1, 2, 2 }**

排序包含 0、1 和 2 的数组的方法 -

通过 **蛮力法** 使用双重遍历。
使用一种高效的方法，使用一种名为 **三向分区** 的单次遍历方法。

让我们开始使用这些方法对数组进行排序 -

方法 # 1 - 使用双重遍历的蛮力法

使用此方法，我们需要对包含 0、1 和 2 的数组进行升序排序。但是，这取决于程序员是想对数组进行升序还是降序排序；我们将按默认情况，即升序进行排序。

我们将为 ' n ' 个元素推导出算法，但我们将取一个随机数组并对其进行实验，以基本理解概念。

A = { 0, 1, 0, 2, 1, 1, 0, 2, 2, 0, 1 }

程序步骤 -

首先，计算给定数组中元素的总数；这里，我们给出了一个包含 11 个元素的数组。
从左到右扫描数组的元素，逐个跟踪元素。
然后计算数组中存在的 0 的数量，并将其存储在一个变量中。
类似地，以这种方式，计算数组中存在的 1 的数量，并将它们存储在另一个变量中。
最后，计算数组中存在的 2 的所有数量，并将计数存储在另一个变量中。或者，要知道数组中存在的 2 的数量，您可以从数组中存在的总元素数量中减去 0 和 1 的计数数量。
您可以在此示例中仅执行此标准，因为我们已经知道了数组，但如果用户在运行时输入数组的元素。您不确定用户输入的那些值是否仅以 0、1 和 2 的形式存在，直到用户受到条件约束，只能以 0、1 和 2 的形式输入值。
在上面的示例中，我们有 4 个 0、4 个 1 和 3 个 2。
在计算完数组中存在的 0、1 和 2 的数量后，再次将值逐个复制到数组 A 中。
为了复制值，启动一个最初指向数组第 0 个索引的循环；首先，复制数组中存在的 0 的所有数量，同时递增索引值。所有 0 将被复制到索引号 3。
然后，为了复制所有 2 的数量，将指针指向索引 4，因为在索引 0 到 3 中，我们有所有 0。现在，复制数组中的所有 1，同时逐个递增索引。在我们上面的示例中，有 4 个 1；因此，在复制所有 1 之后，我们的索引将达到 7。
为了将所有 2 复制到数组中，从索引 8 开始，因为直到索引 7 我们有所有 0，之后我们有所有 1。现在将所有 2 复制到数组中，同时逐个递增索引。在我们上面的示例中，有 3 个 2；因此，在复制所有 2 之后，我们的索引将达到 10。
因此，最后，我们成功地以升序将所有 0、1 和 2 的数量复制到了数组中。

使用计数方法（即方法 # 1）将包含 0、1 和 2 形式元素的数组按升序排序的算法。

步骤 1 - 考虑一个包含 n 个元素的数组，所有元素都以 0、1 和 2 的形式存在。

步骤 2 - 构建一个排序 0、1 和 2 数组的函数。

步骤 3 - 从主函数将数组和元素的总数作为参数传递给排序函数。

步骤 4 - 在排序函数中，声明三个变量，分别命名为 zero_count、one_count 和 two_count。

步骤 5 - 变量 zero_count 存储从主函数作为参数传递的数组中所有零的数量。

步骤 6 - 变量 one_count 存储从主函数作为参数传递的数组中所有一的数量。

步骤 7 - 变量 two_count 存储从主函数作为参数传递的数组中所有二的数量。

步骤 8 - 在计算完数组中的所有 0、1 和 2 之后，将所有值重新插入到给定的主数组中，因为我们需要对数组进行排序。

步骤 9 - 最初，将所有零放回传递给主函数中作为参数的数组。

步骤 10 - 在从连续索引号处放置所有零之后，将所有一放回数组。

步骤 11 - 类似地，最后，将所有二放回数组的剩余索引处。

步骤 12 - 最后，在主函数中，打印排序后的数组。

现在，让我们在 C、C++ 和 Python 中执行上述方法 1，即蛮力双重遍历法。

使用方法 1 在 C 编程语言中排序包含 0、1、2 的数组的程序 -

//  To sort an array of 0's, 1's, and 2's

#include<stdio.h>
void sort_array_0_1_2 ( int A[ ] , int n )  
{
	int i = 0 ,  countzero = 0 , countone = 0 ,  counttwo = 0 ;
	while ( i < n )
	{
		if ( A [ i ] == 0 )
		{
			countzero = countzero + 1 ;
		}
		else if ( A [ i ] == 1 )
		{
			countone = countone + 1 ;
		}
		else
		{
			counttwo = counttwo + 2 ;
		}
		i = i + 1 ;
	}
	for  ( i = 0 ; i < countzero ; i++ )
	{
		A [ i ] = 0 ;
	}
	for ( i = countzero ; i < countzero + countone ; i++ )
	{
		A [ i ] = 1 ;
	}
	for ( i = countzero + countone ; i < n ; i++ )
	{
		A [ i ] = 2 ;
	}
}
void main()
{
	int i ,  A[ 100 ] , n;
	printf ( " Enter number of elements present in the array: " ) ;
	scanf ( " %d " , &n) ;
	printf ( " Enter array:  \n " ) ;
	for ( i = 0 ; i < n ; i++ )
	{
		scanf ( " %d " , &A[ i ] ) ;
	}
	printf  ( " Array after sorting : \n " ) ;
	sort_array_0_1_2 ( A , n ) ;
	for ( i = 0 ; i < n ; i++ )
	{
		printf ( " %d \n " , A [ i ] ) ;
	}
	
}

使用方法 # 1 对包含 0、1、2 的数组进行排序的 C 程序输出

使用方法 1 在 C++ 编程语言中排序包含 0、1、2 的数组的程序 -

//  To sort an array of 0's, 1's, and 2's

#include<iostream>
using namespace std;
void sort_array_0_1_2( int A[ ] , int n )  
{
	int i = 0 ,  countzero = 0 , countone = 0 ,  counttwo = 0 ;
	while ( i < n )
	{
		if ( A [ i ] == 0 )
		{
			countzero = countzero + 1 ;
		}
		else if ( A [ i ] == 1 )
		{
			countone = countone + 1 ;
		}
		else
		{
			counttwo = counttwo + 2 ;
		}
		i = i + 1 ;
	}
	for  ( i = 0 ; i < countzero ; i++ )
	{
		A [ i ] = 0 ;
	}
	for ( i = countzero ; i < countzero + countone ; i++ )
	{
		A [ i ] = 1 ;
	}
            for ( i = countzero + countone ; i < n ; i++ )
	{
		A [ i ] = 2 ;
	}
}
int main()
{
	int  i ,  A[ 100 ] , n ;
	cout << " Enter number of elements present in the array: " << endl ;
	cin >> n ;
	cout << " Enter array:  "  <<  endl ;
	for ( i = 0 ; i < n ; i++ )
	{
		cin >> A [  i  ] ;
	}
	cout << " Array after sorting : \n " << endl ;
	sort_array_0_1_2 ( A , n ) ;
	for ( i = 0 ; i < n ; i++ )
	{
		cout <<  A  [  i  ] << endl ;
	}
	return 0;
	
}

使用方法 # 1 对包含 0、1、2 的数组进行排序的 C++ 程序输出

使用方法 1 在 Python 编程语言中排序包含 0、1、2 的数组的程序 -

#  To sort an array of 0's, 1's, and 2's

def sort_array_0s_1s_2s(A,n):
  i=0
  countzero=0
  countone=0
  counttwo=0
  while(i<n):
    if (A[i]==0):
      countzero=countzero+1
    elif (A[i]==1):
      countone=countone+1
    else:
      counttwo=counttwo+1
    i=i+1
  i=0
  while(i<countzero):
    A[i]=0
    i=i+1
  i=countzero
  while(i<countzero+countone):
    A[i]=1
    i=i+1
  i=countzero+countone
  while(i<n):
    A[i]=2
    i=i+1

print("Enter size of an array: ")
n=int(input())
print("Enter array elements: \n")
i=0
A=[]
while(i<n):
  ele=int(input())
  A.append(ele)
  i=i+1
print("Array after sorting: \n")
sort_array_0s_1s_2s(A,n)
i=0
for i in A:
  print(i)

使用方法 # 1 对包含 0、1、2 的数组进行排序的 Python 程序输出

使用方法 1 在 Java 编程语言中排序包含 0、1、2 的数组的程序 -

//  To sort an array of 0's, 1's, and 2's

import java.util.Scanner ;  
class Array 
{  
static void sortarray ( int [] array , int n )
{
	int countzero = 0 ;
	int countone = 0 ;
	int counttwo = 0 ;
	int i = 0 ;
	while ( i < n )
	{
		if ( array [ i ] == 0 )
		{
			countzero = countzero + 1 ;
		}
		if ( array[ i ] == 1 )
		{
			countone = countone + 1 ;
		}
                       if ( array[ i ] == 2 )
		{
			counttwo = counttwo + 1 ;
		}
		i = i + 1 ;
	}
	i = 0 ;
	while ( i < countzero )
	{
		array[ i ] = 0 ;
		i = i + 1 ;
	}
	while ( i < countone + countzero )
	{
		array[ i ] = 1 ;
		i = i + 1 ;
	}
	while ( i < counttwo + countone + countzero )
	{
		array[ i ] = 2 ;
		i = i + 1 ;
	}
}
public static void main ( String args[] )  
{  
 int n ;
 Scanner sc = new Scanner ( System.in ) ;
 System.out.println ( " Enter number of elements :  " ) ;
 n = sc.nextInt() ;
 int [] array = new int[ 100 ] ;
 System.out.println ( " Enter elements of the array :  " ) ;
 for ( int i = 0 ; i < n ; i++ )
 {
	 array[ i ] = sc.nextInt() ;
 }
 sortarray( array , n ) ;
 System.out.println ( " Array after sorting : " ) ;
  for ( int i = 0 ; i < n ; i++ )
 {
	 System.out.println ( array[ i ] ) ;
 }
}  
}  

使用方法 # 1 对包含 0、1、2 的数组进行排序的 JAVA 程序输出

在特定编程语言中成功执行程序并遵循使用双重遍历方法的蛮力算法后，我们将获得正确的结果，即 **将数组升序排序**。

现在，让我们分析我们应用以将数组升序排序的算法的运行时间和性能，方法是找出算法的时间复杂度和空间复杂度，即方法 # 1。

方法 # 1 的时间复杂度 -

为了找到时间复杂度，我们需要观察算法并分析执行特定行所需的时间。我们可以观察到，我们需要遍历数组两次；一次遍历用于计算 0、1 和 2 的数量。计数后，第二次遍历用于将排序后的值复制回数组，为此，我们需要复制 n 个元素。因此，时间复杂度将是 -

T ( n ) = O ( n ) + O ( n )

T ( n ) = O ( n )

因此，时间复杂度将为 O ( n )，因为我们给出了一个渐进的粗略想法，即我们需要 ' n ' 时间来解决 ' n ' 个元素的问题。

方法 # 1 的空间复杂度 -

为了找到空间复杂度，我们需要观察程序并分析存储所有变量所需的空间。当我们注意到程序时，我们会发现不需要额外的空间来存储元素。

S ( n ) = O ( 1 )

因此，上述方法 # 1 的空间复杂度将是常数。

方法 # 2 - 使用单次遍历进行三向分区优化方法

使用此方法，我们需要对包含 0、1 和 2 的数组进行升序排序；但是，这取决于程序员是想将数组升序还是降序排序；在这里，我们将按默认情况，即升序进行排序。

首先，每个程序员脑海中都会想到方法 1 的方法，我们将先遍历数组，然后在一个遍历中计算数组中给定的元素有多少个 0、1 和 2。我们将再次遍历数组，并将元素按顺序复制到数组中。最后，正如我们上面已经看到的，我们需要对给定数组进行两次遍历才能对数组元素进行排序。

在此三向分区方法中，我们只需要遍历一次，并且在遍历过程中，我们将整个数组按升序排序。此方法将使用三个指针将数组划分为四个部分，即 **low、mid** 和 **high**。

这四个指针如下 -

区域 1 - 在 low 指针之前，即 0 到 low - 1，我们有数组的一个特定区域，其中包含所有值为 0 的元素。
区域 2 - 在 low 之后和 mid 之前，即 low 到 mid - 1，我们有数组的另一个特定区域，其中包含所有值为 1 的元素。
区域 3 - 在 mid 之后和 high 之前，即 mid 到 high - 1，我们有数组的另一个区域，其中包含我们不知道其值的元素，因此是我们无法预测的值。
区域 4 - 在 high 之后，它将达到 n-1，意味着直到给定数组的最后一个索引，即 high 到 n - 1，我们有数组的最后一个特定区域，其中包含所有值为 2 的元素。

在对每个区域进行分区之前，请考虑一点，即分区是基于特定标准进行的，即，让我们以区域 1 为例；在区域 1 中，我们需要将数组划分为一个区域，该区域从索引 0 开始，到 low - 1 结束。我们可以定义它的范围为 - **[ 0, low )**，这意味着我们不包括索引 **' low '** 在 **区域 1** 中。

类似地，在 **区域 2** 中，我们可以将范围定义为从 low 到 mid - 1，即 **[ low, mid )**，这意味着我们不能包含数字 **' mid '** 的索引。

同样，我们有 **区域 3** 的范围，即 **[ mid, high )**，这意味着我们不能包含数字 **' high '** 的索引。

最后，我们可以定义最后一个 **区域 4** 的范围，即 **[ high, n )**，这意味着我们不能包含数字 **' n '** 的索引。

我们将为 ' n ' 个元素推导出算法，但我们将取一个随机数组并对其进行实验，以基本理解概念。

A = { 0, 1, 0, 2, 1, 1, 0, 2, 2, 0, 1 }

程序步骤 -

首先，计算给定数组中元素的总数；这里，我们给出了一个包含 11 个元素的数组。
我们需要三个指针将数组划分为四个区域，正如我们在上面看到的四个区域的机制。
在初始点，我们无法区分哪个区域包含所有零，哪个区域包含所有一，以及哪个区域包含所有二。
因此，最初，我们将从索引 0 开始两个指针，使得 low = 0 且 mid = 0。
对于 high，我们将其指向给定数组的最后一个索引，即 high = 11 - 1 = 10。
之后，我们将运行循环，从 mid 到 high，根据上面的示例，从 0 到 10。
在此循环中，我们将检查 mid 指针指向给定数组中该特定索引。
如果 mid 指针指向值 0，我们将首先交换指针 mid 处的值与指针 low 处的值。之后，我们将 low 指针递增 1，mid 指针递增 1，并继续循环。
如果 mid 指针指向值 1，我们将 mid 递增 1，并继续循环。
如果 mid 指针指向值 2，我们将首先交换指针 mid 处的值与指针 high 处的值。之后，我们将 high 指针递减 1，并继续循环。
此循环将一直处理到 mid 到达 high 指针。
因此，最后，我们将得到排序后的数组作为结果。

使用方法 2（即方法 # 2）将包含 0、1 和 2 形式元素的数组按升序排序的算法。

步骤 1 - 考虑一个包含 n 个元素的数组，所有元素都以 0、1 和 2 的形式存在。

步骤 2 - 构建一个排序 0、1 和 2 数组的函数。

步骤 3 - 从主函数将数组和元素的总数作为参数传递给排序函数。

步骤 4 - 在排序函数中，声明三个变量，分别命名为 low、mid 和 high。

步骤 5 - 将这些变量初始化为 low = 0、mid = 0 和 high = n - 1。

步骤 6 - 运行循环直到 mid <= high。

步骤 7 - 如果 A [ mid ] == 0，那么我们将索引 low 处的元素与索引 mid 处的元素交换，然后将 low 递增 1，即 low = low + 1，并将 mid 递增 1，即 mid = mid + 1。

步骤 8 - 继续。

步骤 9 - 如果 A [ mid ] == 1，那么我们将 mid 递增 1，即 mid = mid + 1。

步骤 10 - 继续

步骤 11 - 如果 A [ mid ] == 2，我们交换索引 mid 处的元素与索引 high 处的元素，然后将 high 递减 1，即 high = high - 1。

步骤 12 - 继续。

步骤 13 - 最后，在主函数中打印排序后的数组。

现在，让我们在 C、C++ 和 Python 中执行上述方法 1，即蛮力双重遍历法。

使用方法 2 在 C 编程语言中排序包含 0、1、2 的数组的程序 -

//  To sort an array of 0's, 1's, and 2's

#include<stdio.h>
void swap ( int *x , int *y )
{
	int temp ;
	temp = *x ;
	*x = *y ;
	*y = temp;	
}
void sort_array_0_1_2 ( int A[ ] , int n )  
{
	int low = 0 , mid = 0 ,  high = n - 1 ;
	while ( mid <= high )
	{
		if ( A [ mid ] == 0 )
		{
			swap ( &A [ low ] , &A [ mid ] ) ;
			low = low + 1 ;
			mid = mid + 1 ;
		}
		else if ( A [ mid ] == 1 )
		{
			mid = mid + 1 ;
		}
		else 
		{
			swap ( &A [ high ] , &A [ mid ] ) ;
			high = high - 1  ;	
		}
	}
}
void main()
{
	int i ,  A[ 100 ] , n;
	printf ( " Enter number of elements present in the array: " ) ;
	scanf ( " %d " , &n) ;
	printf ( " Enter array:  \n " ) ;
	for ( i = 0 ; i < n ; i++ )
	{
		scanf ( " %d " , &A[ i ] ) ;
	}
	printf  ( " Array after sorting : \n " ) ;
	sort_array_0_1_2 ( A , n ) ;
	for ( i = 0 ; i < n ; i++ )
	{
		printf ( " %d \n " , A [ i ] ) ;
	}
	
}

使用方法 # 2 对包含 0、1、2 的数组进行排序的 C 程序输出

使用方法 2 在 C++ 编程语言中排序包含 0、1、2 的数组的程序 -

//  To sort an array of 0's, 1's, and 2's

#include<iostream>
using namespace std;
void swap ( int *x  , int *y )
{
	int temp ;
	temp = *x ;
	*x = *y ;
	*y = temp;	
}
void sort_array_0_1_2 ( int A[ ] , int n )  
{
	int low = 0 , mid = 0 ,  high = n - 1 ;
	while ( mid <= high )
	{
		if ( A [ mid ] == 0 )
		{
			swap ( &A [ low ] , &A [ mid ] ) ;
			low = low + 1 ;
			mid = mid + 1 ;
		
		}
		else if ( A [ mid ] == 1 )
		{
			mid = mid + 1 ;
		}
		else 
		{
			swap ( &A [ high ] , &A [ mid ] ) ;
			high = high - 1 ;	
		}
	}
}
int main()
{
	int i ,  A[ 100 ] , n;
	cout << " Enter number of elements present in the array: " << endl;
	cin >> n;
	cout << " Enter array:  " << endl;
	for ( i = 0 ; i < n ; i++ )
	{
		cin >> A [ i ];
	}
	cout << " Array after sorting : \n " << endl ;
	sort_array_0_1_2 ( A , n ) ;
	for ( i = 0 ; i < n ; i++ )
	{
		cout << A [ i ] << endl ;
	}
	return 0 ;
}

使用方法 # 2 对包含 0、1、2 的数组进行排序的 C++ 程序输出

使用方法 1 在 Python 编程语言中排序包含 0、1、2 的数组的程序 -

#  To sort an array of 0's, 1's, and 2's

def sort_array_0s_1s_2s(A,n):
  i=0
  low = 0
  mid = 0
  high = n-1
  while (mid<=high):
    if (A[mid]==0):
      temp=A[mid]
      A[mid]=A[low]
      A[low]=temp
      low = low + 1
      mid = mid + 1
    elif (A[mid]==1):
      mid = mid + 1
    else:
      temp=A[mid]
      A[mid]=A[high]
      A[high]=temp
      high = high - 1

print("Enter size of an array: ")
n=int(input())
print("Enter array elements: \n")
i=0
A=[]
while(i<n):
  ele=int(input())
  A.append(ele)
  i=i+1
print("Array after sorting: \n")
sort_array_0s_1s_2s(A,n)
i=0
for i in A:
  print(i)

使用方法 # 2 对包含 0、1、2 的数组进行排序的 Python 程序输出

使用方法 2 在 Java 编程语言中排序包含 0、1、2 的数组的程序 -

//  To sort an array of 0's, 1's, and 2's

import java.util.Scanner ;  
class Array 
{  
static void sortarray ( int [] A , int n )
{
	int low = 0 ;
	int mid = 0 ;
	int high = n - 1 ;
	while ( mid <= high )
	{
		if ( A [ mid ] == 0 )
		{
			int temp = A [ mid ] ;
			A [ mid ] = A [ low ];
			A [ low ] = temp ;
			low = low + 1 ;
			mid = mid + 1 ;
		
		}
		else if ( A [ mid ] == 1 )
		{
			mid = mid + 1 ;
		}
		else 
		{
			int temp = A [ mid ] ;
			A [ mid ] = A [ high ] ;
			A [ high ] = temp ;
			high = high - 1 ;
			
		}
	}	
}
public static void main ( String args[] )  
{  
 int n ;
 Scanner sc = new Scanner ( System.in ) ;
 System.out.println ( " Enter number of elements :  " ) ;
 n = sc.nextInt() ;
 int [] array = new int[ 100 ] ;
 System.out.println ( " Enter elements of the array :  " ) ;
 for ( int i = 0 ; i < n ; i++ )
 {
	 array[ i ] = sc.nextInt() ;
 }
 sortarray( array , n ) ;
 System.out.println ( " Array after sorting : " ) ;
  for ( int i = 0 ; i < n ; i++ )
 {
	 System.out.println ( array[ i ] ) ;
 }
}  
}  

使用方法 # 2 对包含 0、1、2 的数组进行排序的 JAVA 程序输出

在特定编程语言中成功执行程序并遵循使用单次遍历方法的三向分区优化算法后，我们将获得正确的结果，即按升序排序数组。

现在，让我们分析我们应用以将数组升序排序的算法的运行时间和性能，方法是找出算法的时间复杂度和空间复杂度，即方法 # 1。

方法 # 2 的时间复杂度 -

为了找到时间复杂度，我们需要观察算法并分析执行特定行所需的时间。我们可以观察到，我们需要仅遍历一次数组，以将 mid 索引处的值与 0、1 和 2 进行比较。我们将根据上述条件应用必要的运算。遍历完成后，我们将得到排序后的数组作为结果。因此，时间复杂度将是 -

T ( n ) = C + O ( n )

T ( n ) = O ( n )

这里 ' C ' 是交换和将值赋给变量所需的任何常数时间。

因此，时间复杂度将是 O ( n )，因为我们进行渐近的粗略估计，即我们需要 ' n ' 时间来解决 ' n ' 个元素的问题。

方法 # 2 的空间复杂度 -

为了找出空间复杂度，我们需要观察程序并分析存储所有变量所需的空间；当我们注意到程序时，我们将观察到不需要额外的空间来存储元素。

S ( n ) = O ( 1 )

因此，上述方法 # 2 的空间复杂度将是常数。

下一主题股票跨度问题

对 0、1 和 2 的数组进行排序

什么是包含 0、1 和 2 的数组？

排序包含 0、1 和 2 的数组的方法 -

方法 # 1 - 使用双重遍历的蛮力法

使用方法 1 在 C 编程语言中排序包含 0、1、2 的数组的程序 -

使用方法 1 在 C++ 编程语言中排序包含 0、1、2 的数组的程序 -

使用方法 1 在 Python 编程语言中排序包含 0、1、2 的数组的程序 -

使用方法 1 在 Java 编程语言中排序包含 0、1、2 的数组的程序 -

方法 # 2 - 使用单次遍历进行三向分区优化方法

使用方法 2 在 C 编程语言中排序包含 0、1、2 的数组的程序 -

使用方法 2 在 C++ 编程语言中排序包含 0、1、2 的数组的程序 -

使用方法 1 在 Python 编程语言中排序包含 0、1、2 的数组的程序 -

使用方法 2 在 Java 编程语言中排序包含 0、1、2 的数组的程序 -

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

对 0、1 和 2 的数组进行排序

什么是包含 0、1 和 2 的数组？

排序包含 0、1 和 2 的数组的方法 -

方法 # 1 - 使用双重遍历的蛮力法

使用方法 1 在 C 编程语言中排序包含 0、1、2 的数组的程序 -

使用方法 1 在 C++ 编程语言中排序包含 0、1、2 的数组的程序 -

使用方法 1 在 Python 编程语言中排序包含 0、1、2 的数组的程序 -

使用方法 1 在 Java 编程语言中排序包含 0、1、2 的数组的程序 -

方法 # 2 - 使用单次遍历进行三向分区优化方法

使用方法 2 在 C 编程语言中排序包含 0、1、2 的数组的程序 -

使用方法 2 在 C++ 编程语言中排序包含 0、1、2 的数组的程序 -

使用方法 1 在 Python 编程语言中排序包含 0、1、2 的数组的程序 -

使用方法 2 在 Java 编程语言中排序包含 0、1、2 的数组的程序 -

相关帖子

后缀表达式到前缀表达式的转换

按行和列排序的矩阵中的所有元素排序输出

按字母顺序打印每个字符的频率

检查给定大小为 n 的数组是否可以表示 n 层的 BST

二进制转对称

到达目的地所需的最小初始点数

DS 中的垃圾回收

根据其对偶和数组构建数组

JavaScript 中图的实现

检查两棵二叉搜索树是否相同

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器