在实际开发中, 有很多场景需要我们将数组元素按照从大到小 (或者从小到大) 的顺序排列, 这样在查阅数据时会更加直观, 例如:
一个保存了班级学号的数组, 排序后更容易分区好学生和坏学生;
一个保存了商品单价的数组, 排序后更容易看出它们的性价比.
以从小到大排序为例, 冒泡排序的整体思想是这样的:
小编推荐一个学 C 语言 / C++ 的学习裙[ 七三零, 一三零, 二二一 ] , 无论你是大牛还是小白, 是想转行还是想入行都可以来了解一起进步一起学习! 裙内有开发工具, 很多干货和技术资料分享!
算法思想:
从数组头部开始, 不断比较相邻的两个元素的大小, 让较大的元素逐渐往后移动(交换两个元素的值), 直到数组的末尾. 经过第一轮的比较, 就可以找到最大的元素, 并将它移动到最后一个位置.
第一轮结束后, 继续第二轮. 仍然从数组头部开始比较, 让较大的元素逐渐往后移动, 直到数组的倒数第二个元素为止. 经过第二轮的比较, 就可以找到次大的元素, 并将它放到倒数第二个位置.
以此类推, 进行 n-1(n 为数组长度)轮 "冒泡" 后, 就可以将所有的元素都排列好.
整个排序过程就好像气泡不断从水里冒出来, 最大的先出来, 次大的第二出来, 最小的最后出来, 所以将这种排序方式称为冒泡排序(Bubble Sort).
下面我们以 "3 2 4 1" 为例对冒泡排序进行说明.
第一轮 排序过程
- 3 2 4 1 (最初)
- 2 3 4 2 (比较 3 和 2, 交换)
- 2 3 4 1 (比较 3 和 4, 不交换)
- 2 3 1 4 (比较 4 和 1, 交换)
第一轮结束, 最大的数字 4 已经在最后面, 因此第二轮排序只需要对前面三个数进行比较.
第二轮 排序过程
- 2 3 1 4 (第一轮排序结果)
- 2 3 1 4 (比较 2 和 3, 不交换)
- 2 1 3 4 (比较 3 和 1, 交换)
第二轮结束, 次大的数字 3 已经排在倒数第二个位置, 所以第三轮只需要比较前两个元素.
第三轮 排序过程
- 2 1 3 4 (第二轮排序结果)
- 1 2 3 4 (比较 2 和 1, 交换)
至此, 排序结束.
算法总结及实现
对拥有 n 个元素的数组 R[n] 进行 n-1 轮比较.
第一轮, 逐个比较 (R[1], R[2]), (R[2], R[3]), (R[3], R[4]), ....... (R[N-1], R[N]), 最大的元素被移动到 R[n] 上.
第二轮, 逐个比较 (R[1], R[2]), (R[2], R[3]), (R[3], R[4]), ....... (R[N-2], R[N-1]), 次大的元素被移动到 R[n-1] 上.
......
以此类推, 直到整个数组从小到大排序.
小编推荐一个学 C 语言 / 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(" ");
- return 0;
- }
运行结果:
小编推荐一个学 C 语言 / C++ 的学习裙[ 七三零, 一三零, 二二一 ] , 无论你是大牛还是小白, 是想转行还是想入行都可以来了解一起进步一起学习! 裙内有开发工具, 很多干货和技术资料分享!
冒泡排序运行结果
这就是 C 语言冒泡排序的运行结果了, 这是非常重要的, 一定要掌握喔. 当然, 还有一种简单的算法思想
这些是 C/C++ 能做的
来源: http://www.jianshu.com/p/d0f248f557b2