Question

插入排序和冒泡排序

Answer 1

在一个有序的数组中插入一个数据，要求该数据插入后数组仍然有序。在插入排序中有序的数组就是指已经排好序的区间，新增的数据就是从未排序的区间中取出一条数据插入即可。

每一次都是从数组中的第一个元素跟下一个元素做对比，然后将最大或最小的数据放到最后。最终产生有序或倒叙的排序结果。

有序度是指数组中两个数组元素之前是有序的个数。如数组 C ： 2，4，3，1，2，7
有序的元素为： （2,4) (2,3) (2,2) (2,7) (4,7) (3,7) (1,2) (1,7) (2,7) 。因此数组C目前的有序度为9。排好序的数据元素个数叫做满有序度，数组C的满有序度为 15 公式n (n-1)/2*，逆序度的定义正好跟有序度相反.

冒泡和插入排序的实质就是数据在交换，每交换一次数据有序度就会加1.无论怎么交换，交换的次数是不变的。也就是逆序度不变。
因此冒泡排序和插入排序交换次数都是一样的，但是冒泡排序在交换数据时，需要三个赋值操作，而插入排序只有一个赋值操作。可以看出来冒泡排序比插入排序更加耗时。

关于插入排序目前还有一种更高效的排序方式，时间复杂都能够提升到，可以使得性能提升至O(n log2 n)。
希尔排序 可以研究一下