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

本文实例讲述了Java排序算法总结之选择排序。分享给大家供大家参考。具体分析如下：

选择排序的基本操作就是每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。算法不稳定，O(1)的额外的空间，比较的时间复杂度为O(n^2)，交换的时间复杂度为O(n)，并不是自适应的。在大多数情况下都不推荐使用。只有在希望减少交换次数的情况下可以用。
 
基本思想
 
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序

第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
 
代码实现

public class Test {
  public static int[] a = {10,32,1,9,5,7,12,0,4,3};
  // 预设数据数组
  public static void main(String args[]) {
    int i; // 循环计数变量
    int Index = a.length;// 数据索引变量
    System.out.print("排序前: ");
    for (i = 0; i < Index - 1; i++)
      System.out.printf("%3s", a);
    System.out.println("");
    SelectSort(Index - 1); // 选择排序
    // 排序后结果
    System.out.print("排序后: ");
    for (i = 0; i < Index - 1; i++)
      System.out.printf("%3s", a);
    System.out.println("");
  }
  public static void SelectSort(int Index) {
    int i, j, k; // 循环计数变量
    int MinValue; // 最小值变量
    int IndexMin; // 最小值索引变量
    int Temp; // 暂存变量
    for (i = 0; i < Index - 1; i++) {
      MinValue = 32767;// 目前最小数值
      IndexMin = 0; // 储存最小数值的索引值
      for (j = i; j < Index; j++) {
        if (a[j] < MinValue) // 找到最小值
        {
          MinValue = a[j]; // 储存最小值
          IndexMin = j;
        }
        Temp = a; // 交换两数值
        a = a;
        a = Temp;
      }
      System.out.print("排序中: ");
      for (k = 0; k < Index; k++)
        System.out.printf("%3s", a[k]);
      System.out.println("");
    }
  }
}

选择排序法与冒泡排序法一样，最外层循环仍然要执行n-1次，其效率仍然较差。

希望本文所述对大家的java程序设计有所帮助。

赞 (0)

相关推荐

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

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

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

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

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

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

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

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

  • 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实现选择排序算法

    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数据结构排序算法之树形选择排序详解

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

  • 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(1)的额外的空间,比较的时间复杂度为O(n^2),交换的时间复杂度为O(n),并不是自适应的.在大多数情况下都不推荐使用.只有在希望减少交换次数的情况下可以用.   基本思想   n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果: ①初始状态:

  • 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

  • Lua中写排序算法实例（选择排序算法）

    早在12年的时候,学过一个月的lua,当时看的是<programming in lua>,一直没用过,然后就忘了.现在我下定决心重新学习它. 时间久了,对编程的热情也随之消失殆尽,很难找回当初编程的乐趣了.近来一放假就玩英雄联盟,太浪费时间,玩个十来局一天就过去了,浑浑噩噩的,这实在不是我想过的.所以,今天我把它卸载了.如果你也是英雄联盟玩家,希望你不要沉迷其中. 从事游戏开发还不到一年,已经有点厌倦了,同事们一致认为游戏公司普遍很浮躁,有些小公司没有一点技术氛围.我知道的有些程序员,技术远远

  • 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).最坏的情况下的执行效率和在平均情况下的执行效率相

  • Python 选择排序中的树形选择排序

    Python 选择排序中的树形选择排序

    目录 1.引言 2.问题描述 3.解决方案 4.结语 1.引言 选择排序里面主要讲了三个排序,分别是简单选择排序.树形选择排序.堆排序.今天这篇文章主要讲树形选择排序,树形选择排序也被称为锦标赛排序,树形选择排序运用了锦标赛的思想进行排序,树形选择排序是指首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进行两两比较,如此重复,直至选出最小的记录为止. 2.问题描述 给定一个序列,我们将如何用树形选择排序来将它排序呢,下面将结合图形和文字一起讲述. 示例1:对数据表A=(73,45,

随机推荐