冒泡排序
算法步骤
以升序排序为例：
- 比较相邻元素，如果前面的比后面的元素大，则两元素交换位置
- 对每一对相邻元素进行比较，大的放后，这样最后的元素将是最大的元素
- 对越来越少的混乱元素重复上述步骤（最后的元素已经有序，不需比较），直到没有元素需要交换位置
动图演示
实现代码
void BubbleSort(int* nums, int numsSize) { for (int i = 0; i < numsSize - 1; i++) { for (int j = 0; j < numsSize - 1 - i; j++) { if (nums[j] > nums[j + 1]) { Swap(&nums[j], &nums[j + 1]); //Swap()函数需要自己实现 } } } }
稍加优化
- 如果在一趟遍历中未发生交换，就可以说明数组已经有序
- 因此我们可以设计一个标记flag，每次外层循环开始时都初始化为1，若内层循环发生了交换就将其改为0
- 因此如果内层循环结束后flag仍为1，就说明这一次遍历未发生交换，即数组已经有序
优化后的代码
void BubbleSort(int* nums, int numsSize) { for (int i = 0; i < numsSize - 1; i++) { int flag = 1; for (int j = 0; j < numsSize - 1 - i; j++) { if (nums[j] > nums[j + 1]) { Swap(&nums[j], &nums[j + 1]); flag = 0; } } if (flag) break; } }
时间复杂度
- 易得冒泡排序的时间复杂度为O(N2)
