专栏首页颍川Java数据结构与算法--简单排序

Java数据结构与算法--简单排序

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/wangtongxue123456/article/details/72638485

简单排序

本文讨论比较简单的排序算法:冒泡排序、选择排序、插入排序

三个算法都包括如下两个步骤。

  • 比较两个数据项
  • 交换两个数据项、或复制其中一项。

冒泡排序

冒泡排序算法运行起来非常慢,但是在概念上他是排序算法中最简单的。

冒泡排序遵循的规则: 1. 比较两个数据 2. 如果左边的数据大,则两个数据交互位置。 3. 向右移动一个位置,比较下面两个数据。(沿着这个队列一直比较下去,一直比较到队列的最右端),这时最右端的数据应该会是最大的数。 4. 当碰到第一个排定的数据后,就返回队列的左端重新开始下一趟排序。 代码实现

/**
 * 冒泡排序
 */
public class BubbleSort {
    //初始化数组
    private static long a[]=new long[]{11,4,7,9,2,10,23,8,34,29};
    //数组长度
    private static int nElems=a.length;
    public static void main(String[] args) {
        int in,out;
        for (out=nElems-1;out>1;out--){ //
            for (in=0;in<out;in++){ 
                //比较相邻的元素。如果第一个比第二个大,就交换他们两个。
                if (a[in]>a[in+1]){
                    swap(in,in+1);
                }
            }
        }
        //输出排序
        for (long l:a){
            System.out.print(l+" ");
        }
    }
    //交换数据
    private static void swap(int in, int i) {
        long temp=a[in];
        a[in]=a[in+1];
        a[in+1]=temp;
    }

算法思路 1.将最小的数据项放在数组的最开始,并将最大的数据项放在数组的最后。 2.外层for 循环的计数器out从数组的最后开始,没经过一次循环out减一。下标大于out的数据项都是已经排好序的,变量out每完成一次内部循环(计数器为in)后就左移一位。 3.内层for循环计数器in从数组的最开始算起(in=0),没完成一次内部循环体加一,当它等于out时结束一次循环,在内层for循环体重,数组下标in和in+1的两个数据项进行比较,如果in数据大于in+1数据项,则交换数据。 4.为了清晰增加独立的swap()方法执行交换,但是它会增加一些额外的消耗,如果自己使用排序程序,最好将交换操作这段代码直接放到程序中。这样可以提高一些速度。

选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法

代码实现

/**
 * Created by YcDr on 2017/5/24.
 * 选择排序
 */
public class SelectSort {
    //初始化数组
    private static long a[]={12,34,19,2,54,13,11,33,18,9};
    //数组长度
    private static int nElems=a.length;

    public static void main(String[] args) {
        int in,out,temp;
        for (out=0;out<nElems;out++){
            temp=out;//temp临时变量,用于存取最小值下标
            for (in=out+1;in<nElems;in++){
                    if (a[temp]>a[in]){
                        temp=in;
                    }
            }
            //每次循环找出最小值下标后,在进行数据交换
            swap(out,temp);
        }

        for (long l:a)
            System.out.print(l+" ");
    }
    //交换数据
    private static void swap(int i,int t) {
        long temp=a[t];
        a[t]=a[i];
        a[i]=temp;
    }
}

与冒泡排序比较

选择排序与冒泡排序相比,都执行了相同的比较次数N*(N-1)/2,但是相比冒泡排序,选择排序降低了交换数据的次数。 选择排序和冒泡排序一样运行了O(N^2)时间,但是显然选择排序要比冒泡排序更快一些,因为选择排序交换次数很少,如果交换时间及比比较时间及要大的多时,选择排序实际要快的多。

插入排序

在大多数情况下,插入算法是本章描述的基本排序算法中最后的一种,虽然插入排序算法任然需O(N^2) 的时间,但是在一般情况下他要比冒泡排序快一倍,比选择排序还要快一点。

算法思路 1. 默认序列中的第0个元素是有序的; 2. 从下标为1(下标从0开始)的元素开始,取当前下标i位置处的元素a[i]保存到一个临时变量里; 3. 对前半部分有序序列的循环遍历,并与临时变量比较,直到遇到一个比临时变量小的元素(这里默认是从小到大排序),交换数据 4. 将待插入元素的下标 i 向后推移一个位置; 5. 重复进行第2步到第4步,直到乱序序列中的元素被全部插入到有序序列中;

代码实现

/**
 * Created by YcDr on 2017/5/25.
 * 插入排序
 */
public class InsertSort {
    //初始化数组
    private static long a[]={12,19,34,2,54,13,11,33,18,9};
    //数组长度
    private static int nElems=a.length;

    public static void main(String[] args) {
        int in,out;
        for (out=1;out<nElems;out++){
            long temp=a[out];
            in=out;
            while (in>0&&a[in-1]>=temp){
                a[in]=a[in-1];
                in--;
            }
            a[in]=temp;
        }

        for (long l:a){
            System.out.print(l+" ");
        }
    }
}

稳定性

有些时候,排序要考虑数据项拥有相同关键字的情况,例如,雇员姓名按字典进行排序,现在又想按邮政编码排序,并希望,让不需要排序的数据保持原来的排序。这种情况下,则只需要算法对需要排序的数据进行排序,让不需要的数据保持原来的顺序,某些算法满足这样的要求,他们就可以称为稳定的算法。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 计算机思维--0和1与逻辑

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    颍川
  • Oracle数据类型之number

    s:小数位,scale,是小数点右边的位数,取值范围是-84~127,默认值取决于p,如果没有指定p,那么s是最大范围,如果指定了p,那么s=0。 ...

    颍川
  • bootstrapValidator 中文API

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    颍川
  • C++ 多进程并发框架FFLIB之Tutorial

          FFLIB框架是为简化分布式/多进程并发而生的。它起始于本人尝试解决工作中经常遇到的问题如消息定义、异步、多线程、单元测试、性能优化等。基本介绍可以...

    知然
  • 数据科学家令人惊叹的排序技巧

    原题 | Surprising Sorting Tips for Data Scientists

    kbsc13
  • 如何通过跨学科应用提高对函数式程序设计的兴趣(cs)

    函数式编程代表了应用和实现软件的现代化工具。函数式编程的最新发展报告了这种范式中越来越多的方法。然而,缺乏广泛的跨学科应用。我们的目标是提高学生的兴趣,追求进一...

    用户7454091
  • IOS safari浏览器登陆时Cookie无法保存的问题

    近期完成了一个儿童的测评项目,测试到最后的时候发现在ipad mini上登陆成功之后无法跳转页面,而安卓和pc端都可以,找了大半天bug,发现其他的苹果设备都没...

    李文杨
  • 排序概念

    qubianzhong
  • 视图——机房收费系统

    在第一次做机房收费系统时,学生信息和卡的信息是在同一张表中的,而机房收费系统重构时,对数据库进行了重新设计,学生信息和卡的信息被分到了单独的两张表中(遵照三范...

    令仔很忙
  • R语言的繁荣背后何尝没有隐患

    但是参与的玩家多了之后,也会出现一些冲突。最近在运行一些三五年前的代码报错了,引发了我的思考。

    生信技能树

扫码关注云+社区

领取腾讯云代金券