Cách sắp xếp mảng chỉ chứa 0 và 1 không dùng bộ nhớ thêm C#

Dùng hai con trỏ low, high. Low ở đầu, high ở cuối mảng.

Nếu arr[low] = 0, không cần hoán đổi.

Nếu arr[low] = 1, hoán đổi với arr[high], giảm high.

Độ phức tạp thời gian - O(N)

Ví dụ

using System;

namespace ConsoleApplication
{
    public class Arrays
    {
        public void SwapZerosOnes(int[] arr)
        {
            int low = 0;
            int high = arr.Length - 1;
            while (low < high)
            {
                if (arr[low] == 1)
                {
                    Swap(arr, low, high);
                    high--;
                }
                else
                {
                    low++;
                }
            }
        }

        private void Swap(int[] arr, int pos1, int pos2)
        {
            int temp = arr[pos1];
            arr[pos1] = arr[pos2];
            arr[pos2] = temp;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Arrays a = new Arrays();
            int[] arr1 = { 0, 1, 1, 0, 1, 1 };
            a.SwapZerosOnes(arr1);
            for (int i = 0; i < arr1.Length; i++)
            {
                Console.WriteLine(arr1[i]);
            }
        }
    }
}

Kết quả

0
0
1
1
1
1

Giải thích: Sắp xếp mảng nhị phân {0,1,1,0,1,1} → {0,0,1,1,1,1} in-place. Two-pointer: low tìm 1, high tìm 0, hoán đổi. Tương tự partition trong QuickSort. Chỉ duyệt một lần O(N).