冒泡排序介绍
定义:冒泡排序(Bubble Sort)是一种最基础的交换排序。之所以叫做冒泡排序,因为每一个元素都可以像小气泡一样,根据自身大小一点一点向数组的一侧移动。
解释:图片中10个元素为什么进行9趟冒泡排序?
按照规律应该是10趟,但在完成9趟冒泡时,9位元素已经就位,因此第十个数就已经其他数原因也就位了。就好比有5个小朋友按顺序分五个凳子,前四个已经排好了,第五个就不需要再排就知道应该在哪里了。
代码如下:
voidbubble_sort(intarr[],intsz) { inti=0; //确定冒泡排序的趟数for (i=0; i<sz-1; i++) { intj=0; flag=1; //对两个数比大小for (j=0; j<sz-1-i; j++) { //调换前后数据if (arr[j] >arr[j+1]) { inttap=arr[j]; arr[j] =arr[j+1]; arr[j+1] =tap; } } } } intmain() { intarr[] = { 9,8,7,6,5,4,3,2,1,0}; inti=0; intsz=sizeof(arr) /sizeof(arr[0]); bubble_sort(arr,sz);//冒泡排列for (i=0;i<sz;i++) { printf("%d ", arr[i]);//打印排列好的数组 } return0; }
修改版代码:
voidbubble_sort(intarr[],intsz) { inti=0; //确定冒泡排序的趟数intflag=0; for (i=0; i<sz-1; i++) { intj=0; flag=1; //对两个数比大小for (j=0; j<sz-1-i; j++) { //调换前后数据if (arr[j] >arr[j+1]) { inttap=arr[j]; arr[j] =arr[j+1]; arr[j+1] =tap; flag=0;//本躺需要排序 } } if (flag==1)//检查本趟是否还需要再进行排列 { break; } } } intmain() { intarr[] = { 9,1,2,3,4,5,6,7,8,}; inti=0; intsz=sizeof(arr) /sizeof(arr[0]); bubble_sort(arr,sz);//冒泡排列for (i=0;i<sz;i++) { printf("%d ", arr[i]);//打印排列好的数组 } return0; }
进阶版解析:在冒泡排序中加入了一个if判断,若正在进行的这一趟冒牌排序已经有序,那么直接跳出第二个for循环可以节省内存。