冒泡排序

33次阅读

共计 465 个字符,预计需要花费 2 分钟才能阅读完成。

概念

冒泡排序算法是通过不断比较相邻的两个元素,谁大谁往后移动。因此,每一轮遍历都会将最大的元素移到序列的末尾,直到整个序列都有序为止。

代码实现

func bubbleSort(arr []int) []int {n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ {if arr[j] > arr[j+1] {arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
    return arr
}

其中,arr 是待排序的整数序列,n 是序列的长度。在每一轮遍历中,从头到尾依次比较相邻的两个元素,如果前一个元素大于后一个元素,则交换它们的位置。这样一轮下来,最大的元素就被交换到了序列的末尾。通过多轮的遍历比较,最终实现整个序列的排序。

算法分析

最好的情况下,要排序的序列已经有序了,每个只需要进行一次冒泡操作,所以最好的情况下时间复杂度为 O(n)。最坏的情况下,要排序的序列刚好是倒叙的,这个时候冒泡排序的时间复杂度为 O(n^2),其中 n 是待排序序列的长度。它的空间复杂度为 O(1),是一种稳定的排序算法。

正文完
 
dkp
版权声明:本站原创文章,由 dkp 2023-04-03发表,共计465字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。