Вставка Сортировка по массиву строк в C # - PullRequest
Новая
       6

Вставка Сортировка по массиву строк в C #

3 голосов
/ 12 октября 2010

Если у меня есть массив строк, например 

string[] names = {"John Doe", "Doe John", "Another Name", "Name Another"};

Как мне отсортировать этот массив, используя сортировку вставкой?

В Википедии есть несколько примеров: https://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Insertion_sort#C.23

static void InsertSort(IComparable[] array)
{
    int i, j;

    for (i = 1; i < array.Length; i++)
    {
        IComparable value = array[i];
        j = i - 1;
        while ((j >= 0) && (array[j].CompareTo(value) > 0))
        {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = value;
    }
}

и 

static void InsertSort<T>(IList<T> list) where T : IComparable<T>
{
    int i, j;

    for (i = 1; i < list.Count; i++)
    {
        T value = list[i];
        j = i - 1;
        while ((j >= 0) && (list[j].CompareTo(value) > 0))
        {
            list[j + 1] = list[j];
            j--;
        }
        list[j + 1] = value;
    }
}

но, похоже, он не работает с моим массивом строк, если я не делаю что-то не так.

Я бы не побежал 

InsertSort(names); // like so?

Ответы [ 3 ]

5 голосов
/ 12 октября 2010

Работает нормально для меня: 

class Program
{
    static void Main()
    {
        string[] names = { "John Doe", "Doe John", "Another Name", "Name Another" };
        InsertSort(names);
        foreach (var item in names)
        {
            Console.WriteLine(item);
        }
    }

    static void InsertSort(IComparable[] array)
    {
        int i, j;

        for (i = 1; i < array.Length; i++)
        {
            IComparable value = array[i];
            j = i - 1;
            while ((j >= 0) && (array[j].CompareTo(value) > 0))
            {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = value;
        }
    }
}

Как и ожидалось, он печатает: 

Another Name
Doe John
John Doe
Name Another
2 голосов
/ 20 февраля 2012

Вот моя реализация: 

public static void Swap<T>(ref T a, ref T b)
{
    T t = a;
    a = b;
    b = t;
}

public static void InsertionSort<T>(this T[] a) where T : IComparable<T>
{
    a.InsertionSort(Comparer<T>.Default.Compare);
}

public static void InsertionSort<T>(this T[] a, Comparison<T> c)
{
    int n = a.Length;
    for (int i = 1; i < n; ++i)
        for (int k = i; k > 0 && c(a[k], a[k - 1]) < 0; --k)
            Swap(ref a[k], ref a[k - 1]);
}
0 голосов
/ 14 мая 2012

Я делаю некоторый класс, чтобы сделать это: 

public static class InsertionSort<T> where T : System.IComparable<T>
{
    public static void Sort(ref T[] array)
    {
        T[] tmp = new T[array.Length];
        tmp[0] = array[0];

        for (int i = 1; i < array.Length; i++)
        {
            int place = FindProperPlace(tmp, array[i]);
            ExpandArray(ref tmp, place);
            tmp[place] = array[i];
        }

        array = tmp;
    }

    private static int FindProperPlace(T[] numbersArray, T number)
    {
        int j;

        for (j = 0; j < numbersArray.Length; j++)
        {
            if (number.CompareTo(numbersArray[j]) < 0)
            {
                break;
            }
        }

        return j;
    }

    private static void ExpandArray(ref T[] tmp, int place)
    {
        for (int i = tmp.Length - 1; i > place; i--)
        {
            tmp[i] = tmp[i - 1];
        }
    }
}
...