简述
冒泡排序通过反复遍历要排序的列表，比较每对相邻项，并以升序或降序的方式交换它们。重复操作列表，知道不需要交换为止。
复杂度
|
|
|
|
|
|
| 名称 |
最好 |
平均 |
最差 |
空间 |
稳定性 |
| 冒泡排序 |
n |
n2 |
n2 |
1 |
是 |
理解
- 冒泡排序，有
n个数字，就要进行n次大循环
- 每次大循环，会找到所有数里面的最大或最小的数并放到正确的位置上
- 大循环里面小循环，本质上就是从下标
0到当前未处理完成的最大下标之间进行循环，任务是找到最大或最小的目标，当找到了，当前未处理完成的最大下标的值就会相应缩小
length-i-1 的本质应该是length-1-i
length-1代表的是一组待处理数组的最大下标- 这个最大下标之所以要
-i，是因为完成了i次大循环，代表着有i个数字已经位于正确的位置，它不需要再被处理
初步实现
|
|
void BubbleSort(int array[],int length) { for (int i = 0; i < length - 1; ++i) { for (int j = 0; j < length - i - 1; ++j) { int temp = 0; if (array[j] > array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } } |
优化版1.0
经过一定次数的排序，数组可能已经处于完成排序的状态，但是，冒泡排序的流程还没走完，所以它还会继续排序，直到走完流程。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
void BubbleSort(int array[],int length) { for(int i = 0;i < length - 1; ++i) { bool isSorted = true; for(int j = 0;j < length - i -1; ++j) { int temp = 0; if(array[j] > array[j+1]) { temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; isSorted = false;//因为有元素发生了交换，所以不是有序的 } } if(isSorted) break; } } |
优化版2.0
存在一种情况，数组在排序之前，有部分区间就是有序的序列。针对这种现象优化。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
void BubbleSort(int array[],int length) { //记录最后一次交换的位置 int lastExchangeIndex = 0; //无序数列的边界 int sortBorder = length - 1; for(int i = 0;i < length - 1; ++i) { //有序标记 bool isSorted = true; for(int j = 0;j < sortBorder; ++j) { int temp = 0; if(array[j] < array[j+1]) { temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; //因为有元素交换，所以是无序的 isSorted = false; //更新最后一次交换元素的位置 lastExchangeIndex = j; } } sortBorder = lastExchangeIndex; if(isSorted) break; } } |
鸡尾酒排序
简述
鸡尾酒排序，是基于冒泡排序的一种升级排序法。
区别
- 冒泡排序
- 每一轮都是从左到右来比较元素，进行单向的位置交换的。
- 鸡尾酒排序
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
void BubbleSort(int array[],int length) { int temp = 0; for(int i = 0;i < length/2; ++i) { //有序标记 bool isSorted = true; //奇数轮，从左向右比较和交换 for(int j = 1;j < length -i -1; ++j) { if(array[j] > array[j+1]) { temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; //有元素交换，所以不是有序的，进行标记 isSorted = false; } } if(isSorted) break; //偶数轮之前，重置标记 isSorted = true; //偶数轮，从右往左比较和交换 for(int j = length -i -1;j > i; --j) { if(array[j] < array[j-1]) { temp = array[j]; array[j] = array[j-1]; array[j-1] = temp; //有元素交换，所以不是有序的，进行标记 isSorted = false; } } if(isSorted) break; } } |
