提示:本文是为C语言排序算法小萌新科普,其他语言的朋友可以参考,大佬“非礼勿视”
对于冒泡排序,我们应该对它的思想进行理解,作为排序算法学习的引导,让我们的思维更加开阔。
文章目录
前言一、冒泡排序算法是什么?二、C语言实现代码1.核心函数2.完整程序 三、针对问题进行优化算法问题优化方案实现问题解决方案(附代码)最终代码效果图对比优化前优化后统计表格数据 总结前言
冒泡排序的原理是:从左到右,相邻元素进行比较。每次比较一轮,就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。
以下是本篇文章正文内容
一、冒泡排序算法是什么?
冒泡排序,是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
二、C语言实现代码
1.核心函数
函数如下(示例):
for (i=0; i<len-1; i++) /* 外循环为排序趟数,len个数进行len-1趟 */for (j=0; j<len-1-i; j++) {/* 内循环为每趟比较的次数,第i趟比较len-i次 */if (arr[j] > arr[j+1]) {/* 相邻元素比较,若逆序则交换(升序为左大于右,降序反之) */temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}
从头开始比较相邻的两个元素,如果有一个的元素比相邻的元素的大(小),就交换两个元素的位置。
注:这些可以根据写程序的人的意愿来调整往前对每个相邻的元素都做这样的比较、交换操作,这样到数组头部时,第 1 个元素会成为最大的元素。重新开始第 1、2 步的操作,除了在这之前头部已经排好的元素。继续对越来越少的数据进行比较、交换操作,直到没有可比较的(即没有逆序的)数据为止,排序完成。
2.完整程序
程序如下(示例):
#include <stdio.h>#define ARR_LEN 255 /*数组长度上限*/#define elemType int /*元素类型*//* 冒泡排序 *//* 1. 从当前元素起,向后依次比较每一对相邻元素,若逆序则交换 *//* 2. 对所有元素均重复以上步骤,直至最后一个元素 *//* elemType arr[]: 排序目标数组 int len: 元素个数 */void bubbleSort (elemType arr[], int len) {elemType temp;int i, j;for (i=0; i<len-1; i++) /* 外循环为排序趟数,len个数进行len-1趟 */for (j=0; j<len-1-i; j++) {/* 内循环为每趟比较的次数,第i趟比较len-i次 */if (arr[j] > arr[j+1]) {/* 相邻元素比较,若逆序则交换(升序为左大于右,降序反之) */temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}int main (void) {elemType arr[ARR_LEN] = {58649841,5,1,-7,4,9,-6,8,10,4};int len = 10;int i;bubbleSort (arr, len);for (i=0; i<len; i++)printf ("%d\t", arr[i]);putchar ('\n');return 0;}
三、针对问题进行优化
算法问题
数据的顺序排好之后,冒泡算法仍然会继续进行下一轮的比较,直到arr.length-1次,后面的比较没有意义的。
优化方案
添加变量钥匙key。
如果发生了交换,key设置为true;如果没有交换就设置为false。
这样当一轮比较结束后如果key仍为false,即:这一轮没有发生交换,这就说明数据的顺序已经排好,没有必要继续进行下去。
实现问题
C语言没有布尔值(true值和false值)
解决方案(附代码)
C语言中表示真假的值是0和1,我们可以利用预定义解决。
true可以用1替代
false可以用0替代
代码
#define True 1 /*将True的值定义为1,即为真*/#define False 0 /*将False的值定义为0,即为假*/
最终代码
#include <stdio.h>#define ARR_LEN 255 /*数组长度上限*/#define elemType int /*元素类型*/#define bool short /*将bool定义为short关键字,便于区分*/ #define True 1 /*将True的值定义为1,即为真*/#define False 0 /*将False的值定义为0,即为假*/ /* 冒泡排序 *//* 1. 从当前元素起,向后依次比较每一对相邻元素,若逆序则交换 *//* 2. 对所有元素均重复以上步骤,直至最后一个元素 *//* elemType arr[]: 排序目标数组 int len: 元素个数 */void bubbleSort (elemType arr[], int len) {elemType temp;int i, j;bool key; /*设置key*/ for (i=0; i<len-1; i++) {/* 外循环为排序趟数,len个数进行len-1趟 */key = False; /*每次排序先将key的值初始化为False*/for (j=len-1; j>0; j--) {/* 内循环为每趟比较的次数,第i趟比较len-i次 */if (arr[j] < arr[j-1]) {/* 相邻元素比较,若逆序则交换(升序为左大于右,降序反之) */temp = arr[j];arr[j] = arr[j-1];arr[j-1] = temp;key = True; /*只要发生交换,key的值就变为True*/ }}if(false == key) break; /*判断标志位是否为false,如果为false,说明后面的元素已经有序,就果断break*/ }}int main (void) {elemType arr[ARR_LEN] = {58649841,5,1,-7,4,9,-6,8,10,4};int len = 10;int i;bubbleSort (arr, len);for (i=0; i<len; i++)printf ("%d\t", arr[i]);putchar ('\n');return 0;}
效果图对比
注意看运行秒数
优化前
Process exited after 0.6533 seconds with return value 0请按任意键继续. . .
优化后
Process exited after 0.4852 seconds with return value 0请按任意键继续. . .
统计表格数据
备注:这里统计次数较少,而且只用了一组数据做实验,结果可能不太严谨
有质疑的小伙伴可以自己多做几次对比,最好可以使用不同的数据(但每一组要对应)进行实验
总结
冒泡排序是一种简单的稳定的排序算法。. 比较相邻的两个数据,如果数据之间满足整体的要求(从小到大或者从大到小)则交换当前的两个元素的值,直到整体有序。
我们可以考虑对起泡排序算法的改进。具体的某一个待排序元素序列可能不需要执行n - 1 次趟排序就能全部排好。为此 ,我们可以再算法中加上一个变量key ,用来标示本趟起泡结果是否发生了逆序交换 。如果没有发生交换,则 False == key ,表示全部的元素都已经排好了,可以进行终止处理,否则继续进行排序。
冒泡排序法在日常中并不会经常性使用,但其思维可以供我们学习。