精选留言(430)

• 
  双木公子

  置顶

  2018-10-15

  对于老师所提课后题，觉得应该有个前提，是否允许修改链表的节点value值，还是只能改变节点的位置。一般而言，考虑只能改变节点位置，冒泡排序相比于数组实现，比较次数一致，但交换时操作更复杂；插入排序，比较次数一致，不需要再有后移操作，找到位置后可以直接插入，但排序完毕后可能需要倒置链表；选择排序比较次数一致，交换操作同样比较麻烦。综上，时间复杂度和空间复杂度并无明显变化，若追求极致性能，冒泡排序的时间复杂度系数会变大，插入排序系数会减小，选择排序无明显变化。

  展开

  作者回复: 👍 回答的很好 可以作为标准答案了 同学们把这条顶上去吧

  共 44 条评论

  1823
• 
  Monday

  2018-10-16

  本节从昨天更新到今天，一共前前后后认认真真听了五遍，再到今天晚上花3小时把3个排序算法实现，做了冒泡排序与插入排序的测试实验。随机生成二维数组a[200][10000]和b[200][10000]（a,b数组数据一致），然后在我的机器上分别用冒泡和插入排序算法来排序（a数组冒泡，b数组插入），冒泡排序算法大约 16332ms 才能执行完成，而插入排序只需要 2228ms 左右。 总结一句：听五遍不如敲一遍！

  展开

  共 11 条评论

  409
• 
  德拉

  2018-10-27

  有同学提到的算法过程动态图，可以看看这个https://visualgo.net/

  共 31 条评论

  307
• 
  Smallfly

  2019-03-02

  二刷了下排序，有了一些新的体会。 冒泡、插入、选择排序都有一个共同点，将待排序数列分为已排序和未排序两部分。在未排序的部分中查找一个最值，放到已排序数列的恰当位置。 具体到代码层面，外层循环的变量用于分割已排序和未排序数，内层循环的变量用于在未排序数中查找。从思路上看，这三种算法其实是一样的，所以时间复杂度也相同。

  展开

  共 10 条评论

  216
• 
  靑城

  2018-10-15

  总结 一、排序方法与复杂度归类 （1）几种最经典、最常用的排序方法：冒泡排序、插入排序、选择排序、快速排序、归并排序、计数排序、基数排序、桶排序。 （2）复杂度归类 冒泡排序、插入排序、选择排序 O(n^2) 快速排序、归并排序 O(nlogn) 计数排序、基数排序、桶排序 O(n) 二、如何分析一个“排序算法”？ <1>算法的执行效率 1. 最好、最坏、平均情况时间复杂度。 2. 时间复杂度的系数、常数和低阶。 3. 比较次数，交换（或移动）次数。 <2>排序算法的稳定性 1. 稳定性概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。 2. 稳定性重要性：可针对对象的多种属性进行有优先级的排序。 3. 举例：给电商交易系统中的“订单”排序，按照金额大小对订单数据排序，对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序，排序完成后用稳定排序算法按照订单金额重新排序。 <3>排序算法的内存损耗 原地排序算法：特指空间复杂度是O(1)的排序算法。 三、冒泡排序 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。 稳定性：冒泡排序是稳定的排序算法。 空间复杂度：冒泡排序是原地排序算法。 时间复杂度： 1. 最好情况（满有序度）：O(n)。 2. 最坏情况（满逆序度）：O(n^2)。 3. 平均情况： “有序度”和“逆序度”：对于一个不完全有序的数组，如4，5，6，3，2，1，有序元素对为3个（4，5），（4，6），（5，6），有序度为3，逆序度为12；对于一个完全有序的数组，如1，2，3，4，5，6，有序度就是n*(n-1)/2，也就是15，称作满有序度；逆序度=满有序度-有序度；冒泡排序、插入排序交换（或移动）次数=逆序度。 最好情况下初始有序度为n*(n-1)/2，最坏情况下初始有序度为0，则平均初始有序度为n*(n-1)/4，即交换次数为n*(n-1)/4，因交换次数<比较次数<最坏情况时间复杂度，所以平均时间复杂度为O(n^2)。 四、插入排序 插入排序将数组数据分成已排序区间和未排序区间。初始已排序区间只有一个元素，即数组第一个元素。在未排序区间取出一个元素插入到已排序区间的合适位置，直到未排序区间为空。 空间复杂度：插入排序是原地排序算法。 时间复杂度： 1. 最好情况：O(n)。 2. 最坏情况：O(n^2)。 3. 平均情况：O(n^2)（往数组中插入一个数的平均时间复杂度是O(n)，一共重复n次）。 稳定性：插入排序是稳定的排序算法。 五、选择排序 选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素插入已排序区间的末尾，直到未排序区间为空。 空间复杂度：选择排序是原地排序算法。 时间复杂度：（都是O(n^2)） 1. 最好情况：O(n^2)。 2. 最坏情况：O(n^2)。 3. 平均情况：O(n^2)。 稳定性：选择排序不是稳定的排序算法。 思考 选择排序和插入排序的时间复杂度相同，都是O(n^2)，在实际的软件开发中，为什么我们更倾向于使用插入排序而不是冒泡排序算法呢？ 答：从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个，所以在对相同数组进行排序时，冒泡排序的运行时间理论上要长于插入排序。

  展开

  

  127
