1.冒泡排序的基本思想
交换排序的基本思想是：两两比较待排序记录（数据表）的关键字（排序码），发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。主要包括冒泡排序和快速排序。
冒泡排序容易理解，因为就像泡泡一样，最轻的率先“冒”出来占据第一的位置，随后是剩下的最轻的再冒出来，占据第二的位置，就这样一步步冒出来，也就完成了排序。
2.冒泡排序的步骤
（1）冒泡排序算法的运作如下：
a.对象个数n。最多作最多作n-1趟， i= 0, 2, …, n-1 。
b.第i趟中从后向前j= n-1, n-2, ……, i，顺次两两比较。
c.比较如果发生逆序，则交换V[j-1] 和V[j]。
冒泡排序算法
（2）例子：以对 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，交换
第二轮结束，第二大的数已经排在倒数第二个位置，所以第三轮只需要比较前两个元素。
第三轮 排序过程
2 1 3 4 （第二轮排序结果）
1 2 3 4 （比较2和1，交换）
至此，排序结束。
总之就是每一趟都是将剩余中最大或最小的数据项排在前面已经“冒”出来的数据表后面，遍历完毕也就实现了排序。
3.冒泡排序分析
（1）最好情况：正序排列，比较次数(KCN):n−1 ; 移动次数(RMN):为0。则对应的时间复杂度为O(n)。
完全正序排列的话，只需一趟就能判定是否有序，如果遍历j之后发现没有发生逆序就说明已经有序，所以，共比较了n−1次，移动0次。
（2）最坏情况：逆序排序，比较次数(KCN): n(n−1)/2；移动次数(RMN): n(n−1)/2。
完全逆序排序的话，第i都要比较n−i次，而每次比较都要移动3次数据项来交换记录位置。因此总的时间复杂度为O(n2)。
（3）冒泡排序算法，需要一个附加空间，是一个稳定的排序算法。
4.冒泡排序算法C语言源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ #include<stdio.h> #include<stdlib.h> #define N 8 void bubble_sort(int a[],int n); //一般实现 void bubble_sort(int a[],int n)//n为数组a的元素个数 { //一定进行N-1轮比较 for(int i=0; i<n-1; i++) { //每一轮比较前n-1-i个，即已排序好的最后i个不用比较 for(int j=0; j<n-1-i; j++) { if(a[j] > a[j+1]) { int temp = a[j]; a[j] = a[j+1]; a[j+1]=temp; } } } } //优化实现 void bubble_sort_better(int a[],int n)//n为数组a的元素个数 { //最多进行N-1轮比较 for(int i=0; i<n-1; i++) { bool isSorted = true; //每一轮比较前n-1-i个，即已排序好的最后i个不用比较 for(int j=0; j<n-1-i; j++) { if(a[j] > a[j+1]) { isSorted = false; int temp = a[j]; a[j] = a[j+1]; a[j+1]=temp; } } if(isSorted) break; //如果没有发生交换，说明数组已经排序好了 } } int main() { int num[N] = {89, 38, 11, 78, 96, 44, 19, 25}; bubble_sort(num, N); //或者使用bubble_sort_better(num, N); for(int i=0; i<N; i++) printf("%d ", num[i]); printf("\n"); system("pause"); return 0; } |
5.冒泡排序算法C++源代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | /** * 算法君：一个专业的算法学习分享网站 * 算法君：专业分享--数据剖析--算法精解 * 算法君：http://www.suanfajun.com */ #include <iostream> using namespace std; void BubbleSort(int a[], int size) { int i,j,k,temp; for(i = 0; i < size - 1; i++) { for(j=0; j < size - 1; j++) { if(a[j] > a[j+1]) { temp = a[j+1]; a[j+1] = a[j]; a[j] = temp; } } for(k = 0; k < size; k++) cout << a[k] <<" "; cout << endl; } int dummy = 1; } int main() { int k; int a[] = {5,7,1,3,4,9,2,6,8,0}; const size_t sz = sizeof(a)/sizeof(a[0]); for(k = 0; k < sz; k++) cout << a[k] <<" "; cout << endl; cout << "======================" << endl; BubbleSort(a,sz); cout << "======================" << endl; for(k = 0; k < sz; k++) cout << a[k] <<" "; cout << endl; } |
