Chương trình Shell Sort trong C#

Shell Sort cho phép trao đổi các phần tử ở xa nhau trong mảng và sau đó giảm dần khoảng cách giữa chúng. Đây là một dạng tổng quát hóa của Insertion Sort. Thuật toán được đặt tên theo Donald Shell - người đầu tiên công bố nó.

Ví dụ

using System;

namespace ShellSortDemo
{
    public class Example
    {
        static void ShellSort(int[] arr, int n)
        {
            int i, j, gap, temp;
            gap = 3; // Khoảng cách ban đầu
            
            while (gap > 0)
            {
                for (i = 0; i < n; i++)
                {
                    j = i;
                    temp = arr[i];
                    
                    while ((j >= gap) && (arr[j - gap] > temp))
                    {
                        arr[j] = arr[j - gap];
                        j = j - gap;
                    }
                    arr[j] = temp;
                }
                
                // Giảm khoảng cách: 3 -> 1 -> 0
                if (gap / 2 != 0)
                    gap = gap / 2;
                else if (gap == 1)
                    gap = 0;
                else
                    gap = 1;
            }
        }
        
        static void Main(string[] args)
        {
            int[] arr = new int[] { 56, 12, 99, 32, 1, 95, 25, 5, 100, 84 };
            int n = arr.Length;
            int i;
            
            Console.WriteLine("Shell Sort");
            Console.Write("Mảng ban đầu: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
            
            ShellSort(arr, n);
            
            Console.Write("\nMảng đã sắp xếp: ");
            for (i = 0; i < n; i++)
                Console.Write(arr[i] + " ");
        }
    }
}

Kết quả

Shell Sort
Mảng ban đầu: 56 12 99 32 1 95 25 5 100 84
Mảng đã sắp xếp: 1 5 12 25 32 56 84 95 99 100

Giải thích thuật toán

Trong hàm Main(), mảng ban đầu được hiển thị, sau đó gọi ShellSort() để sắp xếp.

Trong ShellSort():

• Sử dụng khoảng cách (gap) ban đầu là 3
• Với mỗi gap, thực hiện insertion sort cho các phần tử cách nhau gap vị trí
• Giảm gap dần về 1 (insertion sort chuẩn) rồi kết thúc
• Dãy gap: 3 → 1 → 0 (kết thúc)

Độ phức tạp: Tốt nhất O(n log n), Trung bình phụ thuộc dãy gap, Tệ nhất O(n²).