排序算法之选择排序

1.基本思路

选择排序的思想是在一次排序后把最小的元素放到最前面，从i=0开始，将当前元素的下标存在tempmin变量中，每次默认当前元素最小，然后和相邻元素比较，如果下标为i+1的元素小于当前元素，则tempmin=i+1,一次循环后找出当前最小元素，如果tempmin!=i,则交换tempmin和i的值。选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。

2.时间复杂度

最好的情况全部元素已经有序，则交换次数为0；最差的情况，全部元素逆序，就要交换 n-1 次；所以最优的时间复杂度和最差的时间复杂度和平均时间复杂度都为：O(n^2)

3.代码的实现

 1 namespace SelectSort
 2 {
 3     class Program
 4     {
 5         static void Main(string[] args)
 6         {
 7             Encoding.RegisterProvider(CodePagesEncodingProvider.Instance);
 8             int[] arry = { 9, 7, 12, 6, 8, 1 };
 9             Console.WriteLine("-------------排序前--------------");
10             for (int i = 0; i < arry.Length; i++)
11             {
12                 Console.Write(arry[i] + " ");
13             }
14             SelectSort(arry);
15             Console.WriteLine("
-------------排序后--------------");
16             for (int i = 0; i < arry.Length; i++)
17             {
18                 Console.Write(arry[i] + " ");
19             }
20             Console.ReadKey();
21         }
22         /// <summary>
23         /// 选择排序
24         /// </summary>
25         /// <param name="arry"></param>
26         public static  void SelectSort(int[] arry)
27         {
28             if (arry.Length == 0 || arry == null)
29                 return;
30             var tempmin = 0;
31             for (int i = 0; i < arry.Length - 1; i++)
32             {
33                 tempmin = i;
34                 for (int j = i + 1; j < arry.Length; j++)
35                 {
36                     if (arry[j] < arry[tempmin])
37                     {
38                         tempmin = j;
39                     }
40                 }
41                 if (tempmin != i)
42                 {
43                     var target = arry[tempmin];
44                     arry[tempmin] = arry[i];
45                     arry[i] = target;
46                 }
47             }
48 
49         }
50     }
51 }

运行结果：