设置一个标记flag,如果某次排序发生了交换flag为真;否则flag为假,排序结束。排序结束的标志是某趟排序没有发生交换。那么排序所需要的趟数k范围是1 <= k < n。若初始序列为有序的,则只需要一趟排序,在排序过程中进行n -1 次的关键字的比较,且不需要移动元素。若初始序列为逆序的,则需要n - 1趟排序,共需要n(n - 1) / 2次比较,并作等数量级的元素移动。
void bubble_sort2(int a[], int size) {
int k;
bool flag;
k = size;
flag = true;
while (flag) {
flag = false;
int j;
for (j = 1; j < k; j++) {
int temp;
if (a[j - 1] > a[j]) {
temp = a[j - 1];
a[j - 1] = a[j];
a[j] = temp;
flag = true;
}
}
k--;
}
}
int main() {
int a[] = {9,4,2,6,1, 1, 1};
cout << sizeof(a) / sizeof(int) << endl;
bubble_sort1(a, sizeof(a) / sizeof(int));
//bubble_sort1(a, sizeof(a) / sizeof(int));
int i;
for (i = 0; i < sizeof(a) / sizeof(int); ++i)
cout << a[i] << " ";
cout << endl;
return 0;
}
该排序算法用到了交换两个数的函数。参考这里查看面试题“不借助其他变量,交换两个数”。