C语言 冒泡排序

冒泡排序:
是一种简单直观的排序算法，核心思想是通过多次遍历数组，将较大的元素逐步“冒泡”到数组的末尾，最终实现排序。它的名字来源于排序过程中较大的元素像气泡一样逐渐上浮的过程。

算法原理:

冒泡排序通过比较相邻的两个元素，如果前一个元素比后一个元素大，则交换它们的位置。每一轮遍历后，当前未排序部分的最大值会被移动到数组的末尾。重复这一过程，直到整个数组有序。

假设这里有一组数据，需要排成升序。

确定要排几趟：

可以发现这 10 个数字，需要 9 趟排序。排序把 9个数字都放在这 9 个数字应该出现的位置上，最后 10 个数字，自然地也出现在它应该出现的位置。如果是 n 个元素那么就需要 n-1 趟冒泡排序。

确定要比较级个元素：

10 个数字需要 9 对相邻的元素进行比较，排完 1 趟，9来到想要的位置，下次比较相临元素的对数-1。

下一趟，9 个元素比较，8 对相邻元素比较。排完第2趟，8来到想要的位置，下次比较相临元素的对数-1。

由此可知：每排序一次，需要比较相邻元素的对数-1。

{ int i = 0; // sz 计算元素个数 int sz = sizeof(arr) / sizeof(arr[0]); //确定趟数 for (i = 0; i < sz - 1; i++) { int j = 0; //确定比较相邻元素的对数 for (j = 0; j < sz - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = tmp; } } } } int main() { int arr[] = { 9,8,7,6,5,4,3,2,1,0 }; bubble_sort(arr); int i = 0; for (i = 0; i < 10; i++) { printf("%d ", arr[i]); } return 0; }

sz-1: 最多访问到最后一个元素的下标 ;

sz - 1 - j : 减去个 j , 做到每排完一趟，需要比较的元素的对数就-1。

第一趟是 10-1-0。j 是 0，10个元素，有9对。

第一趟是 10-1-1。j 是 1，9个元素，有8对。

......

依此类推。

运行下看结果。

发现，欸，不对啊，怎么没排序呢。我来找下猫腻。

我们说传参传个数组名，传的是首元素的地址。int arr[ ] 里存的是数组首元素地址。

我们来看下内存。这是没进入bubble_sort 之前的首元素地址。

这是进入函数，形参和sz里存的东西：

一看,sz怎么是1？不是我要的10啊。

下面来解释：

你给我传了个地址 ，那我得用指针接收。int arr[ ] 本质是指针变量 等价于 int * arr，那这在计算元素个数时就要出大问题了。

我们说，指针变量的大小是4或8个字节。在32位机器下是4个字节，在64机器下是8个字节。

sz在计算的时候：用指针变量的大小除以了第一个元素大小，这里是32位环境指针变量是4字节，就计算出来是1；如果是64 位环境下，指针变量是8字节，那结果就是2。

所以这里的sz就是1了，那么sz-1即1-1=0。根本没有进循环。再打印的时候，也会就是原来的数组了。

这里呢有个 t i p:建议不要在函数内部计算元素个数，建议再传参的时候把元素分数传过去直接使用。

这里找到问题，这次在函数外面求sz。

void bubble_sort(int arr[], int sz) { int i = 0; for (i = 0; i < sz - 1; i++) { int j = 0; for (j = 0; j < sz - 1 - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = tmp; } } } } int main() { int arr[] = { 1,2,3,4,5,6,7,8,9,0 }; int sz = sizeof(arr) / sizeof(arr[0]);//计算元素分数 bubble_sort(arr, sz); int i = 0; for (i = 0; i < 10; i++) { printf("%d ", arr[i]); } return 0; }

这次的结果呢：

这次正确了。看来问题已经解决了。那么以上，就是冒泡排序的基本思想和实现。