经典排序算法(Java版)

时间:2023-01-07 00:26:07
1、冒泡排序 Bubble Sort
最简单的排序方法是冒泡排序方法。这种方法的基本思想是,将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理,就是自底向上检查一遍这个序列,并时刻注意两个相邻的元素的顺序是否正确。如果发现两个相邻元素的顺序不对,即“轻”的元素在下面,就交换它们的位置。显然,处理一遍之后,“最轻”的元素就浮到了最高位置;处理二遍之后,“次轻”的元素就浮到了次高位置。在作第二遍处理时,由于最高位置上的元素已是“最轻”元素,所以不必检查。一般地,第i遍处理时,不必检查第i高位置以上的元素,因为经过前面i-1遍的处理,它们已正确地排好序。这个算法可实现如下。
算法如下:
/**
     *冒泡排序
     *@paramsrc待排序数组
     */
    void doBubbleSort(int[] src)
    {
       int len=src.length;
       for(int i=0;i<len;i++)
       {
           for(int j=i+1;j<len;j++)
           {
              int temp;
              if(src[i]>src[j])
              {
                  temp=src[j];
                  src[j]=src[i];
                  src[i]=temp;
              }            
           }
           printResult(i,src);
       }     
    }
2、选择排序 Selection Sort
选择排序的基本思想是:对待排序的记录序列进行n-1遍的处理,第1遍处理是将L[1..n]中最小者与L[1]交换位置,第2遍处理是将L[2..n]中最小者与L[2]交换位置,......,第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样,经过i遍处理之后,前i个记录的位置就已经按从小到大的顺序排列好了。
  当然,实际操作时,也可以根据需要,通过从待排序的记录中选择最大者与其首记录交换位置,按从大到小的顺序进行排序处理。
算法如下:
       /**
     *选择排序
     *@paramsrc待排序的数组
     */
    void doChooseSort(int[] src)
    {
       int len=src.length;
       int temp;
       for(int i=0;i<len;i++)
       {
           temp=src[i];
           int j;
           int samllestLocation=i;//最小数的下标
           for(j=i+1;j<len;j++)
           {
              if(src[j]<temp)
              {
                  temp=src[j];//取出最小值
                  samllestLocation=j;//取出最小值所在下标
              }
           }
           src[samllestLocation]=src[i];
           src[i]=temp;
           printResult(i,src);
       }
    }
3、插入排序 Insertion Sort
插入排序的基本思想是,经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,使得L[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。首先比较L[i]和L[i-1],如果L[i-1]≤ L[i]騆[1..i]已排好序,第i遍处理就结束了;否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),使得L[j] ≤L[j+1]时为止。
  简言之,插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置,直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种,这里只介绍直接插入排序,折半插入排序留到“查找”内容中进行。
  图1演示了对4个元素进行直接插入排序的过程,共需要(a),(b),(c)三次插入。
经典排序算法(Java版)
图1 对4个元素进行插入排序
在下面的插入排序算法中,为了写程序方便我们可以引入一个哨兵元素L[0],它小于L[1..n]中任一记录。所以,我们设元素的类型ElementType中有一个常量-∞,它比可能出现的任何记录都小。如果常量-∞不好事先确定,就必须在决定L[i]是否向前移动之前检查当前位置是否为1,若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时,就将L[i]放入L[0]中,这样也可以保证在适当的时候结束第i遍处理。下面的算法中将对当前位置进行判断。
算法如下:
    /**
     *插入排序(WHILE循环实现)
     *@paramsrc待排序数组
     */
    void doInsertSort1(int[] src)
    {
       int len=src.length;
       for(int i=1;i<len;i++)
       {  
           int temp=src[i];
           int j=i;
          
           while(src[j-1]>temp)
           {
              src[j]=src[j-1];
              j--;
              if(j<=0)
                  break;
           }
           src[j]=temp;
           printResult(i+1,src);
       }
    }
    /**
     *插入排序(FOR循环实现)
     *@paramsrc待排序数组
     */
    void doInsertSort2(int[] src)
    {
       int len=src.length;
       for(int i=1;i<len;i++)
       {
           int j;
           int temp=src[i];
           for(j=i;j>0;j--)
           {
              if(src[j-1]>temp)
              {
                  src[j]=src[j-1];
                 
              }else//如果当前的数,不小前面的数,那就说明不小于前面所有的数,
                   //因为前面已经是排好了序的,所以直接通出当前一轮的比较
                  break;
           }
           src[j]=temp;
           printResult(i,src);
       }
    }

