小码农

趣味编程-面向每个人的创意编程

冒泡排序是一种基础的排序算法,其算法思想是重复地遍历要排序的数组,每次比较相邻两个元素,如果顺序错误就交换位置,直到没有任何一对元素需要交换为止。以下是冒泡排序的详细讲解:

  1. 算法步骤
  • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  • 对每一对相邻元素做同样的工作,从开始的第一对到结尾的最后一对。这步完成后,最后的元素会是最大的数。
  • 针对所有的元素重复以上步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
  1. 算法分析
  • 时间复杂度: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]);
        }
    }
}
发表评论