选择排序(Selection Sort)

　　

      基本思想：第i趟排序从序列的后n-i+1(i=1,2...n-1)个元素中选择一个最小或最大的元素，与该n-i+1个元素的最前面那个元素进行位置交换，直到i=n-1（每一趟的选择排序就是从序列中

未排序的元素中选择一个最小或最大的元素，将该元素与未排序元素的第一个元素交换位置）

      举例分析：设有一个数据元素序列{3,6,4,2,11,10,5}，要求按从小到大顺序排列，排序步骤如下图所示：

      从上图可知：一个包含N个元素的序列，需要N-1趟的选择排序就可以将原序列排列有序，代码如下所示(C#实现):

1 public static int[] SortBySelectionSort(int[] m_SourceArray) 2         { 3             int tmp; 4             int length = m_SourceArray.Length; 5             for (int i = 0; i < length - 1; i++) 6             { 7                 int min = i; 8                 for (int j = i+1; j < length; j++) 9                 {10                     if (m_SourceArray[j] < m_SourceArray[min])11                         min = j;12                 }13                 if (i != min)14                 {15                     tmp = m_SourceArray[i];16                     m_SourceArray[i] = m_SourceArray[min];17                     m_SourceArray[min] = tmp;18                 }19             } 20             return m_SourceArray;21         }

　　  算法分析：选择排序属于不稳定的排序，时间复杂度为：O(N²)， 空间复杂度：O(1)