排序算法 —— 冒泡排序

目录

1.冒泡排序的思想

2.冒泡排序的实现

3.冒泡排序的总结

---

1.冒泡排序的思想

冒泡排序的思想就是在待排序序列中依次比较相邻两个元素，将大的or小的元素往后挪，每一趟都能保证将至少一个元素挪动到正确的位置，然后在待排序序列中重复该过程。

2.冒泡排序的实现

代码如下：

void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++)  //枚举结束位置和最后一个元素位置的差值 {for (int i = 1; i < n-j; i++) //依次枚举相邻的两个元素 {if (a[i - 1] > a[i]){swap(&a[i - 1], &a[i]);}}}
}

可以看出，冒泡排序十分的暴力，枚举的次数在最好和最坏情况下都是一个等差数列，但是，有些比较是没有必要的。比如：当某一趟排序中没有发生交换的时候，说明序列有序了，不需要再比较了，所以我们可以对代码进行优化。

优化之后的代码如下：

• 我们可以增加一个标记位，标记是否发生了交换。

#include <stdio.h>void swap(int* p1, int *p2)
{int t = *p1;*p1 = *p2;*p2 = t;
}void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++)  //枚举结束位置和最后一个元素位置的差值 {int flag = 0;for (int i = 1; i < n-j; i++) //依次枚举相邻的两个元素 {if (a[i - 1] > a[i]){swap(&a[i - 1], &a[i]);flag = 1;}}if (flag == 0){break;}}
}int main()
{int nums[] = {5,4,2,6,3,1,8,9,7};BubbleSort(nums, 10);int i = 0;while(i < sizeof(nums)/sizeof(int)){printf("%d ",nums[i]);i++;}return 0;
}

3.冒泡排序的总结

• 时间复杂度：O(N^2)。
• 空间复杂度：O(1)。
• 稳定性：稳定 。