4.排序(上)

Wesley13
• 阅读 604

点击使用幕布网页版查看(含思维导图)

有序度:数组中具有有序关系的元素对的个数

有序元素对:a[i] <= a[j],如果i < j。

完全有序的数组,有序度就是 n * (n - 1) /2(满有序度)

逆序度 = 满有序度 - 有序度
  • 冒泡排序

    • 特性

      • 原地
      • 稳定
      • O(n**2)(最少0次交换,最多n*(n-1)/2次交换)
    • 冒泡排序每次比较相邻两数,若为逆序则交换,所以冒泡排序交换次数总是确定的,即为逆序度。

  • 插入排序

    • 特性

      • 原地
      • 稳定
      • O(n**2)(将一个数据插入数组(O(n)),重复n次)
    • 插入排序将数组分为两个区间:已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组首元素。每次取未排序区间元素在已排序区间中找到合适的位置插入,直到未排序区间为空。插入排序移动操作的次数是固定的,等于逆序度。

  • 两种排序算法比较

    • 虽然两种排序算法相同,都是原地、稳定排序,但插入排序要比冒泡排序更优

    • 冒泡排序交换次数和插入排序数据移动次数一样,都等于逆序度

    • 冒泡排序数据交换需要3个赋值操作,而插入排序数据移动只需要1个。

冒泡排序和插入排序Java实现

public class Sort {
    /**
     * 冒泡排序
     *
     * @param arr
     * @param n
     */
    public static void bubbleSort(int arr[], int n) {
        if (n <= 1) return;
        int count = 0;
        //最多进行n - 1次冒泡
        for (int i = 0; i < n; i++) {
            boolean swaped = false;
            for (int j = 0; j < n - i - 1; j++) {
                //每次比较相邻数 把较大的放在后面
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = temp;
                    swaped = true;
                }
            }
            count++;
            if (!swaped) break;
        }
        System.out.println("进行了" + count + "次冒泡");
    }

    /**
     * 插入排序
     *
     * @param arr
     * @param n
     */
    public static void inserctionSort(int arr[], int n) {
        if (n <= 1) return;
        //将数组分为已排序部分和未排序部分
        for(int i = 1; i < n; i++) {
            int value = arr[i];//未排序部分的第一个值
            int j = i - 1;
            //每次将未排序部分的第一个值插入已排序部分中
            for(; j >= 0; j--){
                //寻找插入点 arr[j]为第一个小于等于value的值
                if(arr[j] > value)
                    arr[j + 1] = arr[j];
                else
                    break;
            }
            //将value插入到j后面
            arr[j + 1] = value;
        }
    }

    public static void sortTest() {
        int arr[] = {3, 5, 4, 1, 2, 6};
        printArr(arr);
        inserctionSort(arr, arr.length);
        printArr(arr);
    }

    public static void printArr(int arr[]) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Easter79 Easter79
3年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Stella981 Stella981
3年前
JS 对象数组Array 根据对象object key的值排序sort,很风骚哦
有个js对象数组varary\{id:1,name:"b"},{id:2,name:"b"}\需求是根据name或者id的值来排序,这里有个风骚的函数函数定义:function keysrt(key,desc) {  return function(a,b){    return desc ? ~~(ak
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Stella981 Stella981
3年前
Android蓝牙连接汽车OBD设备
//设备连接public class BluetoothConnect implements Runnable {    private static final UUID CONNECT_UUID  UUID.fromString("0000110100001000800000805F9B34FB");
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
9个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这