常用数据结构与算法（排序）

每一趟在n个记录中选取关键字最小的记录作为有序序列中的第I个记录
例：

namespace SelectionSorter
{
    public class SelectionSorter
    {
        private int min;

        public void Sort(int[] list)
        {
            for (int i = 0; i < list.Length-1; i++)
            {
                min = i;
                for (int j = i + 1; j < list.Length; j++)
                {
                    if (list[j] < list[min])           //与最小值比较才能不断用更小的值替换最小值
                    {
                        min = j;
                    }
                    int x;
                    x = list[i];
                    list[i] = list[min];
                    list[min] = x;
                }
            }
        }
    }
    public class MainClass
    {
        static void Main()
        {
            int[] iArray = new int[]{1,5,3,6,10,32,26,73,54 };
            SelectionSorter ss = new SelectionSorter();
            ss.Sort(iArray);

            for (int i = 0; i < iArray.Length; i++)
            {
                Console.Write("{0}  ", iArray[i]);
            }
        } } }

运行结果：

实现直接插入排序需要先找到一个有序数列。在一般排序时我们可以先把第一个元素看做一个序列，让第二个元素进行插入；再将前两个排好的元素看做一个有序数列，让第三个元素通过比较大小进行插入，得到有三个元素的有序数列；依次类推。

namespace InsertionSort
{
    public class InsertionSort
    {
        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;

            }
        }
    }

    public class MainClass
    {
        public static void Main()
        {
            int[] iArray = new int[] { 7, 3, 13, 5, 11, 32, 6, 48, 96, 23, };
            InsertionSort ins = new InsertionSort();
            ins.Sort(iArray);

            for (int i = 0; i < iArray.Length; i++)
            {
                Console.Write("{0}  ", iArray[i]);
            }
        }
    }
}

赋值过程如下：
3 7 13 5（待插入）
3 7 13 13 5（与13比较后需再向前比较，13让出list[2]的位置并将值向list[3]传递）
3 7 7 13 5（与7比较后需再向前比较，7让出list[1]的位置并将值向list[2]传递）
3 5 7 13 已完成插入，5与3比较后确定位置，占据list[1]位置 list[j] = t;

分组排序，组内使用直接插入排序。

namespace ShellSorter
{
    public class ShellSorter
    {
        public void Sort(int[] list)
        {
            int inc;
            for (inc = 1; inc <= list.Length / 9; inc = 3 * inc + 1) ;
            for (; inc > 0; inc /= 3)
            {
                for (int i = inc + 1; i <= list.Length; i += inc)		//直接插入排序
                {
                    int t = list[i - 1];
                    int j = i;
                    while ((j > inc) && (list[j - inc - 1]>t))
                    {
                        list[j - 1] = list[j - inc - 1];
                        j -= inc;
                    }
                    list[j - 1] = t;
                } }
        } }
    public class MainClass
    {
        public static void Main()
        {
            int[] iArray = new int[] { 7, 3, 13, 5, 11, 32, 6, 48, 96, 23, };
            ShellSorter ss = new ShellSorter();
            ss.Sort(iArray);

            for (int i = 0; i < iArray.Length; i++)
            {
                Console.Write("{0}  ", iArray[i]);
            }
        }
    }
}