经典排序算法(Java版)的更多相关文章

  1. 排序算法Java版,以及各自的复杂度,以及由堆排序产生的top K问题

    常用的排序算法包括: 冒泡排序:每次在无序队列里将相邻两个数依次进行比较,将小数调换到前面, 逐次比较,直至将最大的数移到最后.最将剩下的N-1个数继续比较,将次大数移至倒数第二.依此规律,直至比较结 ...

  2. 经典排序算法 — C&num; 版(上)

    提起排序,与我们的息息相关,平时开发的代码少不了排序. 经典的排序算法又非常多,我们怎么评价一个排序算法的好坏呢? 其实可以这样想,要细致的比较排序算法好坏,那我们就从多方面尽可能详细的对比 一.效率 ...

  3. 经典排序算法&lpar;Java实现&rpar;

    以下程序均将数据封装于DataWrap数据包装类中,如下所示: //数据包装类 class DataWrap implements Comparable<DataWrap> { int d ...

  4. 排序算法系列:选择排序算法JAVA版(靠谱、清晰、真实、可用、不罗嗦版)

    在网上搜索算法的博客,发现一个比较悲剧的现象非常普遍: 原理讲不清,混乱 啰嗦 图和文对不上 不可用,甚至代码还出错 我总结一个清晰不罗嗦版: 原理: 从数组头元素索引i开始,寻找后面最小的值(比i位 ...

  5. 常用排序算法--java版

    package com.whw.sortPractice; import java.util.Arrays; public class Sort { /** * 遍历一个数组 * @param sor ...

  6. 排序算法Java版

    选择排序: public static void selectSort(int[]a) { int minIndex=0; int temp=0; if((a==null)||(a.length==0 ...

  7. 一文搞定十大经典排序算法(Java实现)

    本文总结十大经典排序算法及变形,并提供Java实现. 参考文章: 十大经典排序算法总结(Java语言实现) 快速排序算法—左右指针法,挖坑法,前后指针法,递归和非递归 快速排序及优化(三路划分等) 一 ...

  8. 十大经典排序算法最强总结(含JAVA代码实现)&lpar;转&rpar;

    十大经典排序算法最强总结(含JAVA代码实现)   最近几天在研究排序算法,看了很多博客,发现网上有的文章中对排序算法解释的并不是很透彻,而且有很多代码都是错误的,例如有的文章中在“桶排序”算法中对每 ...

  9. Java实现经典七大经典排序算法

    利用Java语言实现七大经典排序算法:冒泡排序.选择排序.插入排序.希尔排序.堆排序.归并排序以及快速排序. 分类 类别 算法 插入排序类 插入排序.希尔排序 选择排序类 选择排序.堆排序 交换排序类 ...

  10. 十大经典排序算法最强总结(含Java、Python码实现)

    引言 所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作.排序算法,就是如何使得记录按照要求排列的方法.排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面 ...

随机推荐

  1. mysql计划字段中有多少个逗号,或者某个标识符

    eg:计划url中有多少个小数点 select length('www.mysql.com')-length(REPLACE('www.mysql.com','.',''));

  2. 视频 之自定义VideoView

    package com.lvshandian.partylive.view;import android.content.Context;import android.util.AttributeSe ...

  3. spring jdbc&period;property的配置与使用

    jdbc.properties driver=com.mysql.jdbc.Driver url=jdbc:mysql://127.0.0.1:3306/ssi1 username=root pass ...

  4. 利用spring,实现package下的类扫描

    项目中需要用到包扫描的情况是很多的,一般是在项目初始化的时候,根据一些条件来对某个package下的类进行特殊处理.现在想实现的功能是,在一个filter或interceptor初始化的时候,扫描指定 ...

  5. C语言二维数组实现扫雷游戏

    #include<stdio.h> //使用二维数组实现 扫雷 int main() { char ui[8][8]={ '+','+','+','+','+','+','+','+', ...

  6. Android如何实现茄子快传

    Android如何实现茄子快传茄子快传是一款文件传输应用,相信大家都很熟悉这款应用,应该很多人用过用来文件的传输.它有两个核心的功能: 端到端的文件传输Web端的文件传输这两个核心的功能我们具体来分析 ...

  7. php 根据身份证获取出身地址

    <?php /**根据身份证算出地址****/ class addr{ /**获取省***/ public function get_shenfen($id){ //截取前两位数 $index ...

  8. 31&period; centos 下修改oracle的编码

    [root@localhost ~]# su - oracle[oracle@localhost ~]$ vi /home/oracle/.bash_profile # .bash_profile # ...

  9. CCRepeatForever和CCDelayTime

    有限次执行一组动作和无限次执行一组动作 void ActionRotateJerk::onEnter() { ActionsDemo::onEnter(); centerSprites(); CCFi ...

  10. js随机数生成与排序

    'use strict'; // 排序算法. // 生成一个指定数量的不含重复数字的随机数组 function ranArr(n,callback) { var res = []; var tmp ; ...