Sắp xếp trộn (Merge Sort) trong C#

Bài tập C#: Sắp xếp trộn (Merge Sort)

Viết chương trình C# minh họa giải thuật Sắp xếp trộn (Merge Sort)

Sắp xếp trộn (Merge Sort) là một giải thuật sắp xếp dựa trên giải thuật Chia để trị (Divide and Conquer). Với độ phức tạp thời gian trường hợp xấu nhất là Ο(n log n) thì đây là một trong các giải thuật đáng được quan tâm nhất.

Đầu tiên, giải thuật sắp xếp trộn chia mảng thành hai nửa và sau đó kết hợp chúng lại với nhau thành một mảng đã được sắp xếp.

Để tham khảo chi tiết về lý thuyết cũng như hình ảnh minh họa cho giải thuật Sắp xếp trộn (Merge Sort), mời bạn tham khảo chương: Sắp xếp trộn (Merge Sort) trong C có trên trang của chúng mình.

Chương trình C#

Dưới đây là chương trình C# minh họa giải thuật Sắp xếp trộn (Merge Sort) trong C#:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text; namespace VietJackCsharp
{
    class TestCsharp
    {
        static void Main(string[] args)
        {
            List unsorted = new List();
            List sorted;            Random random = new Random();            Console.WriteLine("Sap xep tron (Merge Sort) trong C#:");
            Console.WriteLine("------------------------------------");            Console.WriteLine("In mang ban dau:");
            for (int i = 0; i < 10; i++)
            {
                unsorted.Add(random.Next(0, 100));
                Console.Write(unsorted[i] + " ");
            }
            Console.WriteLine();            sorted = MergeSort(unsorted);            Console.WriteLine("\nIn mang da qua sap xep: ");
            foreach (int x in sorted)
            {
                Console.Write(x + " ");
            }
            Console.Write("\n");            Console.ReadKey();
        }
        private static List MergeSort(List unsorted)
        {
            if (unsorted.Count <= 1)
                return unsorted;            List left = new List();
            List right = new List();            int middle = unsorted.Count / 2;
            for (int i = 0; i < middle; i++)  //chia danh sach chua qua sap xep  
            {
                left.Add(unsorted[i]);
            }
            for (int i = middle; i < unsorted.Count; i++)
            {
                right.Add(unsorted[i]);
            }            left = MergeSort(left);
            right = MergeSort(right);
            return Merge(left, right);
        }        private static List Merge(List left, List right)
        {
            List result = new List();            while (left.Count > 0 || right.Count > 0)
            {
                if (left.Count > 0 && right.Count > 0)
                {
                    if (left.First() <= right.First())  //so sanh hai phan tu dau tien  
                    {                                   //de xem phan tu nao nho hon
                        result.Add(left.First());
                        left.Remove(left.First());      //phan con lai cua list, ngoai tru  
                    }                                   //phan tu dau tien
                    else
                    {
                        result.Add(right.First());
                        right.Remove(right.First());
                    }
                }
                else if (left.Count > 0)
                {
                    result.Add(left.First());
                    left.Remove(left.First());
                }
                else if (right.Count > 0)
                {
                    result.Add(right.First());
                    right.Remove(right.First());
                }
            }
            return result;
        }  
    }
}

Nếu bạn không sử dụng lệnh Console.ReadKey(); thì chương trình sẽ chạy và kết thúc luôn (nhanh quá đến nỗi bạn không kịp nhìn kết quả). Lệnh này cho phép chúng ta nhìn kết quả một cách rõ ràng hơn.

Kết quả chương trình C#

Biên dịch và chạy chương trình C# trên sẽ cho kết quả: