排序算法-选择排序


选择排序

 流程:

  遍历整个数组找到最小的数,和索引为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     }

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

  

优质内容筛选与推荐>>
1、如何把Excel发布为moss中的列表(转)
2、spring boot 自定义异常
3、ASP.NET中 Bin,App_Browser,App_code,App_Data,App_Theme 等文件
4、2.9 box plot 箱线图
5、PHPSTORM+Xdebug配置


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号





    联系我们

    欢迎来到TinyMind。

    关于TinyMind的内容或商务合作、网站建议,举报不良信息等均可联系我们。

    TinyMind客服邮箱:support@tinymind.net.cn