思路
- 确定第1位：从后向前两两比较，把较小的放在前，较大的放在后。结束后，最小的已经在第1位了。
- 确定第2位：从后向前两两比较，把较小的放在前，较大的放在后。直到第2位。结束后，第2小的已经在第2位了。
- ……
- 确定第n-1位：……
平均时间复杂度：O(n2)
实现
void bubble_sort(const int* a, int length){
bool flag;
for(int i = 0; i < length-1; i++){
flag = false;
for(int j = length-1; j > i; j--){
if(a[j] < a[j-1]){
swap(a[j], a[j-1]);
flag = true;
}
}
if(!flag) return;
}
}
关键点注释
- 2层遍历嵌套。
- 外遍历从0到length - 1，即：“思路”中确定第1位～确定n - 1位。
- 内遍历从length - 1到i，即“思路”中从后向前。
- 遍历体为“两两比较，把较小的放在前，较大的放在后”。
- flag用于记录一次遍历中是否进行了交换。如果没有进行交换，说明已经排好了，可以直接结束。
