冒泡排序

遍历一组数字以相邻交换的方式找到这一组数字的最值的排序方式
这里讨论的是从小到大的排序

冒泡排序曲线

给出定义

假设：在完全均匀且随机打乱一组数字的情况下进行冒泡排序，将数字的大小以柱的高度表示，在不同的时间下会生成不同的形状。假设这一形状可以用一个近似函数来表示，这个函数的曲线就是冒泡排序曲线。

建立模型

为方便表示：我们设置这张图片的长和宽均为单位1，给定变量时间t，当t=0时，为随机打乱的状态；当t=1时，为排序完成的状态

t=0

t=1

$f(x, t)=\left\{\begin{array}{ll}x & x>1-t \\???& x \leq 1-t\end{array}\right.$

显然，图像分为两部分：
当x大于1-t的时候，函数值为其本身。
我们需要推导，当x小于1-t的时候的函数值。

所以第一部分的曲线呢？

推导曲线

关键在于

• 因为冒泡排序每一次遍历只改变相邻元素，前n项元素在经过相同次数的遍历的情况下的形状是不变的，由于我们设置了单位宽–>这一部分的曲线只随t的增长而横向拉伸
• 
• 数据是完全均匀且随机打乱的，所以即使它们的数据不完全相同，它们形成的弧线也都是相同的–>在数据量不同的情况下，取前n项元素在拉伸前有相同的形状
  • 

推导过程

1. 我们在t的两个不同值处绘制函数，记为$f(x, a)$和$f(x, b)$
2. 为了利用先前推导出的性质，我们将图像t较大的一方进行拉伸
   
3. 由于函数是连续的，所以我们可以知道该点坐标为$(1-a,1-a)$–>$f(1-a,a)=1-a$
4. 令t从1到0呈线性变化，我们得到了推导式$f(1-a,a)=1-a$
5. 代入到$f(x\cdot \frac{b}{a},b)$中，在进行压缩，就得到了函数图像。
   
   推导过程如下

$在f(x\cdot \frac{b}{a}, b)=f(x,a),x\le1-a中， 令 x = 1-a,则有：$

$f((1-a)\cdot \frac{b}{a}, b)=f(1-a,a)=1-a.$

$令x=(1-a)\cdot \frac{b}{a},t=b，则有： a=\frac{t}{x+t}$

$所以f(x, t)=\left\{\begin{array}{ll}x & x>1-t \\\frac{x}{x+t} & x \leq 1-t\end{array}\right.$