C#算法(二)选择排序

工作原理

第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

时间复杂度

可以很直观的看出选择排序的时间复杂度：就是两个循环消耗的时间；

比较时间：$T=(n-1)+(n-2)+(n-3)....+1;$ ===>> $T=[n*(n-1)]/2$；

交换时间：最好的情况全部元素已经有序，则换次数为0；最差的情况，全部元素逆序，就要交换n-1次；

所以最优的时间复杂度和最差的时间复杂度和平均时间复杂度 都为 ：$O(n^2)$

空间复杂度

空间复杂度，最优的情况下（已经有顺序）复杂度为：$O(0)$；最差的情况下（全部元素都要重新排序）复杂度为：$O(n)$;平均的时间复杂度：$O(1)$

代码示例

using System;

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 t = list[min];
                list[min] = list[i];
                list[i] = t;
            }
        }
    }
    public class MainClass
    {
        public static void Main()
        {
            int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
            SelectionSorter ss = new SelectionSorter();
            ss.Sort(iArrary);
            for (int m = 0; m < iArrary.Length; m++)
                Console.Write("{0}  ", iArrary[m]);
            Console.WriteLine();
        }
    }
}