# 数组排序-冒泡排序法 在实际开发中，有很多场景需要我们将数组元素按照从大到小（或者从小到大）的顺序排列，这样在查阅数据时会更加直观，例如： - 一个保存了班级学号的数组，排序后更容易分区好学生和坏学生； - 一个保存了商品单价的数组，排序后更容易看出它们的性价比。 对数组元素进行排序的方法有很多种，比如冒泡排序、归并排序、选择排序、插入排序、快速排序等，其中最经典最需要掌握的是「冒泡排序」。 以从小到大排序为例，冒泡排序的整体思想是这样的： - 从数组头部开始，不断比较相邻的两个元素的大小，让较大的元素逐渐往后移动（交换两个元素的值），直到数组的末尾。经过第一轮的比较，就可以找到最大的元素，并将它移动到最后一个位置。 - 第一轮结束后，继续第二轮。仍然从数组头部开始比较，让较大的元素逐渐往后移动，直到数组的倒数第二个元素为止。经过第二轮的比较，就可以找到次大的元素，并将它放到倒数第二个位置。 - 以此类推，进行 n-1（n 为数组长度）轮“冒泡”后，就可以将所有的元素都排列好。 整个排序过程就好像气泡不断从水里冒出来，最大的先出来，次大的第二出来，最小的最后出来，所以将这种排序方式称为冒泡排序（Bubble Sort）。 ## 算法总结及实现 对拥有 n 个元素的数组 R[n] 进行 n-1 轮比较。 第1轮，逐个比较 (R[1], R[2]), (R[2], R[3]), (R[3], R[4]), ……. (R[N-1], R[N])，最大的元素被移动到 R[n] 上。 第2轮，逐个比较 (R[1], R[2]), (R[2], R[3]), (R[3], R[4]), ……. (R[N-2], R[N-1])，次大的元素被移动到 R[n-1] 上。 ......（每一轮比较前 n-1-i 个数，已经排序好的i个不用比较） 第n-1轮，比较 (R[1], R[2])，得出第n-1大的元素，移动到R[2]位置上，最后一个R[1]则自动被判定为最小的元素。 以此类推，直到整个数组从小到大排序。具体代码实现。 ```c #include #include int main(int argc, char *argv[]) { int nums[10] = { 4, 5, 2, -34, 93, 28, -9, 100, 7, 99 }; int i, j, temp; //冒泡算法排序, 对于每个元素进行n-1轮比较 for (i = 0; i < 10-1; i++) { //每一轮比较前 n-1-i 个数，已经排序好的i个不用比较 for (j = 0; j < 10 - 1 - i; j++) { if (nums[j] > nums[j + 1]) { temp = nums[j+1]; nums[j + 1] = nums[j]; nums[j] = temp; } } } //输出排序后的数组 printf("{"); for (i = 0; i < 10; i++) { printf("%d ", nums[i]); } printf("}\n"); system("pause"); return 0; } ``` ## 优化算法 上面的算法是大部分教材中提供的算法，其中有一点是可以优化的：当比较到第 i 轮的时候，如果剩下的元素已经排序好了，那么就不用再继续比较了，跳出循环即可，这样就减少了比较的次数，提高了执行效率。未经优化的算法一定会进行 n-1 轮比较，经过优化的算法最多进行 n-1 轮比较。 ```c #include int main(){ int nums[10] = {4, 5, 2, 10, 7, 1, 8, 3, 6, 9}; int i, j, temp, isSorted; //优化算法：最多进行 n-1 轮比较 for(i=0; i<10-1; i++){ isSorted = 1; //假设剩下的元素已经排序好了 for(j=0; j<10-1-i; j++){ if(nums[j] > nums[j+1]){ temp = nums[j]; nums[j] = nums[j+1]; nums[j+1] = temp; isSorted = 0; //一旦需要交换数组元素，就说明剩下的元素没有排序好 } } if(isSorted) break; //如果没有发生交换，说明剩下的元素已经排序好了 } for(i=0; i<10; i++){ printf("%d ", nums[i]); } printf("\n"); return 0; } ``` 我们额外设置了一个变量 isSorted，用它作为标志，值为“真”表示剩下的元素已经排序好了，值为“假”表示剩下的元素还未排序好。 每一轮比较之前，我们预先假设剩下的元素已经排序好了，并将 isSorted 设置为“真”，一旦在比较过程中需要交换元素，就说明假设是错的，剩下的元素没有排序好，于是将 isSorted 的值更改为“假”。 每一轮循环结束后，通过检测 isSorted 的值就知道剩下的元素是否排序好。