Question

冒泡排序

Answer 1

    现在有一个数组，共有六个元素，{1,4,7,2,3,5}，要求把他们按照从小到大的顺序排列，每一趟排序将较大的值交换到最右边，下面进行排序过程分析。

    第一趟比较结束，得到{1,4,2,3,5,7}，共比较5次；

    第二趟比较结束，得到{1,2,3,4,5,7}，共比较4次；

    第三趟比较结束，得到{1,2,3,4,5,7}，共比较3次；

    第四趟比较结束，得到{1,2,3,4,5,7}，共比较2次；

    第五趟比较结束，得到{1,2,3,4,5,7}，共比较1次；
    至此，已经无法再进行比较，该序列已经有序，冒泡排序结束。由上述过程可知，冒泡排序的本质就是元素之间的交换，共6个数，执行5趟排序比较，若有n个数，则是执行n-1趟比较，每一趟从左到右比较相邻的两个数，如果大的数在左边则进行交换，在每一趟比较结束后，该趟最大的数在最右边。
    时间复杂度分析：第一趟比较，是n个数进行比较；第二趟比较，是n-1个数进行比较；第三趟比较，是n-2个数进行比较......所以这是一个等差数列求和最后得O(N2)（2是N的上标值，因为不支持latex）。