Java数据结构和算法之 冒泡、选择、插入排序算法

数据结构和算法

数据结构是计算机存储,组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或存储效率。数据结构往往同高效的检索算法和索引技术有关;算法是指令的集合,是为解决特定问题而规定的一系列操作,可以简洁而快速的得到预期的结果集。程序=数据结构+算法

冒泡排序

冒泡大家都知道,在河水中的泡泡,水底刚冒出来的时候是比较小的,随着慢慢向水面浮起会逐渐增大。

图文描述
  • 首先创建一个数组 int[] arr ={60,40,80,20,30}
  • 然后进行冒泡排序如下图:


    逻辑图

    逻辑图
  • 计算的顺序
    1.第一次循环:arr[0]和arr[1],arr[1]和arr[2],arr[2]和arr[3],arr[3]和arr[4] 得到全部5位数中最大值
    2.第二次循环:arr[0]和arr[1],arr[1]和arr[2],arr[2]和arr[3] 得到剩下的4位数中最大的值
    3.第三次循环:arr[0]和arr[1],arr[1]和arr[2] 得到剩下的3位数中最大的值
    4.第四次循环:arr[0]和arr[1] 得到剩下的2位数中最大的值
冒泡算法的运作规律如下:
  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个的值。
  • 最外层可以用个for循环 ,循环4次 也就是(arr.lenght-1)次。
  • 第1次循环i=0时判断4次,第2次循环i=1时判断3次,第3次循环i=2时判断2次,第4循环i=3时判断1次。arr.lenght-1=4,4-0=4,4-1=3,4-2=2,4-3=1,内部循环判断每次都是从下标为0开始的,得到的规律内部j初始化时为0,j<(arr.lenght-1-i)内部判断的次数。
实现代码如下
import java.util.Arrays;
import java.util.Random;
public class MrpSort{

 public static void main(String[] args) {


    /**
     * 第一步首先创建一个数组 内容是100以内的随机数字
     */
    int[] arr = new int[20];
    Random random = new Random();
    for (int i = 0; i < arr.length; i++) {
        arr[i] = random.nextInt(100);
    }

    System.out.println("排序前数组="+ Arrays.toString(arr));

    for (int i = 0; i < arr.length-1; i++) {

        for(int j = 0; j < arr.length-1-i; j++){

            if (arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }

        }

    }

    System.out.println("排序后数组="+Arrays.toString(arr));

  }
 }
结果
冒泡排序

选择排序

选择排序是每一次从待排序的数据元素中选出最小的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。

图文描述
  • 首先创建一个数组 int[] arr ={60,40,80,20,30}
  • 然后进行选择排序如下图:


    选择排序

    选择排序
  • 计算顺序
    1. 第一次循环:arr[0]和arr[1],arr[0]和arr[2],arr[0]和arr[3],arr[0]和arr[4] 得到全部5位数中最小的值。
    2. 第二次循环:arr[1]和arr[2],arr[1]和arr[3],arr[1]和arr[4] 得到剩下四位数中最小的值。
    3. 第三次循环:arr[2]和arr[3],arr[2]和arr[4] 得到剩下三位数中最小的值。
    4. 第四次循环:arr[3]和arr[4] 得到剩下两位数中最小的值。
选择排序计算规律如下:
  • 从待排序序列中,用第一个数字和以下数字比较,如果arr[i]>arr[n] 则换值。
  • 最外层用个for循环,循环4次 也就是(arr.lenght-1)次。
  • 第1次循环i=0时判断4次,第2次循环i=1时判断3次,第3次循环i=2时判断2次,第4循环i=3时判断1次。arr.lenght-1=4,4-0=4,4-1=3,4-2=2,4-3=1,内部循环判断每次都是从下标为i开始的,得到的规律内部j初始化时为i+1,j<arr.lenght 内部判断的次数。
实现代码如下
  import java.util.Arrays;
  import java.util.Random;

  public class selectSort {

    public static void main(String[] args){

    /**
     * 第一步首先创建一个数组 内容是100以内的随机数字
     */
    int[] arr = new int[20];
    Random random = new Random();
    for (int i = 0; i < arr.length; i++) {
        arr[i] = random.nextInt(100);
    }

    System.out.println("排序前数组="+ Arrays.toString(arr));

    for (int i = 0; i < arr.length-1; i++) {

        for (int j = i+1; j < arr.length; j++){

            if (arr[i] > arr[j]){
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }

        }

    }

    System.out.println("排序后数组="+Arrays.toString(arr));
  }
}
结果
选择排序

插入排序

直接插入排序基本思想是每一步将一个待排序的记录,插入到前面已经排好序的有序序列中去,直到插完所有元素为止。从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的。

