Java数据结构及算法实例：选择排序 Selection Sort

/**
 * 选择排序的思想：
 * 每次从待排序列中找到最小的元素，
 * 然后将其放到待排的序列的最左边，直到所有元素有序
 *
 * 选择排序改进了冒泡排序，将交换次数从O(N^2)减少到O(N)
 * 不过比较次数还是O(N)
 */
package al;
public class SelectSort { 

  public static void main(String[] args) { 

    SelectSort selectSort = new SelectSort();
    int[] elements = { 14, 77, 21, 9, 10, 50, 43, 14 };
    // sort the array
    selectSort.sort(elements);
    // print the sorted array
    for (int i = 0; i < elements.length; i++) {
      System.out.print(elements[i]);
      System.out.print(" ");
    }
  } 

  /**
   * @author
   * @param array 待排数组
   */
  public void sort(int[] array) {
    // min to save the minimum element for each round
    int min, tmp; 

    for(int i=0; i<array.length; i++) {
      min = i;
      // search for the minimum element
      for(int j=i; j<array.length; j++) {
        if(array[j] < array[min]) {
          min = j;
        }
      }
      // swap minimum element
      tmp = array[i];
      array[i] = array[min];
      array[min] = tmp;
    }
  }
}
赞 (0)

相关推荐

  • Java创建树形结构算法实例代码

    在JavaWeb的相关开发中经常会涉及到多级菜单的展示,为了方便菜单的管理需要使用数据库进行支持,本例采用相关算法讲数据库中的条形记录进行相关组装和排序讲菜单组装成树形结构. 首先是需要的JavaBean import java.io.Serializable; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.Date; import j

  • Java数据结构及算法实例：插入排序 Insertion Sort

    /** * 选择排序的思想: * 每次循环前,数组左边都是部分有序的序列, * 然后选择右边待排元素,将其值保存下来 * 依次和左边已经排好的元素比较 * 如果小于左边的元素,就将左边的元素右移一位 * 直到和最左边的比较完成,或者待排元素不比左边元素小 */ package al; public class InsertionSort { public static void main(String[] args) { InsertionSort insertSort = new Insert

  • Java数据结构及算法实例：快速计算二进制数中1的个数(Fast Bit Counting)

    /** * 快速计算二进制数中1的个数(Fast Bit Counting) * 该算法的思想如下: * 每次将该数与该数减一后的数值相与,从而将最右边的一位1消掉 * 直到该数为0 * 中间循环的次数即为其中1的个数 * 例如给定"10100",减一后为"10011",相与为"10000",这样就消掉最右边的1 * Sparse Ones and Dense Ones were first described by Peter Wegner i

  • Java数据结构及算法实例：冒泡排序 Bubble Sort

    /** * 冒泡排序估计是每本算法书籍都会提到的排序方法. * 它的基本思路是对长度为N的序列,用N趟来将其排成有序序列. * 第1趟将最大的元素排在序列尾部,第2趟将第2大的元素排在倒数第二的位置, * 即每次把未排好的最大元素冒泡到序列最后端. * 该排序方法实际上分为两重循环,外层循环:待排元素从数组的第1个元素开始. * 内层循环:待排元素从数组的第1个元素开始,直到数组尾端未排过的元素. * 在内循环中,如果遇到前面元素比其后的元素大就交换这两个元素的位置. * 由此可见冒泡排序的复杂

  • Java数据结构及算法实例：考拉兹猜想 Collatz Conjecture

    /** * 考拉兹猜想:Collatz Conjecture * 又称为3n+1猜想.冰雹猜想.角谷猜想.哈塞猜想.乌拉姆猜想或叙拉古猜想, * 是指对于每一个正整数,如果它是奇数,则对它乘3再加1, * 如果它是偶数,则对它除以2,如此循环,最终都能够得到1. */ package al; public class CollatzConjecture { private int i = 1; public static void main(String[] args) { long l = 9

  • java实现Fibonacci算法实例

    本文实例讲述了java实现Fibonacci算法的方法.分享给大家供大家参考.具体如下: package com.yenange.test2; import java.util.Scanner; public class Fibonacci { private static Scanner input = new Scanner(System.in); public static void main(String[] args) { System.out.println("-----------

  • Java算法之堆排序代码示例

    Java算法之堆排序代码示例

    堆是一种特殊的完全二叉树,其特点是所有父节点都比子节点要小,或者所有父节点都比字节点要大.前一种称为最小堆,后一种称为最大堆. 比如下面这两个: 那么这个特性有什么作用?既然题目是堆排序,那么肯定能用来排序.想要用堆排序首先要创建一个堆,如果对4 3 6 2 7 1 5这七个数字做从小到大排序,需要用这七个数创建一个最大堆,来看代码: public class HeapSort { private int[] numbers; private int length; public HeapSor

  • Java实现二分查找算法实例分析

    本文实例讲述了Java实现二分查找算法.分享给大家供大家参考.具体如下: 1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合

  • Java数据结构与算法之选择排序(动力节点java学院整理)

    Java数据结构与算法之选择排序(动力节点java学院整理)

    每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完. 代码 public class ChoseSort { //constructor without parameters public ChoseSort(){}; //constructor with parameters public int[] ChoseSort(int[] intArr){ for(int i=0;i<intArr.length-1;i++){ int

  • java数据结构与算法之希尔排序详解

    本文实例讲述了java数据结构与算法之希尔排序.分享给大家供大家参考,具体如下: 这里要介绍的是希尔排序(缩小增量排序法). 希尔排序:通过比较相距一定间隔的元素来工作:各趟比较所用的距离(增量)随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止.是插入排序的一种,是针对直接插入排序算法的改进. 算法思想:先将要排序的序列按某个增量d分成若干个子序列,对每个子序列中全部元素分别进行直接插入排序,然后再用一个较小的增量对它进行分组,在每组中再进行排序.当增量减到1时,整个要排序的数被分成一

  • java数据结构与算法之奇偶排序算法完整示例

    本文实例讲述了java数据结构与算法之奇偶排序算法.分享给大家供大家参考,具体如下: 算法思想: 基本思路是奇数列排一趟序,偶数列排一趟序,再奇数排,再偶数排,直到全部有序 举例吧, 待排数组[6 2 4 1 5 9] 第一次比较奇数列,奇数列与它的邻居偶数列比较,如6和2比,4和1比,5和9比 [6 2 4 1 5 9] 交换后变成 [2 6 1 4 5 9] 第二次比较偶数列,即6和1比,5和5比 [2 6 1 4 5 9] 交换后变成 [2 1 6 4 5 9] 第三趟又是奇数列,选择的是

  • java数据结构与算法之桶排序实现方法详解

    java数据结构与算法之桶排序实现方法详解

    本文实例讲述了java数据结构与算法之桶排序实现方法.分享给大家供大家参考,具体如下: 基本思想: 假定输入是由一个随机过程产生的[0, M)区间上均匀分布的实数.将区间[0, M)划分为n个大小相等的子区间(桶),将n个输入元素分配到这些桶中,对桶中元素进行排序,然后依次连接桶输入0 ≤A[1..n] <M辅助数组B[0..n-1]是一指针数组,指向桶(链表).将n个记录分布到各个桶中去.如果有多于一个记录分到同一个桶中,需要进行桶内排序.最后依次把各个桶中的记录列出来记得到有序序列. [桶-

  • Java数据结构及算法实例：选择排序 Selection Sort

    /** * 选择排序的思想: * 每次从待排序列中找到最小的元素, * 然后将其放到待排的序列的最左边,直到所有元素有序 * * 选择排序改进了冒泡排序,将交换次数从O(N^2)减少到O(N) * 不过比较次数还是O(N) */ package al; public class SelectSort { public static void main(String[] args) { SelectSort selectSort = new SelectSort(); int[] elements

  • 带你了解Java数据结构和算法之高级排序

    带你了解Java数据结构和算法之高级排序

    目录 1.希尔排序 ①.直接插入排序 ②.希尔排序图解 ③.排序间隔选取 ④.knuth间隔序列的希尔排序算法实现 ⑤.间隔为2h的希尔排序 2.快速排序 ①.快速排序的基本思路 ②.快速排序的算法实现 ③.快速排序图示 ④.快速排序完整代码 ⑤.优化分析 总结 1.希尔排序 希尔排序是基于直接插入排序的,它在直接插入排序中增加了一个新特性,大大的提高了插入排序的执行效率.所以在讲解希尔排序之前,我们先回顾一下直接插入排序. ①.直接插入排序 直接插入排序基本思想是每一步将一个待排序的记录,插入

  • Java数据结构及算法实例：朴素字符匹配 Brute Force

    /** * 朴素字符串算法通过两层循环来寻找子串, * 好像是一个包含模式的"模板"沿待查文本滑动. * 算法的思想是:从主串S的第pos个字符起与模式串进行比较, * 匹配不成功时,从主串S的第pos+1个字符重新与模式串进行比较. * 如果主串S的长度是n,模式串长度是 m,那么Brute-Force的时间复杂度是o(m*n). * 最坏情况出现在模式串的子串频繁出现在主串S中. * 虽然它的时间复杂度为o(m*n),但在一般情况下匹配时间为o(m+n), * 因此在实际中它被大量

随机推荐