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

2024-03-05 11:52:43

选择排序概念

选择排序也是一种交换排序算法，和冒泡排序有一定的相似度，因此个人认为选择排序可以视为冒泡排序的一种改进算法。它的思路是这样的：
设现在要给数组arr[]排序，它有n个元素。
1对第一个元素（Java中，下标为0）和第二个元素进行比较，如果前者大于后者，那么它一定不是最小的，但是我们并不像冒泡排序一样急着交换。我们可以设置一个临时变量a，存储这个目前最小的元素的下标。然后我们把这个目前最小的元素继续和第三个元素做比较，如果它仍不是最小的，那么，我们再修改a的值。如此直到和最后一个元素比较完，可以肯定a存储的一定是最小的元素的下标。
2.如果a的值不为0（初始值，即第一个元素的下标），交换下标为a和0的两个元素。
3.重复上述过程，这次从下标为1的元素开始比较，因为下标为0的位置已经放好了最小的元素了。
4.如此直到只剩下最后一个元素，可以肯定这个元素就是最大的了。
5.排序完成。
很显然，这个算法也需要n-1轮排序。
需要注意的是，以上阐述的只是每次找最小值的办法。实际上也可以每次找最大值，不过那就需要每次放到数组尾巴上了。

Java实现代码：
SelectArray.java

package ch02;

public class SelectArray {
  // 数组
  private long[] arr;

  // 数组中有效数据的大小
  private int elems;

  // 默认构造函数
  public SelectArray() {
    arr = new long[50];
  }

  public SelectArray(int max) {
    arr = new long[max];
  }

  // 插入数据
  public void insert(long value) {
    arr[elems] = value;
    elems++;
  }

  // 显示数据
  public void display() {
    for (int i = 0; i < elems; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }

  // 选择排序
  public void selectSort(){
    int min = 0;
    long tmp = 0L;
    for(int i = 0; i < elems -1; i++){
      min = i;
      for(int j = i + 1; j < elems; j++) {
        if(arr[j] < arr[min]) {
          min = j;
        }
      }
      tmp = arr[i];
      arr[i] = arr[min];
      arr[min] = tmp;
    }
  }
}

测试代码：

package ch02;

public class TestSelectArray {

  public static void main(String[] args) {
    SelectArray sArr = new SelectArray();
    sArr.insert(89);
    sArr.insert(54);
    sArr.insert(667);
    sArr.insert(7);
    sArr.insert(12);
    sArr.insert(43);
    sArr.insert(12);

    sArr.display();
    sArr.selectSort();
    sArr.display();

  }

}

结果：

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

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

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

选择排序是一种非常简单的排序算法,从字面意思我们就可以知道,选择就是从未排序好的序列中选择出最小(最大)的元素,然后与第 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数据结构排序算法之树形选择排序.分享给大家供大家参考,具体如下: 这里我们就来说说选择类排序之一的排序:树形选择排序在简单选择排序中,每次的比较都没有用到上次比较的结果,所以比较操作的时间复杂度是O(N^2),想要降低比较的次数,则需要把比较过程中的大小关系保存下来.树形选择排序是对简单选择排序的改进. 树形选择排序:又称锦标赛排序(Tournament Sort),是一种按照锦标赛的思想进行选择排序的方法.首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进
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 选择排序、插入排序、希尔算法实例详解

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

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

选择排序是排序算法的一种,这里以从小到大排序为例进行讲解. 基本思想及举例说明选择排序(从小到大)的基本思想是,首先,选出最小的数,放在第一个位置:然后,选出第二小的数,放在第二个位置:以此类推,直到所有的数从小到大排序. 在实现上,我们通常是先确定第i小的数所在的位置,然后,将其与第i个数进行交换. 下面,以对 3 2 4 1 进行选择排序说明排序过程,使用min_index 记录当前最小的数所在的位置. 第1轮排序过程 (寻找第1小的数所在的位置) 3 2 4 1(最初, m
Swift实现Selection Sort选择排序算法的实例讲解

选择排序Selection Sort是一种和插入排序Insertion Sort类似的排序方法,它同样只适用于对规模不大的集合进行排序.它的核心思想是,在序列内部,把序列逻辑上分成已排序和未排序两部分,不断找到未排序部分中最符合排序规则的元素,添加进已排序部分,直到序列中所有元素都已经添加到了已排序部分,此时,整个序列就排序完成了. 冒泡排序是两两比较不断交换来实现排序,所以比较繁琐. 而选择排序则是先选择要交换的那个数,才去交换.这样就可以省去很多不必要的步骤. Swift版实现示例: f
Java数组常用排序算法实例小结

本文实例讲述了Java数组常用排序算法.分享给大家供大家参考,具体如下: 1.冒泡排序法 SortArray_01.java public class SortArray_01 { public static void main(String args[]) { int[] array = { 14, 5, 86, 4, 12, 3, 21, 13, 11, 2, 55, 66, 22 }; // 创建一个初始化的一维数组array System.out.println("未排序的数组:&quo
Python实现的选择排序算法原理与用法实例分析

本文实例讲述了Python实现的选择排序算法.分享给大家供大家参考,具体如下: 选择排序(Selection sort)是一种简单直观的排序算法.它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完. 比如在一个长度为N的无序数组中,在第一趟遍历N个数据,找出其中最小的数值与第一个元素交换,第二趟遍历剩下的N-1个数据,找出其中最小的数值与第二个元素交换......第N-1趟遍历剩下的2个数据,找出其中最小的数值与第N-1个元素
python选择排序算法实例总结

本文实例总结了python选择排序算法.分享给大家供大家参考.具体如下: 代码1: def ssort(V): #V is the list to be sorted j = 0 #j is the "current" ordered position, starting with the first one in the list while j != len(V): #this is the replacing that ends when it reaches the end o
JavaScript实现的选择排序算法实例分析

本文实例讲述了JavaScript实现的选择排序算法.分享给大家供大家参考,具体如下: 简单选择排序是人们最熟悉的比较方式,其算法思想为:从数组的开头开始,将第一个元素和其他元素进行比较.检查完所有元素后,最小的元素会被放到数组的第一个位置,然后算法会从第二个位置继续.这个过程会一直进行,当进行到数组的倒数第二个位置时,所有的数据便完成了排序. 代码如下: <!DOCTYPE html> <html> <head> <meta charset="utf-

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

相关推荐

随机推荐