C语言-冒泡排序（数据结构）

要不断坚持啊

2123人浏览 · 2022-04-06 22:03:36

要不断坚持啊 · 2022-04-06 22:03:36 发布

“冒泡排序法” 基本原理

从将要排序的对象中每次选择一个最小元素（或最大元素），按照非递减（从小到大）（或非递增（从大到小））顺序与相邻元素进行比较，将小（或大）的元素交换至左端（或右端），所以小（或大）的元素会不断的往左（或右）移动，每次移动时，最大元素向“气泡”一样冒出，然后移动到适当的位置，因此称为冒泡排序法。以此类推，直至排序完成。

冒泡排序法可以利用设置标志的方式减少比较时间，当走完一圈没有发生交换元素的动作，表示排序已经完成，而无需再进行之后的回圈比较与交换动作。

如下所示：

排序前：95 27 90 49 80 58 6 9 18 50

第1步：27 90 49 80 58 6 9 18 50 [95] 95浮出

第2步：27 49 80 58 6 9 18 50 [90 95] 90浮出

第3步：27 49 58 6 9 18 50 [80 90 95] 80浮出

第4步：27 49 6 9 18 50 [58 80 90 95] 58浮出

第5步：27 6 9 18 49 [50 58 80 90 95] 50浮出

第6步：6 9 18 27 [49 50 58 80 90 95] 49浮出

第7步：6 9 18 [27 49 50 58 80 90 95] 排序结束

到 第7步 时，剩下的数字6、9、18、27已经没有交换元素的动作，因此排序结束。

代码实现

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
#define SWAP(x,y) {int t; t = x; x = y; y = t;}//借助宏定义实现元素交换，可以修改为函数


void bubsort(int number[]){ 
	int i, j, k, flag = 1;
	for(i = 0; i < MAX-1 && flag == 1; i++){ 
		flag = 0; //判断结束标志
		for(j = 0; j < MAX-i-1; j++){ 
			if(number[j+1] < number[j]){
                //此处可以将SWAP宏定义中的交换修改为元素在内部交换
				SWAP(number[j+1], number[j]); 
				flag = 1;
			}
		}
		printf("第 %d 次排序：", i+1); 
		for(k = 0; k < MAX; k++){
			printf("%d ", number[k]);
		}
		printf("\n");
	}
}

int main(){
	int number[MAX] = {0}; 
	int i;
	srand(time(NULL));//刷新每次产生的随机数，若无此句，每次随机数相同，亲自尝试一下便知 
	printf("\n冒泡排序:\n\n");
	printf("排序前：");
	for(i = 0; i < MAX; i++){ 
		number[i] = rand() % 100; //产生0-99的随机数，这里没有采用固定的数组值进行排序，随机生成
		printf("%d ", number[i]);//输出数组元素
	}
	printf("\n\n");
	bubsort(number);
	return 0;
}