图文描述
  • 首先创建一个数组 int[] arr ={60,40,80,20,30}

  • 然后进行选择排序如下图(借用大神一张图):


    插入排序
  • 计算顺序

    1. 第一次循环:arr[1]和arr[0] 得到前两位最小的值。
    2. 第二次循环:arr[2]和arr[1],arr[2]和arr[0] 得到前三位最小的值。
    3. 第三次循环:arr[3]和arr[2],arr[3]和arr[1],arr[3]和arr[0] 得到前四位最小的值。
    4. 第四次循环: arr[4]和arr[3], arr[4]和arr[2], arr[4]和arr[1], arr[4]和arr[0] 得到五位最小的值。
选择排序计算规律如下:
  • 最外层用个for循环,循环4次,因为从下标为1开始,所以i<arr.lenght。
  • 拿到右边待排序的值和左边已排序最右边的值依次比较,如果待排序的值小于已排序的值继续对比。
实现代码如下
import java.util.Arrays;
import java.util.Random;

public class InsertSort {

  public static void main(String[] args){

    /**
     * 第一步首先创建一个数组 内容是100以内的随机数字
     */
    int[] arr = new int[20];
    Random random = new Random();
    for (int i = 0; i < arr.length; i++) {
        arr[i] = random.nextInt(100);
    }

    System.out.println("排序前数组="+ Arrays.toString(arr));

    int j;
    for(int i = 1 ; i < arr.length ; i++){
        int tmp = arr[i];//记录要插入的数据
        j = i;
        while(j > 0 && tmp < arr[j-1]){//从已经排序的序列最右边的开始比较,找到比其小的数
            arr[j] = arr[j-1];//向后挪动
            j--;
        }
        arr[j] = tmp;//存在比其小的数,插入
    }

    System.out.println("排序后数组="+Arrays.toString(arr));
  }

}
结果
插入排序

冒泡、选择、插入排序 效率对比

分别用冒泡、选择、插入排序,来实现同一个需求,分别看完成花费的时间。

实现代码
 import java.util.Random;

/**
 * 冒泡、选择、插入 排序对比
 */
   public class CompareSort {

    public static void main(String[] args){

    /**
     * 冒泡排序
     */
    int[] arrayBub = getArray();
    long startTimeBub = System.currentTimeMillis();
    for (int i = 0; i < arrayBub.length-1; i++) {
        for(int j = 0; j < arrayBub.length-1-i; j++){
            if (arrayBub[j] > arrayBub[j+1]){
                int temp = arrayBub[j];
                arrayBub[j] = arrayBub[j+1];
                arrayBub[j+1] = temp;
            }
        }
    }
    long endTimeBub = System.currentTimeMillis();
    System.out.println("冒泡排序时间戳= "+(endTimeBub-startTimeBub));

    /**
     * 选择排序
     */
    int[] arraySelect = getArray();
    long startTimeSelet = System.currentTimeMillis();
    for (int i = 0; i < arraySelect.length-1; i++) {
        for (int j = i+1; j < arraySelect.length; j++){
            if (arraySelect[i] > arraySelect[j]){
                int temp = arraySelect[i];
                arraySelect[i] = arraySelect[j];
                arraySelect[j] = temp;
            }
        }
    }
    long endTimeSelet = System.currentTimeMillis();
    System.out.println("选择排序时间戳= "+(endTimeSelet-startTimeSelet));

    /**
     * 插入排序
     */
    int[] arrayInsert = getArray();
    long startTimeInset = System.currentTimeMillis();
    int j;
    for(int i = 1 ; i < arrayInsert.length ; i++){
        int tmp = arrayInsert[i];//记录要插入的数据
        j = i;
        while(j > 0 && tmp < arrayInsert[j-1]){//从已经排序的序列最右边的开始比较,找到比其小的数
            arrayInsert[j] = arrayInsert[j-1];//向后挪动
            j--;
        }
        arrayInsert[j] = tmp;//存在比其小的数,插入
    }
    long endTimeInset = System.currentTimeMillis();
    System.out.println("插入排序时间戳= "+(endTimeInset-startTimeInset));

}

/**
 * 创建一个数组 内容是一万个1000以内的随机数字
 */
public static int[] getArray(){
    int[] arr = new int[10000];
    Random random = new Random();
    for (int i = 0; i < arr.length; i++) {
        arr[i] = random.nextInt(1000);
    }
    return arr;
}

}
结果
三种排序时间戳
  • 最终结论显示,插入排序的效率要高于选择排序高于冒泡排序。
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,588评论 6 496
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,456评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,146评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,387评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,481评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,510评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,522评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,296评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,745评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,039评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,202评论 1 343
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,901评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,538评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,165评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,415评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,081评论 2 365
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,085评论 2 352

推荐阅读更多精彩内容