动画：面试官问我插入排序和冒泡排序哪个更牛逼？

杨利霞

动画：面试官问我插入排序和冒泡排序哪个更牛逼？

写在前边

$ S2 k" R* r3 p. t& W& R
/ M% B9 Z. ^6 T( T# j/ l排序对于每个开发者来讲，都多多少少知道几个经典的排序算法，比如我们之前以动画形式分享的冒泡排序，也包括今天要分享的插入排序。还有一些其他经典的排序，小鹿整理的共有十种是面试常问到的，冒泡排序、插入排序、希尔排序、选择排序、归并排序、快速排序、堆排序、桶排序、计数排序、基数排序。

. q* N! M" C7 Z1 g& Z, j虽然我们基本知道了这些排序算法，但是在实际项目开发以及面试中往往出乎我们所料。在面试中，经常会被问到各种排序之间的比较；在实际项目中，往往排序的数据不是我们所练习的整数。
0 N/ _8 ]& ?& n! k6 t+ a
那么今天我们来学习一下，插入排序比我们之前讲的冒泡排序有什么区别呢？面试官问我们，我们如何回答完整呢？
$ I, y: Z( C1 e- o
0 T" L5 I1 u/ N, q& i! @, T思维导图


/ E3 P! Y/ g7 J$ E- f& h

1

如何分析一个排序算法？
. n+ h2 w" g8 R5 I- S
- s: _/ J- D. I7 T9 P之前写的一篇很详细的文章。
  Z  n& g+ T" [
0 `2 P, ^4 o2 f2 Z! I9 n2 _佩奇学编程 | 复杂度分析原来这么简单

分析排序算法已经成为我们衡量一个算法优良的重要标准，从以下三个方面入手。
  U! E% I( q4 ~6 |7 W/ s( V8 i
1.1 时间效率

这里所谓的实践效率就是时间复杂度，相信大家对于时间复杂度并不陌生。

* T5 L6 c) c+ G; S( k$ i7 e复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。
+ S1 Q& R. s. h. E" X; R
对于时间复杂度的分析，要把最好时间复杂度、最坏时间复杂度、平均时间复杂度分析出来，分别对应了排序算法的最好排序情况、最坏排序情况以及平均排序效率。
, F% H0 ]$ h; d  t8 ~0 j; i5 e2 L- C
9 ~/ b+ ~/ ~2 S2 B1.2 空间消耗

所谓的空间消耗对应的是空间复杂度，在排序算法中需要开辟的额外内存空间是多少。如果空间复杂度为 O(1)，此时该排序叫做原地排序。

注意：是额外的内存空间，存储排序数据消耗的空间不计。
) a+ T, x3 C! O. d8 P6 L7 W
0 X0 y+ n1 V0 i% C1.3 稳定性
0 I' k) @5 _: G: d, C% b+ Z# D
1 u. j+ F4 r1 s$ }算法的稳定性虽然我们之前接触的很少，但是稳定性也是衡量一个排序算法的重要标准。什么是稳定排序呢？比如有一组有重复待排序的数据，排序前后，重复的数据顺序不变，此时该排序为稳定排序。否则，叫做不稳定排序。它在实际应用中非常重要的，今天我们就不多说，以后会慢慢分享到。
, ^7 w# q: G/ z! z
- _/ W1 Q  V; D1 m; N2

4 [- {# Q) E2 ?什么是插入排序？

顾名思义，插入排序就是通过插入的方式来排序呗，最经典的就是打斗地主，可以将打乱的扑克牌作为未排序区间，手中已经排好序的作为排序区间。每次我们摸牌的过程，就是从未排序区间，通过插入的方式，插入到已排序区间。那么这个过程就称为插入排序。


# B" P& @6 q- `4 }
3

