.NET c#程序的排序算法插入排序

插入排序是一种简单、直观的排序算法，适用于元素数量较少或已经接近有序的数据。它的思想是将待排序的元素插入到已排序的序列中，经过逐步比较和移动，最终排序完成。在 .NET C# 编程中，插入排序是必不可少的一种排序算法。下面我们将介绍如何在 C# 中实现插入排序，并探讨如何对排序算法进行优化，以提高程序性能。

C# 程序中依据元素数量和序列有序程度的不同，可以选择多种不同的插入排序算法。

通用的插入排序算法可以描述为：

public static void InsertionSort<T>(T[] array) where T : IComparable<T> {
    for(int i=1;i<array.Length;i++){
        for(int j=i;j>0&&LessThan(array[j], array[j-1]);j--){
            Swap(array,j,j-1);
        }
    }
}

其中，LessThan 是一个比较方法，比较两个元素之间的关系，Swap 是一个简单的交换两个元素的方法。具体实现代码如下：

private static bool LessThan<T>(T a, T b) where T : IComparable<T>{
    return a.CompareTo(b) < 0;
}

private static void Swap<T>(T[] array, int a, int b){
    T temp = array[a];
    array[a] = array[b];
    array[b] = temp;
}

在以上代码中，将待排序数组分成已排序区间 (0, i-1) 和未排序区间 [i, array.Length - 1] 两个区间。在 for 循环中处理从 i = 1 开始的所有元素，通过逐次比较，找到“位置合适”的位置来进行插入排序。具体实现中，我们从 j = i 开始逆序比较元素，只有满足 array[j-1] > array[j] 的情况下，才需要交换元素。

当数据是有序的情况下，只需要进行少量比较即可得到最终结果。而当数据量非常大时，还可以通过以下优化方法进一步提高程序性能：

1. 在排序过程中，尽量减少比较次数，可以将比较后大的元素移动到一个新位置，而不是先交换元素位置再比较。这样可以减少插入排序时的比较和交换操作，从而提高效率。
2. 对于相同关键字的元素，如果插入到已排序区间中，相对位置也不会发生改变。因此，在进行插入排序时，可以添加特殊逻辑，实现按非递减规则排序，以进一步减少比较操作的数量。

上面的有点复杂了,来个简单源码:

        public void Sort(int[] list)
        {
            for (int i = 1; i < list.Length; i++)
            {
                int t = list[i];
                int j = i;
                while ((j > 0) && (list[j - 1] > t))
                {
                    list[j] = list[j - 1];
                    --j;
                }
                list[j] = t;
            }
        }

实现效果如下: