本文共 992 字,大约阅读时间需要 3 分钟。
优化后的冒泡排序算法:
在刚开始写的时候,遇到想用size_t(即unsigned int)来表示数组索引,但是在进行比较时,j出现溢出,最后用int型来表示~
注意点在注释中写明
若为基本有序的情况下,如a[9]={2,1,3,4,5,6,7,8,9}则时间复杂度为O(n)
但在最差情况下,为O(n^2)
//优化后的冒泡排序(排序后为从小到大)#include#include using namespace std;void BubbleSort(int (&a)[7]){//数组作为引用形参传入,使用在此修改对原数组也有效 int aSize = sizeof(a) / sizeof(a[0]);//取数组的大小 int flag = 1;//flag用来判断是否为基本有序情况 for (int i = 0; flag && i < (aSize - 1); ++i){//执行aSize-1次外循环,因为执行完后,最后一个数一定是最大的,flag放前面,当为0时,减少运算 flag = 0; for (int j = (aSize - 2); j >= i; --j){//这里用int型的原因,就是为了防止当i=0、j=0时,因为j>=i满足,--j时如果j为unsigned int型会溢出 if (a[j]>a[j + 1]){//从倒数第二个数开始,与后一个相比,将小的换到前面。 swap(a[j], a[j + 1]); flag = 1;//有交换则flag=1 } } }}int main(){ int a[] = {12, 42, 6, 17, 32, 4, 19 }; cout << "Before Sorted:" << endl; for (size_t i = 0; i < 7; ++i){//输出 cout << a[i] << " "; } cout << endl; BubbleSort(a); cout << "After Sorted:" << endl; for (size_t i = 0; i < 7; ++i){//输出 cout << a[i] << " "; } cout << endl; return 0;}
最终程序结果: