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 条评论
登录 后参与评论

相关文章

来自专栏有趣的Python

算法与数据结构(七) 图论

图论 Graph Theory 图论并不是研究图画。而是研究由节点和边所构成的数学模型 ? 图论抽象模型 万事开头难,虽然看上去很复杂,但是慢慢学习深入之后会体...

4008
来自专栏新智元

【看图识算法】这是你见过最简单的 “算法说明书”

【新智元导读】像阅读宜家的安装说明书一样学习算法,是怎样的体验?不伦瑞克工业大学的三名研究者制作了这份“算法说明书”,简明传神地解释了一些基本算法,一起来看图说...

3458
来自专栏大数据挖掘DT机器学习

R语言vs Python:数据分析哪家强?

本文章旨在更客观地看待这两门语言。我们会平行使用Python和R分析一个数据集,展示两种语言在实现相同结果时需要使用什么样的代码。这让我们了解每种语言的优缺点,...

62111
来自专栏Python小屋

Python版选择排序算法

关于Python版冒泡排序算法请参考:Python版冒泡法排序算法。 def selectSort(lst, reverse=False): leng...

2675
来自专栏潇涧技术专栏

Python Algorithms - C4 Induction and Recursion and Reduction

Python算法设计篇(4) Chapter 4: Induction and Recursion and Reduction

923
来自专栏Python攻城狮

Python数据科学(九)- 使用Pandas绘制统计图表1.信息可视化

因为人对图像信息的解析效率比文字更高,所以可视化可以使数据更为直观,便于理解,使决策变得高效,所以信息可视化就显得尤为重要。

793
来自专栏数据科学与人工智能

【Python环境】监督学习之KNN算法

1、ipython是一个python的交互式shell,比默认的python shell好用得多,支持变量自动补全,自动缩进,支持bash shell命令,内置...

2337
来自专栏Deep Learning 笔记

图像识别(三)cifar10.py

tf.app.flags.DEFINE_integer()等函数是添加了命令行的可选参数

824
来自专栏用户画像

7.6.2 内部排序算法的应用

1)若n较小(N<=50),则可以采用直接插入排序或简单选择排序。由于直接插入排序所需的记录移动操作较简单选择排序多,因而当记录本身信息量较大时,用简单选择排序...

541
来自专栏静默虚空的博客

排序算法系列

概述 概念 排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。 排序分为内部排序和外部排序。 若整个排序过程不需要访问...

2007

扫码关注云+社区