排序算法-选择排序

选择排序

　流程：

　　遍历整个数组找到最小的数，和索引为0的元素交换位置

　　再次遍历数组，找到第二小的元素和索引为1的元素交换位置

　　遍历 length-1 次...

　　(只有第一次是遍历整个数组，选择排序完成了的元素就不用在遍历了)

　　时间复杂度：O(n^2)

　　代码实现(java)：

    public static void main(String[] args) {
        int[] arrs = {5, 20, 100, 50, 1, 40, 2};
        chooseSort(arrs);
    }
    
    private static void chooseSort(int[] arrs) {
        //遍历次数 length-1 次即可(当然遍历length也不会出现报错，最大程度追求效率)
        for(int i = 0;i < arrs.length - 1;i++){
            int index = i;
            //遍历找最小的元素
            for(int j = i;j < arrs.length;j++){
                if(arrs[j] < arrs[index]){
                    index = j;
                }
            }
            //如果此次遍历得到的最小元素不是当前最小索引位置的元素 则交换位置
            if(arrs[index] != arrs[i]){
                repalceIndex(arrs, index, i);
            }
        }
        for (int i : arrs) {
            System.out.println(i);
        }
    }

    //交换元素位置的方法
    private static void repalceIndex(int[] arrs, int small, int i) {
        int temp = arrs[small];
        arrs[small] = arrs[i];
        arrs[i] = temp;
    }

在选择排序的基础上衍生出或者说是一种优化效率的选择排序：双向选择排序

双向选择排序

　流程:

　　遍历整个数组找到最小的数min，最大的数max，最小的数和索引为0的元素交换位置，最大的数和索引为length - 1的元素交换位置

　　再次遍历数组，最小的数min，最大的数max，最小的数和索引为1的元素交换位置，最大的数和索引为length - 2的元素交换位置

　　遍历 length/2 次...

　　好处是减少了遍历了次数，遍历次数大约减少一半。

　　时间复杂度：O(n^2/2)

　　代码实现(java):

 1     public static void main(String[] args) {
 2         int[] arrs = {5, 20, 100, 50, 1, 40, 2, 0};
 3         chooseSort2(arrs);
 4     }
 5 
 6     /**
 7      * 双向选择排序
 8      * @param arrs
 9      */
10     private static void chooseSort2(int[] arrs) {
11         //遍历次数
12         for(int i = 0;i < arrs.length / 2 ;i++){
13             //本次遍历的最小和最大索引
14             int small = i;
15             int big = arrs.length - 1 - i;
16             for(int j = i;j < arrs.length - i;j++){
17                 if(arrs[j] < arrs[small]){
18                     small = j;
19                 }
20                 if(arrs[j] > arrs[big]){
21                     big = j;
22                 }
23             }
24             //如果此次遍历得到的最小元素不是当前最小索引位置的元素 则交换位置
25             if(arrs[small] != arrs[i]){
26                 repalceIndex(arrs, small, i);
27             }
28             //如果此次遍历得到的最大元素不是当前最大索引位置的元素 则交换位置
29             if(arrs[big] != arrs[arrs.length - 1 - i]){
30                 repalceIndex(arrs, big, arrs.length - 1 - i);
31             }
32         }
33         for (int i : arrs) {
34             System.out.println(i);
35         }
36     }
37     
38     //交换元素位置的方法
39     private static void repalceIndex(int[] arrs, int small, int i) {
40         int temp = arrs[small];
41         arrs[small] = arrs[i];
42         arrs[i] = temp;
43     }

以上为自己编译通过的代码以及结合部分书籍得出来的结论，如有不对还望指出！