|
|
知识路径: > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 > 简单排序 >
|
相关知识点:3个
|
|
|
|
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(n2)。排序过程中仅需要一个元素的辅助空间用于元素的交换,空间复杂度为O(1)。
|
|
|
|
|
|
|
|
|
|
|
|