排序算法分析的方方面面
- 排序算法的执行效率
1.最好、最坏、平均情况时间复杂度；
2.时间复杂度的系数、常数、低阶；
3.比较次数和交换（或移动）次数。 - 排序算法的内存消耗
可用空间复杂度衡量，原地排序（Sorted in place）特指空间复杂度是O(1)的排序算法。 - 排序算法的稳定性
如1(A),2,3,4,5,1(B)，排序后保持1(A),1(B),2,3,4,5，即1(A)仍在1(B)左边，那这个就是稳定的排序算法；反之为不稳定的排序算法。
有序度、逆序度、满有序度
- 有序度是数组中具有有序关系的元素对的个数。
如2,1,3,4按从小到大排序，有序元素对为(1,3)，(1,4)，(3,4)，(2,3)，(2,4)，有序度为5，同理，逆序元素对的个数为(2,1)，逆序度为1。 - 满有序度就是有序度+逆序度，也就是n!=n*(n-1)/2。
排序的过程就是增加有序度减少逆序度的过程，直到达到满有序度，排序完成。
冒泡排序时间复杂度分析
- 冒泡排序包含2个操作原子，比较和交换。每交换一次，有序度加1。不管算法怎么改进，交换次数总是确定的，即为“逆序度”。
- 对包含n个数据的数组进行冒泡排序，最坏情况下初始状态有序度是0，需要进行n*(n-1)/2次交换。最好情况下，出事状态有序度是n*(n-1)/2，无需进行交换。取中间值n*(n-1)/4，表示初始有序的的平均情况。也就是平均情况下需要n*(n-1)/4次交换操作，比较操作肯定要比交换操作多，而这个复杂度的上限是O(n²)，所以可粗略地认为冒泡排序平均情况下时间复杂度是O(n²)。
