Java数据结构和算法总结-冒泡排序、选择排序、插入排序算法分析

前言:排序在算法中的地位自然不必多说,在许多工作中都用到了排序,就像学生成绩统计名次、商城商品销量排名、新闻的搜索热度排名等等。也正因为排序的应用范围如此之广,引起了许多人深入研究它的兴趣,直至今天,排序算法已经出现了很多种。本篇博文主要介绍常见的八种排序算法,总得来说,不同的排序算法在不同的场景下都有着自己独特的优点,例如一下简单的冒泡排序、选择排序、插入排序不仅思路简单,有利于我们理解,而且在小规模的数据量的处理中并不逊色。接下来我们就一一分析一下各算法的优缺点以及时间复杂度。

  本篇博文的所有代码已上传 github ,对应工程的 exercise 模块下的 cn.codingblock.sort 包,下载地址:https://github.com/lgliuwei/DataStructureStudy,项目工程为 IntelliJ IDEA 环境,童鞋不妨下载下来,参照着代码看博文岂不是效果更好~(额~由于本工程为练习工程,结构比较随意而且还有重复代码,参考时还请多找找:D)

一、冒泡排序

  冒泡排序非常简单,也很易于理解,其逻辑思路就像水里面冒气泡一样,越往上气泡越大,也因此而得名冒泡排序,其具体规则如下:

  1、从一组的数据的起始位置开始依次向后比较相邻两个数,

  2、如果前一个数比后一个数大则交换位置,

  3、一直比较到最后一个数。

  此时,这组数的最后一个数一定是最大的了,然后进行下一轮如此比较到倒数第二个数,再下一轮比较到倒数第三个,如此循环,直到有一轮比较到第二个数结束,最终这一组数就是有序的了。

  上代码让日志演示一下过程,具体代码如下:

 1     /**
 2      * 冒泡排序
 3      * @param nums
 4      */
 5     public void bubbleSort(int[] nums){
 6         int count = 0;// 日志辅助代码
 7         for (int out = nums.length - 1; out > 1; out--){
 8             for (int in = 0; in < out; in++) {
 9                 Logger.print("比较 " + nums[in] + " , " + nums[in + 1]);
10                 if (nums[in] > nums[in + 1]) {
11                     int temp = nums[in+1];
12                     nums[in+1] = nums[in];
13                     nums[in] = temp;
14                     Logger.println(": 交换: ");// 日志辅助代码
15                     display(nums, in, in + 1);// 日志辅助代码
16                 } else  {
17                     Logger.println(": 不交换");// 日志辅助代码
18                 }
19             }
20             Logger.print(">>第" + (++count) + "趟冒泡:");// 日志辅助代码
21             display(nums);// 日志辅助代码
22         }
23     }

  日志如下:

