时间复杂度恒为 $O(n^2)的排序算法
时间: 2023-07-24 07:48:01 浏览: 60
常见的时间复杂度恒为 $O(n^2)$ 的排序算法有冒泡排序、插入排序和选择排序。
1. 冒泡排序
冒泡排序是一种简单直观的排序算法,其基本思想是不断交换相邻逆序的元素,将待排序序列中较大的数往后移动,较小的数往前移动。具体步骤如下:
1. 从头到尾遍历待排序序列,比较相邻两个元素的大小,如果它们的顺序错误,则交换它们的位置。
2. 重复执行上述操作,直到整个序列有序为止。
冒泡排序的时间复杂度为 $O(n^2)$,空间复杂度为 $O(1)$,是一种稳定排序算法。
2. 插入排序
插入排序的基本思想是将待排序的元素分为已排序区间和未排序区间。初始时,已排序区间只有一个元素,即第一个元素。每次从未排序区间中取出一个元素,插入到已排序区间的合适位置,直到未排序区间中元素全部排完为止。具体步骤如下:
1. 从第二个元素开始,依次将每个元素插入到它前面已排好序的序列中的正确位置。
2. 重复执行上述操作,直到所有元素均排序完成。
插入排序的时间复杂度为 $O(n^2)$,空间复杂度为 $O(1)$,是一种稳定排序算法。
3. 选择排序
选择排序的基本思路是每次从待排序序列中选择最小(或最大)的元素,放到序列的起始位置,然后再从剩余未排序元素中继续寻找最小(或最大)的元素,放到已排序序列的末尾。以此类推,直到所有元素均排序完成。具体步骤如下:
1. 在未排序序列中找到最小(或最大)元素,存放到排序序列的起始位置。
2. 从剩余未排序的元素中继续寻找最小(或最大)元素,放到已排序序列的末尾。
3. 重复执行上述操作,直到所有元素均排序完成。
选择排序的时间复杂度为 $O(n^2)$,空间复杂度为 $O(1)$,是一种不稳定排序算法。