冒泡排序是一种基础的排序算法，其算法思想是重复地遍历要排序的数组，每次比较相邻两个元素，如果顺序错误就交换位置，直到没有任何一对元素需要交换为止。以下是冒泡排序的详细讲解：
- 算法步骤
- 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
- 对每一对相邻元素做同样的工作，从开始的第一对到结尾的最后一对。这步完成后，最后的元素会是最大的数。
- 针对所有的元素重复以上步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
- 算法分析
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
- 稳定性：稳定排序
3.代码示例
void bubbleSort(int arr[], int n) {
int i, j;
for (i = 0; i < n-1; i++) {
// Last i elements are already in place
for (j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
}
}
发表评论