排序前:23, 52, 81, 69, 78, 32, 67, 70, 36, 73, 
比较 23 , 52: 不交换
比较 52 , 81: 不交换
比较 81 , 69: 交换: 
23, 52, [69], [81], 78, 32, 67, 70, 36, 73, 
比较 81 , 78: 交换: 
23, 52, 69, [78], [81], 32, 67, 70, 36, 73, 
比较 81 , 32: 交换: 
23, 52, 69, 78, [32], [81], 67, 70, 36, 73, 
比较 81 , 67: 交换: 
23, 52, 69, 78, 32, [67], [81], 70, 36, 73, 
比较 81 , 70: 交换: 
23, 52, 69, 78, 32, 67, [70], [81], 36, 73, 
比较 81 , 36: 交换: 
23, 52, 69, 78, 32, 67, 70, [36], [81], 73, 
比较 81 , 73: 交换: 
23, 52, 69, 78, 32, 67, 70, 36, [73], [81], 
>>第1趟冒泡:23, 52, 69, 78, 32, 67, 70, 36, 73, 81, 
比较 23 , 52: 不交换
比较 52 , 69: 不交换
比较 69 , 78: 不交换
比较 78 , 32: 交换: 
23, 52, 69, [32], [78], 67, 70, 36, 73, 81, 
比较 78 , 67: 交换: 
23, 52, 69, 32, [67], [78], 70, 36, 73, 81, 
比较 78 , 70: 交换: 
23, 52, 69, 32, 67, [70], [78], 36, 73, 81, 
比较 78 , 36: 交换: 
23, 52, 69, 32, 67, 70, [36], [78], 73, 81, 
比较 78 , 73: 交换: 
23, 52, 69, 32, 67, 70, 36, [73], [78], 81, 
>>第2趟冒泡:23, 52, 69, 32, 67, 70, 36, 73, 78, 81, 
比较 23 , 52: 不交换
比较 52 , 69: 不交换
比较 69 , 32: 交换: 
23, 52, [32], [69], 67, 70, 36, 73, 78, 81, 
比较 69 , 67: 交换: 
23, 52, 32, [67], [69], 70, 36, 73, 78, 81, 
比较 69 , 70: 不交换
比较 70 , 36: 交换: 
23, 52, 32, 67, 69, [36], [70], 73, 78, 81, 
比较 70 , 73: 不交换
>>第3趟冒泡:23, 52, 32, 67, 69, 36, 70, 73, 78, 81, 
比较 23 , 52: 不交换
比较 52 , 32: 交换: 
23, [32], [52], 67, 69, 36, 70, 73, 78, 81, 
比较 52 , 67: 不交换
比较 67 , 69: 不交换
比较 69 , 36: 交换: 
23, 32, 52, 67, [36], [69], 70, 73, 78, 81, 
比较 69 , 70: 不交换
>>第4趟冒泡:23, 32, 52, 67, 36, 69, 70, 73, 78, 81, 
比较 23 , 32: 不交换
比较 32 , 52: 不交换
比较 52 , 67: 不交换
比较 67 , 36: 交换: 
23, 32, 52, [36], [67], 69, 70, 73, 78, 81, 
比较 67 , 69: 不交换
>>第5趟冒泡:23, 32, 52, 36, 67, 69, 70, 73, 78, 81, 
比较 23 , 32: 不交换
比较 32 , 52: 不交换
比较 52 , 36: 交换: 
23, 32, [36], [52], 67, 69, 70, 73, 78, 81, 
比较 52 , 67: 不交换
>>第6趟冒泡:23, 32, 36, 52, 67, 69, 70, 73, 78, 81, 
比较 23 , 32: 不交换
比较 32 , 36: 不交换
比较 36 , 52: 不交换
>>第7趟冒泡:23, 32, 36, 52, 67, 69, 70, 73, 78, 81, 
比较 23 , 32: 不交换
比较 32 , 36: 不交换
>>第8趟冒泡:23, 32, 36, 52, 67, 69, 70, 73, 78, 81, 
排序后:23, 32, 36, 52, 67, 69, 70, 73, 78, 81,    

  冒泡排序的时间复杂度:O(n^2)。

  通过分析我们可以得出,如果对 N 个数据项进行排序,一般情况下第一趟排序比较了 N-1 次,第二趟排序比较了 N-2 次,依次类推。所以冒泡排序对N个数据项排序时需要比较的次数为:

  (N-1)+(N-2)+(N-3)+....+ = N*(N-1)/2 方便起见,近似看做比较了 (N^2)/2 次数。

  用大 O 表示法忽略常数,所以其时间复杂度为:O(n^2)。 

二、选择排序

  选择排序是在冒泡排序的基础上做了一些改进,虽然比较次数仍然是O(n^2),但它将必要的交换次数从O(n^2)将到了O(n)次,其排序规则如下:

  1、从数组的0下标开始标记为最小,

  2、从1下标开始与标记下标的值比较,如果小于标记下标的值则更新将标记赋值为1下标,依次往后类推直到最后遍历完数组,最后将0下标与最小标记下标的值交换位置。

  3、然后再从数组1小标开始比较为最小,类比第二步最终交换1下标与最小标记下标的位置。依次类推。。。

  选择排序的一趟排序过程示意图(非排序全程):

  选择详细代码如下:

 1     /**
 2      * 选择排序
 3      * @param nums
 4      */
 5     public void selectionSort(int[] nums) {
 6         int min;
 7         for (int out = 0; out < nums.length; out++) {
 8             min = out;
 9             for (int in = out + 1; in <nums.length; in++) {
10                 if (nums[in] < nums[min]) {
11                     min = in;
12                 }
13             }
14             int temp = nums[min];
15             nums[min] = nums[out];
16             nums[out] = temp;
17         }
18     }             

   选择排序的时间复杂度为:O(N^2)。

  相比冒泡而言,选择排序虽然大大减少了交换次数,但是也比较了和冒泡相同的次数,所以其时间复杂度也为:O(N^2)。