如何实现插入排序？
2 J/ s% h9 \& n, v" v. n' I. {8 D
6 H0 Y( K% B, {8 d8 f上述插入排序的概念我们已经理解了，那么给你一组数据，如何来进行插入排序呢？



- y) a/ U$ D0 X( G/ i2 V$ q首先我们要将数据划分为两个区间，已排序区间和未排序区间。

) @5 [3 b2 Q* O& k3 l3 s- d
8 w" O. ~4 T9 u

6 }" O0 D& P5 }" N# r& C; {
我们从未排序区间取出数据和已排序区间的数据进行比较，如果小于已排序区间的数据，那我们就交换数据。
% v& G" H* R9 E" {; V' \
3 ]" `* v7 [* s; E4 Z

# @, [  o0 w& y+ v

4 F' X# `* [6 A如果交换到已排序区间数据不在大于插入的数据，然后将元素插入进去。
$ @6 k9 ]0 [$ L* ?: B' H8 }
" I$ F+ n* k* E4 ]; C2 f- ~
" h, O- z# [0 E* q

6 ~# T3 E3 q: |: m0 U
; {& T4 k1 S5 Y" u& _  ]最后我们看一下总的插入排序动画和代码实现。
, P% H& e) @) Z9 `# e% }4 r


; u" S0 O% q& Z4

插入排序的性能
! E  l) I! P$ R* B+ Z8 W, E2 Q  r
我们通过上边的对插入排序的拆分讲解和动画以及代码实现，想必面试官让你手写一个插入排序可以轻轻松松写出。但是我们掌握的插入排序知识还往往不够，我们在实际项目中，还要考虑插入排序的性能怎么样？因为才能更好的选择适当排序应用到项目中去。
. n# W$ [3 [, F% e) M  C
, B" u" K# U6 a7 ]0 W- }. _% j4.1 插入排序的稳定性

4 f6 @3 U* Q5 L9 H6 b& N* u再插入排序中，如果存在重复数据的话，前边的元素再插入的过程永远在第二个重复数据的前边，所以插入排序后的重复数据前后顺序不变，所以插入排序是稳定排序算法。

4.2 插入排序的空间消耗
0 Q# H2 W/ Y5 `8 i
我们可以发现，插入排序的移动方式，需要消耗常量级的额外内存空间存储，也就是代码中的 temp，所以时间复杂度为 O(1),我们上边讲到，空间复杂度为O(1)的是原地排序算法。
, A6 ]( \7 p$ X+ P2 o/ o. u
4.3 插入排序的时间效率

插入排序的最好情况就是不需要搬移任何数据，从头到尾寻找插入数据，每次只比较一次即可，即一组有序数据，所以最好时间复杂度为O(n)。
0 d* n+ }% l" V1 c1 |' \
+ w" l* K$ r" K# W% M如果一组数据正好是倒序输出，那么每次都需要比较移动所有数据，每次移动时 n，n 个数据时间复杂度为O(n2)。
6 E  x" {' e5 @3 h3 s  C; e
对于插入排序的平均时间复杂度，每次插入都要移动数据，插入 n 次，所以平均时间复杂度为 O(n2)。
, u7 d3 g) r$ V0 f% B. U
( A. P' n% ^' y7 c5
, ?- l! j, G: L3 X! Z
, o$ l0 o; t! N/ F! X小结
% K/ {& N: E3 S5 `
我们学完了今天的插入排序之后，我们回到最初的面试官问题上。插入排序和冒泡排序哪个更好呢？

1 w4 Q" b- w% W! A. O% s9 k8 ]! V8 a我们现在元素移动次数上进行分析，如果一组无序的数据通过冒泡排序排好序之后，它的交换次数是这种数据的逆序度；对于插入排序来说也是一样的，移动次数上都是原本数据的逆序度。
0 e% m+ r( V( D' @; U6 c
4 O, y$ l' T2 a( ]1 t, \' C元素的移动次数是相同的，那我们接下来看看元素的交换次数。从代码上分析可以明显看出，冒泡排序的一次交换需要三行代码，而插入排序的交换却需要一行，所以总的交换次数冒泡排序大于插入排序。

有小伙伴会问，这两行的差别有那么大吗？移动一次，我们可以不计较，如果数据很多，想想下，两者的效率差别很轻易的就比较出来了。

7 A4 V4 n% [7 `0 ^虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的，但是我们实际使用中还是优先选择插入排序。
8 a) Q* i: m9 Y9 S) [! o# z
对于插入排序还是可以优化的，对了，没错，就是希尔排序，我们在这不多分开写，后期会继续更新。
/ v0 e/ U0 p/ ~% p————————————————
5 m% S3 S* d8 N8 s版权声明：本文为CSDN博主「胡鹏程的博客」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" G' |" j) ?3 {3 N( S: R原文链接：https://blog.csdn.net/lyshark_lyshark/article/details/126792708
, j- ]2 J  f1 c$ a6 r% N

# s0 u. X& G% V; l- ]$ }