Kotlin冒泡排序实战技巧

【出自HW面试题】

难度系数：★★★☆☆ 被考察系数：★★★☆☆

题目描述：

给定一个无序整型数组，请用选择排序对数组进行升序排列。

分析与解答：

冒泡排序顾名思义就是整个过程就像气泡一样往上升，单向冒泡排序的基本思想是（假设由小到大排序）：对于给定的n个记录，从第一个记录开始依次对相邻的两个记录进行比较，当前面的记录大于后面的记录时，交换其位置，进行一轮比较和换位后，n个记录中的最大记录将位于第n位；然后对前（n-1）个记录进行第二轮比较；重复该过程直到进行比较的记录只剩下一个时为止。

以数组{36，25，48，12，25，65，43，57}为例（假设要求为升序排列），具体排序过程如下：

初始状态：[36 25 48 12 25 65 43 57]

1趟排序：[25 36 12 25 48 43 57 65]

2趟排序：[25 12 25 36 43 48]57 65

3趟排序：[12 25 25 36 43]48 57 65

4趟排序：[12 25 25 36]43 48 57 65

5趟排序：[12 25 25]36 43 48 57 65

6趟排序：[12 25]25 36 43 48 57 65

7趟排序：[12]25 25 36 43 48 57 65(www.xing528.com)

程序示例如下：

程序的输出结果如下：

0 1 2 3 4 5 6 7 8 9

冒泡排序是一种稳定的排序方法，最好情况下的时间复杂度为O（n），最坏情况下时间复杂度为O（n^2），平均情况下的时间复杂度为O（n^2）。空间复杂度为O（1）。

引申：如何进行双向冒泡排序

答案：双向冒泡排序是冒泡排序的一种优化，它的基本思想是首先将第一个记录的关键字和第二个记录的关键字进行比较，若为“逆序”（即L.r[1].key＞L.r[2].key），则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依次类推，直至第n-1个记录的关键字和第n个记录的关键字比较过为止。这是第一趟冒泡排序，其结果是使得关键字最大的记录被安置到最后一个记录的位置上。

第一趟排序之后进行第二趟冒泡排序，将第n-2个记录的关键字和第n-1个记录的关键字进行比较，若为“逆序”（即L.r[n-1].key＜L.r[n-2].key），则将两个记录交换，然后比较第n-3个记录和n-2个记录的关键字。依次类推，直至第1个记录的关键字和第2个记录的关键字比较过为止。其结果是使得关键字最小的记录被安置到第一个位置上。

再对其余的n-2个记录进行上述同样的操作，其结果是使关键字次大的记录被安置到第n-1个记录的位置，使关键字次小的记录被安置到第2个记录的位置。

通常，第i趟冒泡排序是：若i为奇数，则从L.r[i/2+1]～L.r[n-i/2]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最大的记录被交换到第n-i/2的位置上；若i为偶数，则从L.r[n-i/2]～L.r[i/2]依次比较相邻两个记录的关键字，并在“逆序”时交换相邻记录，其结果是这n-i+1个记录中关键字最小的记录被交换到第i/2的位置上。整个排序过程需要进行K（1≤K＜n）趟冒泡排序，同样判别冒泡排序结束的条件仍然是“在一趟排序过程中没有进行过交换记录的操作”。

程序示例如下：

程序的输出结果如下：

0 1 2 3 4 5 6 7 8 9

算法性能分析：

双向冒泡排序跟普通冒泡排序的时间复杂度相同。但是，双向冒泡排序能解决普通冒泡排序的乌龟问题。乌龟问题是指假设需要将序列按照升序序列排序，序列中的较小的数字又大量存在于序列的尾部，这样会让小数字向前移动得很缓慢。