×

Thuật toán Merge Sort để sắp xếp mảng số nguyên trong C#

Để viết thuật toán Merge Sort để sắp xếp một mảng số nguyên trong C#, bạn có thể làm theo các bước sau. Merge Sort là một thuật toán chia để trị, chia mảng thành hai nửa, sắp xếp từng nửa và sau đó hợp nhất chúng lại.

Dưới đây là mã nguồn C# cho thuật toán Merge Sort:

using System;

class MergeSortExample
{
    // Hàm chính để sắp xếp mảng
    public static void MergeSort(int[] array)
    {
        if (array.Length <= 1)
            return;

        int mid = array.Length / 2;
        int[] left = new int[mid];
        int[] right = new int[array.Length - mid];

        Array.Copy(array, 0, left, 0, mid);
        Array.Copy(array, mid, right, 0, array.Length - mid);

        MergeSort(left);
        MergeSort(right);
        Merge(array, left, right);
    }

    // Hàm hợp nhất hai mảng đã sắp xếp lại
    private static void Merge(int[] array, int[] left, int[] right)
    {
        int leftIndex = 0, rightIndex = 0, arrayIndex = 0;

        while (leftIndex < left.Length && rightIndex < right.Length)
        {
            if (left[leftIndex] <= right[rightIndex])
            {
                array[arrayIndex] = left[leftIndex];
                leftIndex++;
            }
            else
            {
                array[arrayIndex] = right[rightIndex];
                rightIndex++;
            }
            arrayIndex++;
        }

        while (leftIndex < left.Length)
        {
            array[arrayIndex] = left[leftIndex];
            leftIndex++;
            arrayIndex++;
        }

        while (rightIndex < right.Length)
        {
            array[arrayIndex] = right[rightIndex];
            rightIndex++;
            arrayIndex++;
        }
    }

    static void Main(string[] args)
    {
        int[] array = { 38, 27, 43, 3, 9, 82, 10 };
        Console.WriteLine("Mảng trước khi sắp xếp: " + string.Join(", ", array));

        MergeSort(array);

        Console.WriteLine("Mảng sau khi sắp xếp: " + string.Join(", ", array));
    }
}

Giải thích:

  1. MergeSort Method: Hàm này là phần chính của thuật toán Merge Sort. Nó chia mảng thành hai nửa, sắp xếp từng nửa và sau đó hợp nhất chúng lại bằng hàm Merge.

  2. Merge Method: Hàm này hợp nhất hai mảng đã được sắp xếp. Nó sử dụng ba chỉ số để theo dõi vị trí trong mảng left, rightarray.

  3. Main Method: Đây là điểm bắt đầu của chương trình. Nó khởi tạo một mảng, in ra mảng trước và sau khi sắp xếp bằng Merge Sort.

Chạy chương trình sẽ in ra mảng trước và sau khi sắp xếp để bạn có thể thấy kết quả của thuật toán Merge Sort.

Comments