Java——简单选择排序

简单选择排序基本思想:第一趟,从n个元素中找出关键字最小的元素与第一个元素交换;第二趟,在从第二个元素开始的n-1个元素中在选出关键字最小的元素与第二个元素交换;如此,第k趟,则从第k个元素开始的n-k+1个元素中选出关键字最小的元素与第k个元素交换,直到整个序列按关键字有序。
public static void test2(int[] r) {
        for(int i = 1;i < r.length;i++) {
            int j = i - 1;
            int min = r[j]; //默认第一项是最小的元素
            for(;j<r.length;j++) {
                if(min > r[j]) {//查找剩下的元素的最小值
                    int temp = min;
                    min = r[j];
                    r[j] = temp;
                }
            }
            r[i-1] = min; //把最小值赋值给第一项
        }
    }

空间效率:显然简单选择排序是需要一个辅助空间

时间效率:再简单选择排序中,所需移动元素的次数较少,在排序序列已经有序的情况下,简单选择排序不需要移动元素,在最坏的情况下,即待排序序列本身是逆序时,则移动元素的次数为3(n-1).然而无论简单选择排序过程中移动元素的次数多少,在任何情况下,简单选择排序都需要进行n(n-1)/2次比较操作,因此简单选择排序的时间复杂度O(n2)

其实,基于这个简单选择排序,我们可以深入思考一下,这个算法的改进空间。。后期我会跟进的。。。。

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 排序的基本概念 在计算机程序开发过程中,经常需要一组数据元素(或记录)按某个关键字进行排序,排序完成的序列可用于快...
    Jack921阅读 1,607评论 1赞 4
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    蚁前阅读 5,373评论 0赞 52
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到已排序好...
    依依玖玥阅读 1,397评论 0赞 2
  • 2017,9,22。 深夜,一个人,在漆黑的孤影里听尤克里里一下一下的拨奏,心弦颤动。脑海里突然浮现夏日灿烂的阳光...
    你只是一阵风吹过阅读 220评论 0赞 1
  • #yes I can。每天无理由地多说几次,真的会产生很神奇的正面效果。we are what we believ...
    macrossliu阅读 321评论 0赞 1

友情链接更多精彩内容