三、插入排序

  插入排序是根据有序插入的思想来的,可以对照上篇博文中的有序插入来理解插入排序,其大概规则如下:

  1、最数组的1下标开始赋值给临时变量,看成待插入元素,

  2、从数组的1下标向前遍历,凡是大于临时变量的元素均后移一位,直到遇到不大于临时变量的值时将临时变量插入到它后一位。

  3、然后在从数组的2下标开始赋值给临时变量,并从2下标向前遍历依照第二步遇到不大于临时变量时将临时变量插入到它后一位,依次类推...

  插入排序的详细代码如下:

 1     /**
 2      * 插入排序
 3      * @param nums
 4      */
 5     public void insertionSort1(int[] nums) {
 6         int temp;
 7         int in;
 8         for(int out = 1; out < nums.length; out++) {
 9             temp = nums[out];
10             in = out;
11             while (in > 0 && nums[in - 1] > temp) {
12                 nums[in] = nums[in - 1];
13                 in--;
14             }
15             nums[in] = temp;
16         }
17     }

  插入排序的时间复杂度:O(N^2)。

  对于随机数据,插入排序速度是冒泡排序的二倍,比选择排序也要快一点,而对于基本有序的数据来说插入排序表现则要出色的多,因为基本有序的数据排序时,while 循环的条件大部分情况下都不成立,这样基本就相当于只执行了外层的一层循环,某些理想情况下插入排序的时间复杂度可以达到 O(N),但通常情况下,插入平均时间复杂度为:O(N^2)。

四、小结

  除了上面介绍的三种简单排序之外,还有归并排序、希尔排序、快速排序、基数排序、堆排序等等,后面这几种都是高级排序,稍微复杂一些,而且用到了递归、树等知识,所以这些排序将会在以后的博文中介绍,本篇中的三种排序对比如下:

排序名称

时间复杂度

分析

级别

冒泡排序

O(N^2)

速度慢,交换次数多。

简单排序

选择排序

O(N^2)

速度比冒泡快。

简单排序

插入排序

O(N^2)

速度是冒泡的二倍,优于选择排序,在基本有序的数据中表现出色。

简单排序

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Bingo的深度学习杂货店

Python实现十大经典排序算法

话不多数,先上两张图: ? ? 名词解释: n:数据规模 k:“桶”的个数 In-place:占用常数内存,不占用额外内存 Out-place:占用额外内...

2.2K6
来自专栏编程

从零基础开始学习PHP(七)

貌似有两周没有更新文章了、"忙"都是借口、不过我是真的忙、一天瞎忙活。希望多多理解。在这里我要感谢那些支持我的小伙伴、因为有你们的支持、我知道我要对我的文章以及...

2085
来自专栏深度学习与计算机视觉

Python Numpy简介

原文地址:What is Numpy? Numpy是应用Python进行科学计算时的基础模块。它是一个提供多维数组对象的Python库,除此之外,还包含了多种衍...

21810
来自专栏小古哥的博客园

读书笔记-JavaScript面向对象编程(一)

前前后后大概花了两周的时间,终于把这本书大致看完了,对之前javascript高级程序设计中模糊不清的概念,有了一些新的看法和角度,整体上来说,本书还是一本比较...

3157
来自专栏C语言及其他语言

C语言经典笔试题

1.以下程序的结果是什么? ? A: main()函数里的i是一个未定义值 B: main()函数的i为1 C: 编译器不允许这种写法 D: main()里i的...

3897
来自专栏恰同学骚年

你必须知道的指针基础-3.指针的移动及指针的危险

  指针每次加一就是指针向前移动指针类型对应的字节数。下面通过一个int指针来指向一个int数组,看看指针的加法运算到底是个什么鬼?

802
来自专栏CSDN技术头条

算法入门,其实可以像读小说一样有趣

我琢磨着目录,心想终于要把这些主题搞明白了。但那本书深奥难懂,看了几周后我就放弃了。直到遇到一位优秀的算法教授后,我才认识到这些概念是多么地简单而优雅。

4384
来自专栏WD学习记录

Python数据结构与算法笔记(4)

当数据项存储在诸如列表的集合中时,我们说它们具有线性或顺序关系。每个数据项都存储在相对与其他数据项的位置。在Python列表中,这些相对位置是单个项的索引值。由...

1091
来自专栏五分钟学算法

看完动画你还会不懂 快速排序么

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画...

1165
来自专栏一名合格java开发的自我修养

MapReduce中一次reduce方法的调用中key的值不断变化分析及源码解析

摘要:mapreduce中执行reduce(KEYIN key, Iterable<VALUEIN> values, Context context),调用一...

1053

扫码关注云+社区