• 
  myrabbit

  2018-10-15

  王老师，我发现你文章中的图画的很漂亮，字也写得很漂亮，图文结合的形式对于表达的帮助真的很大！有时候做笔记也可以用此方法，请问你的图文是用什么软件画的？

  作者回复: 不是我画的 大编辑画的

  共 9 条评论

  102
• 
  陈问渔

  2018-11-22

  https://mp.weixin.qq.com/s/HQg3BzzQfJXcWyltsgOfCQ 这里面的图解排序算法，很形象。java实现的代码

  共 1 条评论

  67
• 
  流风之回雪

  2018-11-02

  a[j+1] = value; // 插入数据，这条语句弄了好久才明白，一直以为 j的值最小为0，那么a[j+1]最小就是a[1]，不过这样赋值逻辑上就有问题，后来debug了一下，发现j是可以为-1的，a[j+1]最小为a[0]，这样逻辑上就通了，果然多敲代码才能弄明白勒

  作者回复: 👍钻研精神

  共 15 条评论

  57
• 
  allean

  2018-11-13

  每一次看文章都要至少看三遍，代码实现也至少写三遍，不是追求量，是真的感觉每一次的体会都更加不一样😁

  作者回复: 👍

  共 2 条评论

  54
• 
  姜威

  2018-10-22

  总结： 一、几种经典排序算法及其时间复杂度级别 冒泡、插入、选择 O(n^2) 基于比较 快排、归并 O(nlogn) 基于比较 计数、基数、桶 O(n) 不基于比较 二、如何分析一个排序算法？ 1.学习排序算法的思路？明确原理、掌握实现以及分析性能。 2.如何分析排序算法性能？从执行效率、内存消耗以及稳定性3个方面分析排序算法的性能。 3.执行效率：从以下3个方面来衡量 1）最好情况、最坏情况、平均情况时间复杂度 2）时间复杂度的系数、常数、低阶：排序的数据量比较小时考虑 3）比较次数和交换（或移动）次数 4.内存消耗：通过空间复杂度来衡量。针对排序算法的空间复杂度，引入原地排序的概念，原地排序算法就是指空间复杂度为O(1)的排序算法。 5.稳定性：如果待排序的序列中存在值等的元素，经过排序之后，相等元素之间原有的先后顺序不变，就说明这个排序算法时稳定的。 三、冒泡排序 1.排序原理 1）冒泡排序只会操作相邻的两个数据。 2）对相邻两个数据进行比较，看是否满足大小关系要求，若不满足让它俩互换。 3）一次冒泡会让至少一个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序工作。 4）优化：若某次冒泡不存在数据交换，则说明已经达到完全有序，所以终止冒泡。 2.代码实现（见下一条留言） 3.性能分析 1）执行效率：最小时间复杂度、最大时间复杂度、平均时间复杂度 最小时间复杂度：数据完全有序时，只需进行一次冒泡操作即可，时间复杂度是O(n)。 最大时间复杂度：数据倒序排序时，需要n次冒泡操作，时间复杂度是O(n^2)。 平均时间复杂度：通过有序度和逆序度来分析。 什么是有序度？ 有序度是数组中具有有序关系的元素对的个数，比如[2,4,3,1,5,6]这组数据的有序度就是11，分别是[2,4][2,3][2,5][2,6][4,5][4,6][3,5][3,6][1,5][1,6][5,6]。同理，对于一个倒序数组，比如[6,5,4,3,2,1]，有序度是0；对于一个完全有序的数组，比如[1,2,3,4,5,6]，有序度为n*(n-1)/2，也就是15，完全有序的情况称为满有序度。 什么是逆序度？逆序度的定义正好和有序度相反。核心公式：逆序度=满有序度-有序度。 排序过程，就是有序度增加，逆序度减少的过程，最后达到满有序度，就说明排序完成了。 冒泡排序包含两个操作原子，即比较和交换，每交换一次，有序度加1。不管算法如何改进，交换的次数总是确定的，即逆序度。 对于包含n个数据的数组进行冒泡排序，平均交换次数是多少呢？最坏的情况初始有序度为0，所以要进行n*(n-1)/2交换。最好情况下，初始状态有序度是n*(n-1)/2，就不需要进行交互。我们可以取个中间值n*(n-1)/4，来表示初始有序度既不是很高也不是很低的平均情况。 换句话说，平均情况下，需要n*(n-1)/4次交换操作，比较操作可定比交换操作多，而复杂度的上限是O(n^2)，所以平均情况时间复杂度就是O(n^2)。 以上的分析并不严格，但很实用，这就够了。 2）空间复杂度：每次交换仅需1个临时变量，故空间复杂度为O(1)，是原地排序算法。 3）算法稳定性：如果两个值相等，就不会交换位置，故是稳定排序算法。 四、插入排序 1.算法原理 首先，我们将数组中的数据分为2个区间，即已排序区间和未排序区间。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想就是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间中的元素一直有序。重复这个过程，直到未排序中元素为空，算法结束。 2.代码实现（见下一条留言） 3.性能分析 1）时间复杂度：最好、最坏、平均情况 如果要排序的数组已经是有序的，我们并不需要搬移任何数据。只需要遍历一遍数组即可，所以时间复杂度是O(n)。如果数组是倒序的，每次插入都相当于在数组的第一个位置插入新的数据，所以需要移动大量的数据，因此时间复杂度是O(n^2)。而在一个数组中插入一个元素的平均时间复杂都是O(n)，插入排序需要n次插入，所以平均时间复杂度是O(n^2)。 2）空间复杂度：从上面的代码可以看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是O(1)，是原地排序算法。 3）算法稳定性：在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现的元素的后面，这样就保持原有的顺序不变，所以是稳定的。

  展开

  作者回复: 👍

  

  41
