数据结构与算法：冒泡排序

如何分析排序算法（时间复杂度、空间复杂度、稳定性）
1、排序算法的执行效率

• 最好情况，最坏情况，平均情况时间复杂度（有序和无序的数据，对时间复杂度有影响）
  冒泡排序最好情况数据已经有序，时间复杂度为O(n)；最坏情况数据是倒序，要进行n次冒泡，时间复杂度为O(n2)；
  平均情况下，时间复杂度为O(n2)。
  
• 时间复杂度的系数、常数、低阶
• 比较次数和交换（或移动）次数
  2、排序算法的内存消耗
  原地排序算法：特指空间复杂度是O(1)的排序算法。冒泡、插入和选择排序都为原地排序算法
  3、排序算法的稳定性
  稳定性是指，待排序元素中有相同元素，排序后相同元素之间原有的顺序不变

冒泡排序

python实现冒泡排序：

def bubble_sort(list1):
    for i in range(len(list1)):
        for j in range(i+1,len(list1)):
            if list[i] > list[j]:
                list[i], list[j] = list[j], list[i]


if __name__ == '__main__':
    n = [1, 4, 8, 9, 3, 5, 2, 7, 4]
    bubble_sort(n)

有序度和逆序度
**有序度：**有序元素对的个数

**满有序度：*完全有序的数组有序度，比如1，2，3，4，5，6 有序度为n(n-1)/2 ，有序度为15
**逆序度：**逆序元素对个数。逆序度=满有序度-有序度。
冒泡排序包含两个操作原子：交换和比较。每交换一次，有序度＋1，总交换次数为逆序度