冒泡排序的改进

谁借莪１个温暖的怀抱￠ 2022-08-07 05:52 113阅读 0赞

# 通常的冒泡排序    #

假设按照升序排序。

排序思想：

第一趟排序：首先将第一个元素和第二个元素比较，若第一个元素大于第二个元素，交换它们，然后比较第二个元素和第三个元素，……，知道第n-1个元素和第n个元素比较， 第一趟排序将最大的元素放在了最后一位（第n位）；

第二趟排序：对前n-1个元素元素执行同样操作，其结果是将第二大的元素放在了数组第n - 1的位置上。

第i趟排序：依次比较前n - i + 1个元素，将这n - i + 1个元素中最大的元素放到第n - i + 1位上。

设数组大小为n；比较相邻的两个数，如果第一个大于第二个，则交换两个数据；这样，第一个排序后，比较了n-1次，最大的数在数组末尾。然后n = n- 1，在n不为0情况下继续排序，否则排序完成。

void bubble_sort1(int a[], int size) {
    	int i;
    	for (i = 0; i < size; ++i) {
    		int j;
    		for (j = 1; j < size - i; ++j) {
    			if (a[j - 1] > a[j]) {
    				int temp = a[j - 1];
    				a[j - 1] = a[j];
    				a[j] =  temp;
    			}
    		}
    	}
    }

# 改进版本 #

设置一个标记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;
    }

该排序算法用到了交换两个数的函数。参考[这里][Link 1]查看面试题“不借助其他变量，交换两个数”。

[Link 1]: http://blog.csdn.net/u013074465/article/details/44342629