假设有8个记录，它的初始关键字序列为{57382914}用冒泡排序对它进行排序，第5次排序结..

n个记录进行冒泡排序的方法是：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则交换两个记录的值，然后比较第二个记录和第三个记录的关键字，以此类推，直至第n-1个记录和第n个记录的关键字比较完为止。上述过程称作一趟冒泡排序，其结果是关键字最大的记录被交换到第n个位置。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是关键字次大的记录被交换到第n-1个位置。当进行完第n-1趟时，所有记录有序排列。

【算法】冒泡排序算法。

冒泡排序法在最好情况下（待排序列已按关键码有序）只需作1趟排序，元素的比较次数为n-1且不需要交换元素，因此总比较次数为n-1次，总交换次数为0次。在最坏情况下（元素已经逆序排列），进行第i趟排序时，最大的i-1个元素已经排好序，其余的n-（i-1）个元素需要进行n-i次比较和n-i次交换，因此总比较次数为

，总交换次数为

。

由此，冒泡排序是一种稳定的排序方法，其时间复杂度为O（n²）。排序过程中仅需要一个元素的辅助空间用于元素的交换，空间复杂度为O（1）。

排序

假设含n个记录的文件内容为｛R₁，R₂，…，R_n｝，其相应的关键字为｛k₁，k₂，…，k_n｝。经过排序确定一种排列｛R_j₁，R_j₂，…，R_jn｝，使得它们的关键字满足如下递增（或递减）关系：k_j₁≤k_j₂≤…≤k_jn（或k_j₁≥k_j₂≥…≥k_jn）。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5