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 趟排序： index = 1, min = 2, 　　交换后 -->  1,2,3,6,5,4

第 3 趟排序： index = 2, min = 2, 　　交换后 -->  1,2,3,6,5,4

第 4 趟排序： index = 3, min = 5, 　　交换后 -->  1,2,3,4,5,6

第 5 趟排序： index = 4, min = 4, 　　交换后 -->  1,2,3,4,5,6

核心代码如下：

/**
   * 选择排序，从小到大排序
   */
  public static void selectsort(int[] arr) {
    int min = 0;  //记录最小值的索引
    //遍历 n-1 轮，最后一个数不用遍历比较
    for(int i = 0; i < arr.length - 1; i++) {
      min = i;    //初始最小值为每轮循环的第一个数
      //遍历初始最小值后的所有数
      for(int j = i + 1; j < arr.length; j++) {
        if(arr[min] > arr[j]) {    //判断是否存在比最小值小的数
          min = j;        //记录下标
        }
      }
      if(min != i) {      //判断最小值的索引是否等于初始最小值的索引
        int temp = arr[min];    //不是则进行最小值交换
        arr[min] = arr[i];
        arr[i] = temp;
      }
    }
  }

选择排序算法是一种不稳定的算法，它的时间复杂度为 O(n2)，空间复杂度为 O(1).

以上这篇java排序算法之_选择排序(实例讲解)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

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

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

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

  • Java 选择排序、插入排序、希尔算法实例详解

    Java 选择排序、插入排序、希尔算法实例详解

    1.基本思想: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换:然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止. 2.实例 3.算法实现 /** * 选择排序算法 * 在未排序序列中找到最小元素,存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾. * 以此类推,直到所有元素均排序完毕. * @param numbers */ public static void selectSort(int[] nu

  • Java排序算法总结之选择排序

    本文实例讲述了Java排序算法总结之选择排序.分享给大家供大家参考.具体分析如下: 选择排序的基本操作就是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完.算法不稳定,O(1)的额外的空间,比较的时间复杂度为O(n^2),交换的时间复杂度为O(n),并不是自适应的.在大多数情况下都不推荐使用.只有在希望减少交换次数的情况下可以用.   基本思想   n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果: ①初始状态:

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

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

  • java实现选择排序算法

    java实现选择排序算法

    java实现选择排序算法 public static void selectSort(int[] array) { for (int i = 0; i < array.length - 1; i++) { int min = i; for (int j = i + 1; j < array.length; j++) { if (array[j] < array[min]) { min = j; } } Sort.swap(array, i, min);//交换i和min } } 选择排序

  • JAVA简单选择排序算法原理及实现

    简单选择排序:(选出最小值,放在第一位,然后第一位向后推移,如此循环)第一位与后面每一个逐个比较,每次都使最小的置顶,第一位向后推进(即刚选定的第一位是最小值,不再参与比较,比较次数减1) 复杂度: 所需进行记录移动的操作次数较少 0--3(n-1) ,无论记录的初始排列如何,所需的关键字间的比较次数相同,均为n(n-1)/2,总的时间复杂度为O(n2):空间复杂度 O(1) 算法改进:每次对比,都是为了将最小的值放到第一位,所以可以一比到底,找出最小值,直接放到第一位,省去无意义的调换移动操作

  • Java对数组实现选择排序算法的实例详解

    Java对数组实现选择排序算法的实例详解

    一. 算法描述     选择排序:比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素交换,至此选择排序完成. 以下面5个无序的数据为例: 56 12 80 91 20(文中仅细化了第一趟的选择过程) 第1趟:12 56 80 91 20 第2趟:12 20 80 91 56 第3趟:12 20 56 91 80 第4趟

  • 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版本 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; } } }

  • PHP排序算法之简单选择排序(Simple Selection Sort)实例分析

    本文实例讲述了PHP排序算法之简单选择排序(Simple Selection Sort).分享给大家供大家参考,具体如下: 基本思想: 通过 n - i 次关键字间的比较,从 n - i + 1 个记录中选出关键字最小的记录,并和第 i (1 <= i <= n) 个记录交换,执行n-1趟 后就完成了记录序列的排序. 算法实现: <?php //简单选择排序 //交换函数 function swap(array &$arr,$a,$b){ $temp = $arr[$a]; $a

  • Java经典算法汇总之选择排序（SelectionSort）

    Java经典算法汇总之选择排序（SelectionSort）

    a)原理:每一趟从待排序的记录中选出最小的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕.也就是:每一趟在n-i+1(i=1,2,-n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录.基于此思想的算法主要有简单选择排序.树型选择排序和堆排序.(这里只介绍常用的简单选择排序) b)简单选择排序的基本思想:给定数组:int[]arr={里面n个数据}:第1趟排序,在待排序数据arr[1]~arr[n]中选出最小的数据,将它与arrr[1]交换:第2趟,在待排序数据arr[2]~ar

  • PHP排序算法之归并排序(Merging Sort)实例详解

    PHP排序算法之归并排序(Merging Sort)实例详解

    本文实例讲述了PHP排序算法之归并排序(Merging Sort).分享给大家供大家参考,具体如下: 基本思想: 归并排序:就是利用归并(合并)的思想实现的排序方法.它的原理是假设初始序列含有 n 个元素,则可以看成是 n 个有序的子序列,每个子序列的长度为 1,然后两两归并,得到 ⌈ n / 2⌉ (⌈ x ⌉ 表示不小于 x 的最小整数)个长度为 2 或 1 的有序序列:再两两归并,······,如此重复,直至得到一个长度为 n 的有序序列为止,这种排序方法就成为 2 路归并排序. 一.归并

  • PHP排序算法之基数排序(Radix Sort)实例详解

    本文实例讲述了PHP排序算法之基数排序(Radix Sort).分享给大家供大家参考,具体如下: 基数排序在<大话数据结构>中并未讲到,但是为了凑齐八大排序算法,我自己通过网络学习了这个排序算法,并给大家分享出来. 基本思想: 基数排序(radix sort)属于"分配式排序"(distribution sort),又称"桶子法"(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些"桶&quo

  • java数据结构与算法之简单选择排序详解

    本文实例讲述了java数据结构与算法之简单选择排序.分享给大家供大家参考,具体如下: 在前面的文章中已经讲述了交换类的排序算法,这节中开始说说选择类的排序算法了,首先来看一下选择排序的算法思想: 选择排序的基本算法思想: 每一趟在 n-i+1 (i=1,2,3,--,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录. 简单选择排序: 设所排序序列的记录个数为n.i取1,2,-,n-1,从所有n-i+1个记录(Ri,Ri+1,-,Rn)中找出排序码最小的记录,与第i个记录交换.执行n-

  • Java排序算法总结之希尔排序

    本文实例讲述了Java排序算法总结之希尔排序.分享给大家供大家参考.具体分析如下: 前言:希尔排序(Shell Sort)是插入排序的一种.是针对直接插入排序算法的改进.该方法又称缩小增量排序,因DL．Shell于1959年提出而得名.本文主要介绍希尔排序用Java是怎样实现的. 希尔排序(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序.希尔排序并不稳定,O(1)的额外空间,时间复杂度为O(N*(logN)^2).最坏的情况下的执行效率和在平均情况下的执行效率相

随机推荐