• 
  Jo

  2018-10-15

  冒泡排序的外层循环次数只需要n-1次，此时第1个数字在上一次已经比较过，肯定比第2个小（或大），所以第n次没必要比较了

  共 2 条评论

  28
• 
  WL

  2018-12-07

  把该讲内容总结为几个问题, 大家复习的时候可以先尝试回答这些问题检查自己的掌握程度: 1. 分析排序算法的三个维度都是什么? 2. 从算法执行效率这个维度出发可以从哪三个方面进行衡量? 3. 原地排序的概念是什么? 4. 什么是排序的稳定性, 稳定性排序算法和不稳定排序算法的区别在哪里? 5. 数组的满序度, 有序度, 逆序度概念各是什么? 如何计算? 6. 冒泡排序的实现思路是怎样的, 请实现冒泡排序算法? 7. 冒泡排序的为什么是原地排序算法, 为什么是稳定排序算法, 最好最坏,平均时间复杂度各是多少? 8. 插入排序的实现思路是怎样的, 请实现插入排序算法? 9. 插入排序的为什么是原地排序算法, 为什么是原地排序算法, 最好最坏,平均时间复杂度各是多少? 10. 选择排序的实现思路是怎样的, 请实现选择排序算法? 11. 选择排序的为什么是原地排序算法, 为什么不是稳定排序算法, 最好最坏,平均时间复杂度各是多少? 12. 插入排序比冒泡排序的优势在哪里

  展开

  共 1 条评论

  22
• 
  醉比

  2018-10-15

  大家多思考多吸收吧。。。。我得多吸收一会

  

  20
