Java 十大排序算法之选择排序刨析

目录
  • 选择排序原理
  • 选择排序API设计
  • 选择排序代码实现
  • 选择排序的时间复杂度

选择排序原理

①假设第一个索引处的元素为最小值，和其他值进行比较，如果当前的索引处的元素大于其他某个索引处的值，则假定其他某个索引处的值为最小值，最后找到最小值所在的索引

②交换第一个索引处和最小值所在的索引处的值

选择排序API设计

类名 Selection
构造方法 Selection():创建Selection对象
成员方法
1.public static void sort(Comparable[] a):对数组内的元素进行排序

2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w

3.private static void exchange(Comparable[] a,int i,int j):交换a数组中，索引i和索引j处的值

选择排序代码实现

public class Selection {
    //对数组a中的元素进行排序
    public static void sort(Comparable[] a){
        for(int i=0;i<a.length-2;i++){
            int minIndex=i;
            for(int j=i+1;j<a.length;j++){
                if(greater(a[minIndex],a[j])){
                    minIndex=j;
                }
            }
            exchange(a,i,minIndex);
        }
    }
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;
    }
    private static void exchange(Comparable[] a,int i,int j ){
        Comparable t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
class Test{
    public static void main(String[] args) {
        Integer[] a={4,6,8,7,9,2,10,1};
        Selection.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

选择排序的时间复杂度

选择排序使用了双层for循环，外层循环完成了数据交换，内层循环完成了数据比较，所以分别统计：数据比较次数：(N-1)+(N-2)+(N-3)+...+2+1=

((N-1)+1)*(N-1)/2=N^2/2-N/2;

数据交换次数：N-1；

时间复杂度： N^2/2-N/2+(N-1)=N^2/2+N/2-1;

根据大O推导法则，保留最高阶项，去除常数因子，时间复杂度为O（N^2）

到此这篇关于Java 十大排序算法之选择排序刨析的文章就介绍到这了,更多相关Java 选择排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java实现选择排序算法的实例教程

    Java实现选择排序算法的实例教程

    选择排序概念 选择排序也是一种交换排序算法,和冒泡排序有一定的相似度,因此个人认为选择排序可以视为冒泡排序的一种改进算法.它的思路是这样的: 设现在要给数组arr[]排序,它有n个元素. 1对第一个元素(Java中,下标为0)和第二个元素进行比较,如果前者大于后者,那么它一定不是最小的,但是我们并不像冒泡排序一样急着交换.我们可以设置一个临时变量a,存储这个目前最小的元素的下标.然后我们把这个目前最小的元素继续和第三个元素做比较,如果它仍不是最小的,那么,我们再修改a的值.如此直到和最后一个元素

  • Java实现的各种排序算法(插入排序、选择排序算法、冒泡排序算法)

    一.插入排序算法实现java版本 public static int[] insert_sort(int[] a) { for (int i = 0; i < a.length; i++) { for(int j=i+1;j>0&&j<a.length;j--) { if(a[j]<a[j-1]) { int tmp = a[j]; //这样定义初始化逻辑上是可以的,j变量,每次tmp的值变化的 a[j] = a[j-1]; a[j-1] = tmp; } } }

  • java数据结构排序算法之树形选择排序详解

    本文实例讲述了java数据结构排序算法之树形选择排序.分享给大家供大家参考,具体如下: 这里我们就来说说选择类排序之一的排序:树形选择排序 在简单选择排序中,每次的比较都没有用到上次比较的结果,所以比较操作的时间复杂度是O(N^2),想要降低比较的次数,则需要把比较过程中的大小关系保存下来.树形选择排序是对简单选择排序的改进. 树形选择排序:又称锦标赛排序(Tournament Sort),是一种按照锦标赛的思想进行选择排序的方法.首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进

  • JAVA十大排序算法之选择排序详解

    JAVA十大排序算法之选择排序详解

    目录 选择排序 代码实现 动图演示 代码实现 时间复杂度 算法稳定性 总结 选择排序 1.找到数组中最大(或最小)的元素 2.将它和数组的第一个元素交换位置(如果第一个元素就是最大(小)元素那么它就和自己交换) 3.在剩下的元素中找到最大(小)的元素,将它与数组的第二个元素交换位置.如此往复,直到将整个数组排序. 代码实现 对下面数组实现排序:{87, 23, 7, 43, 78, 62, 98, 81, 18, 53, 73, 9} 动图演示 代码实现 public class Selecti

  • java排序算法之_选择排序(实例讲解)

    选择排序是一种非常简单的排序算法,从字面意思我们就可以知道,选择就是从未排序好的序列中选择出最小(最大)的元素,然后与第 i 趟排序的第 i-1(数组中下标从 0 开始) 个位置的元素进行交换,第 i 个元素之前的序列就是已经排序好的序列.整个排序过程只需要遍历 n-1 趟便可排好,最后一个元素自动为最大(最小)值. 举个小例子: arr[] = {3,1,2,6,5,4} 第 1 趟排序: index = 0, min = 1, 交换后 -->  1,3,2,6,5,4 第 2 趟排序: in

  • Java排序算法之选择排序

    Java排序算法之选择排序

    一.选择排序 选择排序就是在每一次遍历过程中将数组中值最小的排到当前的第一位. 总共需要(数组长度-1)次遍历,在每次遍历中假定第一位索引的值为最小值,然后与下一个值对比,如果最小索引所在值大于其他值就将小的那一个索引当作最小值索引,接着继续对比最小索引所在值与下一个索引的值,重复此操作,最终就会在此次遍历中得到最小值及其索引,将最小值与第一位的值进行交换,这样就将最小值放到了数组开头,完成本次遍历. 选择排序的时间复杂度为O(N^2) 二.代码实现 package com.example.al

  • java 排序算法之选择排序

    java 排序算法之选择排序

    目录 基本介绍 基本思想 思路分析 代码实现 演变过程 优化 算法函数封装 大量数据耗时测试 基本介绍 选择排序(select sorting)也属于内部排序法,是从欲排序的数据中,按指定的规则选出来某个元素,再依规定交换位置后达到排序的目的. 它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 基本思想 选择排序(select sorting)也是一种简单直

  • java排序算法之选择排序详解

    java排序算法之选择排序详解

    本文实例为大家分享了java排序算法之选择排序的具体代码,供大家参考,具体内容如下 选择排序 选择排序的思路是这样的:首先,找到数组中最小的元素,拎出来,将它和数组的第一个元素交换位置,第二步,在剩下的元素中继续寻找最小的元素,拎出来,和数组的第二个元素交换位置,如此循环,直到整个数组排序完成. 至于选大还是选小,这个都无所谓,你也可以每次选择最大的拎出来排,也可以每次选择最小的拎出来的排,只要你的排序的手段是这种方式,都叫选择排序. (有序区,无序区).在无序区里找一个最小的元素跟在有序区的后

  • Java 十大排序算法之选择排序刨析

    Java 十大排序算法之选择排序刨析

    目录 选择排序原理 选择排序API设计 选择排序代码实现 选择排序的时间复杂度 选择排序原理 ①假设第一个索引处的元素为最小值,和其他值进行比较,如果当前的索引处的元素大于其他某个索引处的值,则假定其他某个索引处的值为最小值,最后找到最小值所在的索引 ②交换第一个索引处和最小值所在的索引处的值 选择排序API设计 类名 Selection 构造方法 Selection():创建Selection对象 成员方法 1.public static void sort(Comparable[] a):对

  • Python排序算法之选择排序定义与用法示例

    Python排序算法之选择排序定义与用法示例

    本文实例讲述了Python排序算法之选择排序定义与用法.分享给大家供大家参考,具体如下: 选择排序 选择排序比较好理解,好像是在一堆大小不一的球中进行选择(以从小到大,先选最小球为例): 1. 选择一个基准球 2. 将基准球和余下的球进行一一比较,如果比基准球小,则进行交换 3. 第一轮过后获得最小的球 4. 在挑一个基准球,执行相同的动作得到次小的球 5. 继续执行4,直到排序好 时间复杂度:O(n^2).  需要进行的比较次数为第一轮 n-1,n-2....1, 总的比较次数为 n*(n-1

  • C语言排序算法之选择排序(直接选择排序,堆排序)

    C语言排序算法之选择排序(直接选择排序,堆排序)

    目录 前言 一.直接选择排序 1.1 算法思想 1.2 代码实现 1.3 直接选择排序的特征总结 二.堆排序 2.1 什么是堆? 2.2 判断是否是堆 2.3 向下调整算法 2.4 自底向上的建堆方式 2.5 代码实现 2.6 堆排序的特性总结 2.7 堆排序的特性总结 前言 本期为大家带来的是常见排序算法中的选择排序,主要有直接选择排序以及——堆排序(有点难理解),包您一看就会,快来试试吧~ 一.直接选择排序 1.1 算法思想 每一次从待排序的数据元素中选出最小(或最大的)的一个元素,存放在序

  • JavaScript实现经典排序算法之选择排序

    表现最稳定的排序算法之一,因为无论什么数据进去都是O(n²)的时间复杂度.....所以用到它的时候,数据规模越小越好.唯一的好处可能就是不占用额外的内存空间. 1)算法原理 先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 2)算法描述和实现 n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果.具体算法描述如下: <1>初始状态:无序区为R[1..n],有序区为

  • Java十大经典排序算法的实现图解

    Java十大经典排序算法的实现图解

    目录 前言 一.排序算法 1.排序算法概述(百度百科) 2.<数据结构与算法>中的排序算法 3.算法分析 二.十大经典排序算法(Java开发版) 1.冒泡排序 2.快速排序 3.基数排序 4.插入排序 5.选择排序 6.希尔排序 7.归并排序 8.计数排序 9.堆排序 10.桶排序 前言 本文章主要是讲解我个人在学习Java开发环境的排序算法时做的一些准备,以及个人的心得体会,汇集成本篇文章,作为自己对排序算法理解的总结与笔记. 内容主要是关于十大经典排序算法的简介.原理.动静态图解和源码实现

  • Java 十大排序算法之冒泡排序刨析

    Java 十大排序算法之冒泡排序刨析

    目录 冒泡排序原理 冒泡排序API设计 冒泡排序的代码实现 冒泡排序的时间复杂度分析 冒泡排序原理 ①比较相邻的元素,如果前一个元素比后一个元素大,则交换这两个元素的位置 ②对每一对相邻的元素循环上面的步骤,最终最后面的元素就是最大值 冒泡排序API设计 类名 Bubble 构造方法 Bubble:创建Bubble对象 成员方法 1.public static void sort(Comparable[] a):对数组内元素进行排序 2.private static void greater(C

随机推荐