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

相关文章

来自专栏猿人谷

常见排序算法分析

一.常见排序算法的实现 1.冒泡排序 冒泡排序是非常容易理解和实现,,以从小到大排序举例: 设数组长度为N。 1.比较相邻的前后二个数据,如果前面数据大于后面...

1828
来自专栏小小挖掘机

各种排序算法的分析及java&python实现

排序大的分类可以分为两种:内排序和外排序。在排序过程中,全部记录存放在内存,则称为内排序,如果排序过程中需要使用外存,则称为外排序。下面讲的排序都是属于内排序。...

3467
来自专栏机器学习从入门到成神

一道归并排序题的解析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

552
来自专栏用户画像

7.2.3 插入排序之希尔排序

直接插入排序算法适用于基本有序的排序表和数据量不大的排序。基于这两点,1959年D.L.Shell提出了希尔排序,又称为缩小增量排序。

531
来自专栏fangyangcoder

算法导论中的四种基本排序

                                                        by方阳

742
来自专栏java一日一条

八大排序算法

(1)基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一...

491
来自专栏Java3y

希尔排序就这么简单

一、希尔排序介绍 来源百度百科: 希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort...

3956
来自专栏青玉伏案

算法与数据结构(十三) 冒泡排序、插入排序、希尔排序、选择排序(Swift3.0版)

本篇博客中的代码实现依然采用Swift3.0来实现。在前几篇博客连续的介绍了关于查找的相关内容, 大约包括线性数据结构的顺序查找、折半查找、插值查找、Fibon...

1767
来自专栏专注研发

桶排序/基数排序(Radix Sort)

基本思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要...

802
来自专栏aCloudDeveloper

经典排序之 插入排序

Author: bakari  Date: 2012.7.21 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之...

1778

扫码关注云+社区