每天一算法 -- （选择排序）

一、原理

　　每一趟从待排序的数中，选出最小的元素，并将 最小的元素 换到 趟数 对应的位置上。 

二、思路

　1.假设有一个数组为 [n个数]，第一趟先选出 最小的元素 min[k]，将min[k]位置 和 第一个元素的位置 互换，此时第一个元素就是 最小的元素 min[k]；由于第一趟已经选出最小的元素，也就是第二趟中就从第二个元素比较，选出除了第一个的最小元素min[j]，然后和 第二个元素互换，此时 第二小的 元素 也排好序了，后面的也就一样的。 

　2.举例说明：数组 [5,3,2,8,1,4]

　　第一趟：选出最小元素：1，将1和5 的位置互换，即

　　　　　　1,3,2,8,5,4 

　　------------------------------------------------------------------------

　　第二趟：除了第一个元素，选出最小元素：2，将2和3的位置互换，即：

　　　　　　1,2,3,8,5,4

　　------------------------------------------------------------------------

　　第三趟：除了第一二个元素，选出最小元素：3，将 3和3的位置互换，即：

　　　　　　1,2,3,8,5,4

　　------------------------------------------------------------------------

　　第四趟：除了第一二三个元素：选出最小元素：4，将4和8的位置互换，即：

　　　　　　1,2,3,4,5,8

　　------------------------------------------------------------------------

　　第五趟：除了第一二三四个元素：选出最小元素：5，将5和5的位置互换，即：

　　　　　　1,2,3,4,5,8

　　------------------------------------------------------------------------

　　此时，原来的数据 已经按照从小到大的顺序排列好了。

三、时间复杂度

　　选择排序改进了冒泡排序，将必要的交互次数从O(n²)减少到O(n)，但比较次数依然是O(n²)。选择排序仍然为大计数量的排序提出了一个非常大的改进，因为这些大量的记录会在内存中移动，这就是使交换的时间和比较的时间比起来，交换的时间更为重要。

　　选择排序和冒泡排序执行了相同的比较次数，N(N-1)/2。对于10个数据项，需要进行45次比较，但 交换的次数却小于 10次；对于100个数据项，需要进行4500次比较，但 交换的次数却 小于100次。N值很大时，比较的次数是主要的。所以 选择排序 和 冒泡排序的时间复杂度都是 O(n²)，但是，选择排序 无疑更快，因为它交换的次数少，

四、代码实现

             1
            /**
             2
             * 排序算法

             3
             * 
            @author
             Administrator

             4
            */
             5
            public
            class
             Sort {

             6
             7
            /**
             8
                 * 选择排序

             9
                 * 
            @param
             numbers

            10
            */
            11
            public
            static
            void selectSort(int[] numbers) {
12int min = 0;   // 定义最小变量13int temp = 0;   // 定义中间变量1415for(int i = 0; i < numbers.length - 1 ; i++){     // 第i趟16             min = i;
17for(int j = i + 1; j < numbers.length; j ++){    // 找出最小元素    18if(numbers[j] < numbers[min]){
19                     min = j;
20                }
21            }
22             temp = numbers[i];
23             numbers[i] = numbers[min];
24             numbers[min] = temp;
25        }
2627for(int i = 0;i<numbers.length;i++){
28             System.out.print(numbers[i] + "  ");
29        }
30    }
3132/**33     * 测试
34     * @param args
35*/36publicstaticvoid main(String[] args) {
37int[] arr = {5,3,2,8,1,4};
38        selectSort(arr);
39    }
40 }

原文：http://www.cnblogs.com/xbq8080/p/6824506.html