用数据结构实现冒泡排序,运用c语言,用change减少运行次数
时间: 2024-09-15 10:09:26 浏览: 22
在C语言中,我们可以使用数组或结构体作为数据结构来实现冒泡排序。冒泡排序的基本思想是比较相邻的元素,如果它们的顺序错误就把它们交换过来,直到整个序列都有序。为了减少不必要的比较,可以引入一个名为`swapped`的标志变量,它用于记录是否进行了交换,如果没有发生交换说明已经有序,这时可以提前结束循环。
以下是使用数组和`change`计数器实现冒泡排序的示例:
```c
#include <stdio.h>
void bubbleSort(int arr[], int n, int *change) {
for (int i = 0; i < n - 1; i++) { // 一次遍历n-1次
for (int j = 0; j < n - i - 1; j++) { // 每次内部循环比上一次少一位
if (arr[j] > arr[j + 1]) { // 如果当前元素大于下一个
int temp = arr[j];
arr[j] = arr[j + 1]; // 交换
arr[j + 1] = temp;
*change++; // 记录交换次数
}
}
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
int change = 0; // 初始化变化计数器
bubbleSort(arr, n, &change);
printf("Sorted array is \n");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\nNumber of swaps: %d\n", change);
return 0;
}
```
在这个例子中,`bubbleSort`函数接受一个整型数组、数组长度以及指向`change`变量的指针。当发现元素需要交换时,会递增`change`。当遍历结束后,如果`change`没有发生变化,说明数组已经是有序的,可以提前结束排序。