排序算法—冒泡排序
Table of Contents
1 问题描述
引子
- 说明
排序是数据结构中十分重要的一章,排序算法有很多种,一直没时间整理而且很多排序算法理解的也不是很透彻.希望通过这次整理吃透吧! 排序算法十分多,故分篇进行整理.
- 分类
本文重点是理解排序算法,而不是完整的程序,所以每节都只有具体排序算法的接口.没有完整的源代码.
内部排序
- 整个排序过程完全在内存中进行.
外部排序- 因为待排序的记录数据太大,内存无法容纳全部数据,需要借助外部存储设备才能完成排序.
2 冒泡排序(Bubble)
这个应该是众多程序员接触的第一个排序算法,十分基础.
冒泡排序算法的原理如下:
每次比较相邻的元素,如果第一个数比第二个数大,就交换他们.对每一对相邻元素做同样的工作,
从开始第一对到最后一对.这步做完后,最后的元素就是最大的数.重复上述步骤,这样第 i 次比较完后,
最后的元素就是第 i 大的数.持续每次对越来越少的元素重复上面的步骤,直到没有需要比较的元素为止.
2.1 冒泡排序(一)
1: /** 2: * 基本的冒泡排序 3: * @param int* num 排序数组 4: * @param int length 数组大小 5: * @return int 排序成功与否 6: */ 7: int BubbleSort(int *num, int length) 8: { 9: int i,j;10: if(length < 2)11: return 0;12: for(i = 0; i < n; i++) //外层循环控制排序的趟数13: {14: for(j = 0; j < n-1-i; j++) //内层循环控制排序要交换的数的范围15: {16: if(num[j] > num[j+1])17: swap(num[j],num[j+1]) //两两相邻的数比较大小 18: }19: }20: return 0;21: }22: 算法分析:23: 时间复杂度:最优的情况,所有的数都是有序的,那么内层循环就不用交换数了,24: 只进行外层的循环,复杂度是O(n);25: 最差的情况,所有的数都是倒序的,那么两层循环都要进行,复杂度是O(n^2);26: 平均时间复杂度是O(n^2);27: 空间复杂度:一维数组 O(1);该思路也可以逆序进行,伪代码如下:
1: for(i from n-1 downto 0) 2: { 3: for(j from n-1 downto n-1-i) 4: { 5: cmp(num[j],num[j-1]) 6: } 7: } 8: 9: // 其他类似的写法还有:10: for(i = n-1; i > 0; i--)11: {12: for(j = 0; j > i; j++)13: {14: cmp(j,j+1)15: }16: }17: 18: // 交换排序19: for(i = 0; i < n-1; i++)20: {21: for(j = i+1; j < n; j++)22: {23: cmp(num[i],num[j]) //此时比较的不是相邻的两个元素了24: }25: }
2.2 冒泡排序(二)
上述的排序是两两相邻的数进行比较,更符合冒泡的形态.但实际上要比较的也不一定就是相邻的数.
1: /** 2: * 改进的冒泡排序一 3: * @param int* num 排序数组 4: * @param int length 数组大小 5: * @return int 排序成功与否 6: */ 7: 8: //逆序版 但还是不同的较少了交换的次数 而且类似选择排序 9: int BubbleSort(int *num, int length)10: {11: int i,j,max;12: if(length < 2)13: return 0;14: for(i = n-1; i > 0; i--) //外层循环控制排序的趟数15: {16: for(j = 1,max = 0; j < i; j++) //从0～j左边部分选出最大的数17: {18: if(num[max] < num[j])19: max = j;20: }21: if(num[i] < num[max])22: swap(num[i],num[max]);23: }24: return 0;25: }
2.3 冒泡排序(三)
可以设置一个标志,如果一趟过程中发成了交换,则为true,反之则未false,如果有一趟没有发生交换就说明排序已经完成
1: /** 2: * 改进的冒泡排序二 3: * @param int* num 排序数组 4: * @param int length 数组大小 5: * @return int 排序成功与否 6: */ 7: int BubbleSort(int *num, int length) 8: { 9: int i,j,flag;10: if(length < 2)11: return 0;12: for(i = 0; i < n-1; i++) //外层循环控制排序的趟数13: {14: flag = 0;15: for(j = n-1; j > i; i++) //内层循环控制依次排序的完成16: {17: if(num[j] > num[j-1])18: { 19: swap(num[i],num[j]) 20: flag = 1;21: }22: }23: if(flag == 0) //终止排序24: break; 25: }26: return 0;27: } 28: 如果100个数,就前10个数是乱序的,后面的数是有序的.可以通过设置标志记录交换时的位置,下一次循环到此处即可.29: int BubbleSort(int *num, int length)30: {31: int i,j,lastchange; //lastchange记录上次交换的位置32: if(length < 2)33: return 0;34: i = n;35: while(i > 0)36: {37: lastchange = 0;38: for(j = 0; j < i; j++)39: {40: if(num[j] > num[j+1])41: {42: swap(num[j],num[j+1])43: lastchagne = j;44: } //if45: }// for46: i = lastchange;47: }48: return 0;49: }
2.4 冒泡排序(四)
双向冒泡进一步提高效率,又称鸡尾酒排序.
1: /** 2: * 基本的冒泡排序 3: * @param int* num 排序数组 4: * @param int length 数组大小 5: * @return int 排序成功与否 6: */ 7: int BubbleSort(int *num, int length) 8: { 9: int i,j,left,right,l,r;10: left = 0;i = 0;11: right = length-1;12: 13: //双向冒泡14: while(left < right)15: {16: //必须要给l和r赋值,否则若数组一开始就是有序,则right = r时,r未赋值会报错.17: l = left + 1;18: r = right - 1;19: 20: // 第一次循环将最大的值放到末尾21: for(j = left; j < right; j++)22: {23: if(a[j] > a[j+1])24: { 25: swap(a[j],a[j+1]);26: r = j;27: }28: }29: right = r; // 这里好好想想,r 不一定是最后一个数喔!30: 31: //第二次循环将最小的值放到开头32: for(j = right; j > left; j--)33: { 34: if(a[j] < a[j-1])35: {36: swap(a[j],a[j-1]);37: l = j;38: }39: }40: left = l;41: 42: //测试结果43: /*44: printf("第%d次排序结果:",i+1);45: i++;46: for(j = 0; j < n; j++)47: printf("%d\t",a[j]);48: */49: }50: }51:
3 阅读参考
Date: 2014-08-15 Fri
Org version 7.8.11 with Emacs version 24