排序国彩网7：3向快速排序（荷兰国旗）国彩网

介绍：

这是一个非常简单的国彩网，如果数组中只有3种不同类型的键，则该国彩网有效。

例如：

如果我们有一个0、1、2的未排序数组，如图{2、0、0、1、1、2、0、2、1}所示，那么简单的解决方案是计算0、1和2的数量，然后将那么多元素放在数组中，但是这种解决方案效率不高。

为了以最小的时间复杂度求解阵列，我们使用“荷兰国旗”国彩网。

国彩网说明：

在此国彩网中，我们考虑一个元素在中间。小于中间元素的元素将向左移动，大于中间元素的元素将向右侧移动。

因此，将自动对数组进行排序。

注意：在某些情况下，中间元素称为枢轴元素。即[0，1，2]中的1是枢轴元素。

国彩网步骤：

Step 1: 
	Set low_index = 0, high_index = n – 1, mid_index =  0;
	The mid variable is going to trace all the elements in the array.

 Step 2:
	We get a[mid] element and perform below steps
	
Case 0: If a[mid] == 0, Then move to the left, by swapping a[ low_index ] and a[  mid_index ].Then increment low_index and mid_index.

Case 1: If a[mid] == 1 [piot element], we don’t do any swapping operation. But we increment mid_index.

Case 2: If a[mid] == 2, Then move to the right, by swapping a[ mid_index ] and a[high_index]. Then decrement high_index.

Step 3: Loop till mid_index > high_index.

注意：在情况2中，我们没有更改mid_index的值。那是因为被high_index交换的元素可能是0。如果它是0，那么我们必须执行将0移到枢轴元素左侧的操作。

让我们借助示例来了解此国彩网：

考虑下面给出的元素

最初的值将如下所示：

当arr [mid] = arr [0] = 2时，您需要将are [mid]与are [high]交换，并将高索引减少1。如下图所示：

现在arr [mid] = are [0] =0。您需要将中索引和低索引都增加1，如下所示：

现在，arr [mid] = arr [1] = 2。将arr [mid]与arr [high]交换并降低高索引，如下所示：

现在arr [mid] = arr [1] =1。将中索引增加1。

现在中索引==高索引。因此数组被排序。

C语言的国彩网解决方案。

#include<stdio.h>


void swap(int *num_1, int *num_2)
{
	int temp;
	temp = *num_1;
	*num_1 = *num_2;
	*num_2 =  temp;
}


void DutchNationalFlagSort(int arr[], int length)
{
	int low_index = 0;
	int mid_index = 0;
	int high_index = length -1;

	while(mid_index <= high_index)
	{
		switch(arr[mid_index])
		{
			// as we know we are dealing with 0, 1, 2. We take 上 ly those cases.

			case 0:
					swap(&arr[low_index], &arr[mid_index]);
					low_index++; mid_index++;
					break;

			case 1:
					mid_index++;
					break;	

			case 2:
					swap(&arr[mid_index], &arr[high_index]);
					high_index--;
					break;
		}

	}

}

void print_array(int arr[], int length)
{

	int itr = 0;

	printf("Sorted array is\n");

	for (itr = 0; itr < length; itr++)
	{
		printf("%d ", arr[itr]);
	}
	printf("\n");
}

int main(int argc, char const *argv[])
{
	int arr [100] = {0};
	int length = 0;
	int itr = 0;

	printf("Enter the length of the array\n");
	scanf("%d", &length);

	for (itr = 0; itr < length; itr++)
	{
		scanf("%d", &arr[itr]);
	}

	DutchNationalFlagSort(arr, length);

	print_array(arr, length);

	return 0;
}

输出：

Enter the length of the array
4
1
2
0
1
Sorted array is
0 1 1 2

因为我们仅使用1个循环，所以时间复杂度为O（n）。

进一步阅读：

AJ关于DS和国彩网的权威指南。单击此处以学习国彩网和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：