数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究如何使用 C# 在不使用额外空间的情况下在数组中对 0、1、2进行排序（荷兰国旗）？
我们需要采用三位指针：low、mid、high。我们将在开始时使用 low 和 mid 指针，high 指针指向给定数组的末尾。
如果 array[mid] = 0，则将 array[mid] 与 array[low] 交换，并在一次操作中增加两个指针。
如果 array[mid] = 1，则不需要交换。在一次操作中增加 mid 指针。
如果 array[mid] = 2，则将 array[mid] 与 array[high] 交换，并在一次操作中减少 high 指针。
时间复杂度 − O(N)
示例
using System;
namespace ConsoleApplication{
public class Arrays{
private void Swap(int[] arr, int pos1, int pos2){
int temp = arr[pos1];
arr[pos1] = arr[pos2];
arr[pos2] = temp;
}
public void DutchNationalFlag(int[] arr){
int low = 0;
int mid = 0;
int high = arr.Length - 1;
while (mid <= high){
if (arr[mid] == 0){
Swap(arr, low, mid);
low++;
mid++;
}
else if (arr[mid] == 2){
Swap(arr, high, mid);
high--;
}
else{
mid++;
}
}
}
}
class Program{
static void Main(string[] args){
Arrays a = new Arrays();
int[] arr = { 2, 1, 1, 0, 1, 2, 1, 2, 0, 0, 1 };
a.DutchNationalFlag(arr);
for (int i = 0; i < arr.Length; i++){
Console.WriteLine(arr[i]);
}
Console.ReadLine();
}
}
}输出
0 0 0 0 1 1 1 1 2 2 2
更新时间： 27-8-2021
185 次浏览
广告