冒泡排序是最基础的排序算法, 每一轮的冒泡都是把最小的或者最大的冒到一端, 是一种稳定的排序算法, 时间复杂度为 O(n^2)
原始的冒泡排序
- // 冒泡排序
- void BubbleSort1(int* arr, int size)
- {
- int i = 0, j = 0;
- for (i = 0; i <size - 1; i++)// 一共要排序 size-1 次
- {
- for (j = 0; j < size - 1 - i; j++)// 选出该趟排序的最大值往后移动
- {
- if (arr[j]> arr[j + 1])
- {
- int tmp = arr[j];
- arr[j] = arr[j + 1];
- arr[j + 1] = tmp;
- }
- }
- }
- }
优化一: 优化外层循环
在某一次外层循环发现没有发生交换时说明冒泡已经结束, 因为接下来的循环区间都比这一次的要小, 所以接下来的冒泡就无意义, 则提前退出循环. 优化后的冒泡排序最好时间复杂度是 O(n), 最坏时间复杂度是 O(n2), 平均时间复杂度是 O(n2)
- // 冒泡排序优化 1
- void BubbleSort2(int* arr, int size)
- {
- int i = 0, j = 0;
- for (i = 0; i <size - 1; i++)// 一共要排序 size-1 次
- {
- // 每次遍历标志位都要先置为 0, 才能判断后面的元素是否发生了交换
- int flag = 0;
- for (j = 0; j < size - 1 - i; j++)// 选出该趟排序的最大值往后移动
- {
- if (arr[j]> arr[j + 1])
- {
- int tmp = arr[j];
- arr[j] = arr[j + 1];
- arr[j + 1] = tmp;
- flag = 1;// 只要有发生了交换, flag 就置为 1
- }
- }
- // 判断标志位是否为 0, 如果为 0, 说明后面的元素已经有序, 就直接 return
- if (flag == 0)
- {
- return;
- }
- }
- }
优化 2: 优化内层循环
在每趟扫描中, 记住最后一次交换发生的位置 lastExchange,(该位置之后的相邻记录均已有序, 因为正在冒的数是当前最小的, 如果该数停止往上冒了, 且后面没有冒泡的操作了, 说明后面的数比这个数都小, 且已经排好序). 下一趟排序开始时, R[1..lastExchange-1] 是无序区, R[lastExchange..n] 是有序区. 这样, 一趟排序可能使当前无序区扩充多个记录, 因此记住最后一次交换发生的位置 lastExchange, 从而减少排序的趟数.
- void BubbleSort3(int* arr, int size)
- {
- int i = 0, j = 0;
- int k = size - 1,pos = 0;//pos 变量用来标记循环里最后一次交换的位置
- for (i = 0; i <size - 1; i++)// 一共要排序 size-1 次
- {
- // 每次遍历标志位都要先置为 0, 才能判断后面的元素是否发生了交换
- int flag = 0;
- for (j = 0; j <k; j++)// 选出该趟排序的最大值往后移动
- {
- if (arr[j]> arr[j + 1])
- {
- int tmp = arr[j];
- arr[j] = arr[j + 1];
- arr[j + 1] = tmp;
- flag = 1;// 只要有发生了交换, flag 就置为 1
- pos = j;// 循环里最后一次交换的位置 j 赋给 pos
- }
- }
- k = pos;
- // 判断标志位是否为 0, 如果为 0, 说明后面的元素已经有序, 就直接 return
- if (flag == 0)
- {
- return;
- }
- }
- }
来源: http://www.jianshu.com/p/1a19507766aa