冒泡排序法
思路:
顾名思义，冒泡排序法就是让数组元素像水中的气泡一样逐渐上浮，进而达到排序的目的。
模板:
bubbleSort(A, N) flag = 1 while flag flag = 0 for j 从 N-1 到 1 if A[j] < A[j-1] A[j]与A[j-1]交换 flag = 1 ________________________________________ int bubbleSort(A, N) { bool flag = 1; for(int i=0;flag;i++) { flag = 0; for(int j = N-1;j >= i + 1;j--) { if(A[j]<A[j-1]) { swap(A[j],A[j-1]); flag = 1; } } } }
C++模板:
#include <bits/stdc++.h> using namespace std; void bubbleSort(int A[],int N) { bool flag=1; for(int i=0;flag;i++) { flag=0; for(int j=N-1;j>=i+1;j--) { if(A[j]<A[j-1]) { swap(A[j],A[j-1]); flag=1; } } } } int main() { int A[100],N; cin>>N; for(int i=0;i<N;i++) cin>>A[i]; bubbleSort(A,N); for(int i=0;i<N;i++) { if(i) cout<<" "; cout<<A[i]; } cout<<endl; return 0; }
时间复杂度:
冒泡排序法仅对数组中的相邻元素进行比较和交换，因此键相同的元素不会改变顺序。所以冒泡排序法也属于一种稳定排序的算法。但要注意的是，一旦将比较运算A[j] < A[j - 1]改为A[j] ≤ A[j - 1]，算法就会失去稳定性。
然后我们考虑一下冒泡排序法的复杂度。假设数据总量为 N，冒泡排序法需对未排序部分的相邻元素进行(N - 1) + (N - 2) + ···+ 1 = (N2 - N)/2次比较。也就是说，冒泡排序法在最坏的情况下需要进行(N2 - N)/2次比较运算，算法复杂度数量级O(N2)。
顺便提一下，冒泡排序法中的交换次数又称为反序数或逆序数，可用于体现数列的错乱程度。
例题:
请编写一个程序，读取数列 A，利用冒泡排序法将其按升序排列并输出。另外，请报告冒泡排序法执行元素交换的次数。
输入：在第 1 行输入定义数组长度的整数 N。在第 2 行输入 N的个数，以空格隔开。
输出：输出总计 2 行。请在第 1 行输出排序后的数列。数列相邻要素用 1 个空格隔开。第 2 行输出元素交换的次数。
输入示例
5 5 3 2 4 1
输出示例
1 2 3 4 5 8
C++
#include <bits/stdc++.h> using namespace std; int bubbleSort(int A[],int N) { int sw=0; bool flag=1; for(int i=0;flag;i++) { flag=0; for(int j=N-1;j>=i+1;j--) { if(A[j]<A[j-1]) { swap(A[j],A[j-1]); flag=1; sw++; } } } return sw; } int main() { int A[100],N,sw; cin>>N; for(int i=0;i<N;i++) cin>>A[i]; sw=bubbleSort(A,N); for(int i=0;i<N;i++) { if(i) cout<<" "; cout<<A[i]; } cout<<endl; cout<<sw<<endl; return 0; }
例题网址:
http://judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=ALDS1
上海得物信息集团有限公司公司福利 1253人发布
