冒泡排序——简单理解和使用

阅前声明：如果想直接了解冒泡排序的简化思想，请跳至文章尾部

在介绍之前，我们先看一个用到该功能的实战训练（本人也是从中开始认识到冒泡排序这个函数定义）

对于小白来说，我的思路如下：

1.题目中涉及到三个数组，首先scanf两个整型变量m,n，其次定义三个变长数组arr[m + n] 、arr1[m] 、arr2[n]；

2.我们了解到一个关键信息，两个输入的数组为升序类型，那么考虑两个数组中同下标值的元素进行比较，然后根据他们比较的结果在arr中进行元素输入；

具体操作编码如下：（为错误示范，可以理解和纠正一下编码思路）

void input_arr(int arr[], int a,int b)
{for (a = 0; a < b; a++){scanf("%d", &arr[a]);}
}
int smaller(int a, int b)
{if (a >= b)return b;elsereturn a;
}
int bigger(int a, int b)
{if (a >= b)return a;elsereturn b;
}
void print(int a , int arr[])
{int i;for (i = 0; i < a; i++){printf("%d ", arr[i]);}
}
int main()
{int m, n;scanf("%d %d", &m, &n);int arr1[m];//先将三个数组定义出来int arr2[n];int arr[m + n];int i,j;input_arr(arr1, i, m);//输入两个数组input_arr(arr2, i, n);int b = smaller(m,n);//先比较m,n；用新赋值的变量去参与后续判断int c = bigger(m,n);for (j = 0; j < c; j++)//利用变量j对arr数组的元素进行输入{if (j < b)//在相同下标区间内，进行大小判断，要将两个同数量的数组比较并放入新的数组中，需要2b个空间，下标位数为2b-1{arr[2 * j ] = smaller(arr1[j], arr2[j]);//先进行一个同下标数的大小判断，小的放在本位上，大的放在+1位上arr[2 * j + 1] = bigger(arr1[j], arr2[j]);if (j >= 1){arr[2 * j] = bigger(smaller(arr1[j], arr2[j]), arr[2 * j - 1]);//将新的小值与前一次的大值进行比较，纠正排序arr[2 * j - 1] = smaller(smaller(arr1[j], arr2[j]), arr[2 * j - 1]);}}//到这里完成了0-2b-1的数值输入，共2b个数else if (j == b){if (b == m) //判断元素数量大的一方数组后，对超出的第一位数组值进行比较{arr[2 * b] = bigger(arr2[b], arr[2 * b - 1]);arr[2 * b - 1] = smaller(arr2[b], arr[2 * b - 1]);}else{arr[2 * b] = bigger(arr1[b], arr[2 * b - 1]);arr[2 * b - 1] = smaller(arr1[b], arr[2 * b - 1]);}}else{if (b == m){arr[2 * b + j - b] = arr2[j];}else{arr[2 * b + j - b] = arr1[j];}}}for (int s = m + n - 1; s > 0; s--){int temp;if (arr[s] < arr[s - 1]){temp = arr[s];arr[s] = arr[s - 1];arr[s - 1] = temp;}}print(m + n, arr);return 0;
}//仅适合升序，且没有相同数的两个数组

在这个输入例子中，编写的代码出现了明显的错误，存在交替的大小变化，这是由于下标值相差太多的元素之间存在漏比较的情况，这是由于我们比较方式的局限性导致的，不要简单的把一个元素集合按照规定的容量分为多个比较区间，进行依次比较后纠正的元素排列就是我们想要的结果，下面是这种错误观念的示意图

一个数字，确定其在整型数组中正确的大小排序和下标值，应该将其和每一个元素进行比较。

那么我们可以得出冒泡排序的关键思想：

假设一个整型数组 中有N个元素，每一个元素确定自己的正确位置需要与剩余的N-1个元素进行比较，而每一个元素都需要完成这个过程 即 实现数组的正确排序，我们需要完成N * (N - 1)次的比较，细分下来就是C语言中的两个for循环的嵌套使用，具体如下：

	for (int a = 0; a < m + n; a++){for (int b = 0; b < m + n - 1; b++){int temp = 0;if (arr[b] > arr[b + 1]){temp = arr[b + 1];//此时的temp仅为存储数据的一个整型变量，无其他特殊含义arr[b + 1] = arr[b];arr[b] = temp;}}}

因此，我们可以简化并且加深对冒泡排序这个代码块的理解。

有表述不当的地方辛苦不吝赐教，三克油。

打怪升级中..................................................................................................................................