• 
  王木公

  2019-08-08

  感觉有个问题始终没有解决。前人是如何想出的这些算法？或者说是在怎样的环境下，作者经历了怎样的心路历程想出了这个算法。我认为知道这个很重要，尽管现在学这些算法觉得理所应当，但当时间久了仍然会忘记，尤其是那些细节临界点，人的大脑适合记忆有关联性的东西，这些算法则属于不擅长记忆的创造性内容，如果没有历史那些前提，相信很难根本性掌握。

  作者回复: 很难知道人家是怎么想到的，你要求有点高了，说不定灵机一动就想到了。

  共 10 条评论

  19
• 
  姜威

  2018-10-22

  五、选择排序 1.算法原理 选择排序算法也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，并将其放置到已排序区间的末尾。 2.代码实现（见下一条留言） 3.性能分析 1）时间复杂度：最好、最坏、平均情况 选择排序的最好、最坏、平均情况时间复杂度都是O(n^2)。为什么？因为无论是否有序，每个循环都会完整执行，没得商量。 2）空间复杂度： 选择排序算法空间复杂度是O(1)，是一种原地排序算法。 3）算法稳定性： 选择排序算法不是一种稳定排序算法，比如[5,8,5,2,9]这个数组，使用选择排序算法第一次找到的最小元素就是2，与第一个位置的元素5交换位置，那第一个5和中间的5的顺序就变量，所以就不稳定了。正因如此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。 六、思考 1.冒泡排序和插入排序的时间复杂度都是 O(n^2)，都是原地排序算法，为什么插入排序要比冒泡排序更受欢迎呢？ 冒泡排序移动数据有3条赋值语句，而选择排序的交换位置的只有1条赋值语句，因此在有序度相同的情况下，冒泡排序时间复杂度是选择排序的3倍，所以，选择排序性能更好。 2.如果数据存储在链表中，这三种排序算法还能工作吗？如果能，那相应的时间、空间复杂度又是多少呢？ 代码实现： /** * 冒泡排序 * @param a 待排序数组 * @param n 数组长度 */ public static void bubbleSort(int[] a, int n) { if(n<=0) return ; for (int i = 0; i < n; i++) { //标记一次冒泡是否存在数据交换，若存在，则改为true boolean tag = false; for (int j = 0; j < n-1-i; j++) { if(a[j] > a[j+1]){ int temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; tag = true; } } //若本次冒泡操作未发生数据交换，则终止冒泡操作 if (tag == false) break; } } /** * 插入排序 * @param a 待排序数组 * @param n 表示数组大小 */ public static void insertSort(int[] a, int n) { if(n<=1) return; for(int i=1;i<n;i++){ int value=a[i]; int j=i-1; //找到插入位置 for(;j>0;j--){ if(a[j]>value){ a[j+1]=a[j];//移动数据 } else { break; } } a[j+1]=value;//插入数据 } } /** * 选择排序 * @param a 待排序数组 * @param n 数组长度 */ public static void selectSort(int[] a, int n) { if(n<=0) return; for(int i=0;i<n;i++){ int min=i; for(int j=i;j<n;j++){ if(a[j] < a[min]) min=j; } if(min != i){ int temp=a[i]; a[i]=a[min]; a[min]=temp; } } }

  展开

  作者回复: 👍

  共 5 条评论

  16
• 
  oldman

  2018-10-16

  我用python实现了冒泡排序，插入排序，选择排序。地址如下，欢迎大家一起探讨： 冒泡排序：https://github.com/lipeng1991/testdemo/blob/master/40_bubble_sort.py 插入排序：https://github.com/lipeng1991/testdemo/blob/master/41_insert_sort.py 选择排序： https://github.com/lipeng1991/testdemo/blob/master/42_select_sort.py

  

  16
• 
  ILoveKindness

  2019-06-03

  老师您好，我不是很懂您所置顶的答案中插入排序后要倒置链表的意思，请求解答。

  作者回复: 应该是不需要倒置的。

  共 3 条评论

  14
• 
  峰

  2018-10-15

  三种排序算法不涉及随机读取，所以链表是可以实现的，而且时间复杂度空间空间复杂度和数组一样，O(n*n),O(1).

  共 1 条评论

  12
• 
  安静

  2018-11-09

  每天坐地铁看一节都有点坚持不下来了，加油。

  共 3 条评论

  10
• 
  星

  2018-12-22

  冒泡排序的应该重复n-1次就有序了

  共 1 条评论

  9