Insertion Sort on an array of strings in C#

问题:

If I have an array of strings, such as

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

How do I sort this array, using insertion sort?

Wikipedia has some examples: 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;
    }
}

and

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;
    }
}

but it doesn't seem to work on my array of strings, unless I'm doing something wrong.

Would I not run

InsertSort(names); // like so?

回答1:

Works fine for me:

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;
        }
    }
}

As expected it prints:

Another Name
Doe John
John Doe
Name Another

回答2:

Here's my implementation:

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]);
}

回答3:

I do some class to do this:

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];
        }
    }
}