資料結構
網路
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 次瀏覽
廣告