冒泡排序及2种优化方法

冒泡排序及2种优化方法

原博客：白话经典算法系列之八 MoreWindows白话经典算法之七大排序总结篇 

#include <iostream>
#include <vector>
//#include <cstddef>//size_t
using namespace std;void bubble(vector<int> &vi){if(vi.size()<=1) return ;int n=vi.size();//还是不要用size_t了，要不然，(size_t)0-1会转为正数最大值。/*for(int i=0;i<n-1;++i){//把n-1个数放到正确的位置上，排序就完成了。for(int j=0;j<n-i-1;++j){//把某正确的数入到下标为n-i-1的位置上if(vi[j]>vi[j+1])swap(vi[j],vi[j+1]);}}*///上面的下标太麻烦了for(int i=0;i<n-1;++i){//把n-1个数放到正确的位置上，排序就完成了。for(int j=1;j<n-i;++j){if(vi[j]<vi[j-1])swap(vi[j],vi[j-1]);}}
}
//优化1：用一个标记来判断当前起泡过程是否存在交换，如果不存在，则数组已有序，可以终止排序过程了。
void bubble1(vector<int> &vi){if(vi.size()<=1) return ;bool flag=true;//需要继续排序int n=vi.size();int start=0;while(flag){flag=false;for(int j=1;j<n-start;++j){if(vi[j]<vi[j-1]){swap(vi[j],vi[j-1]);flag=true;}}++start;}
}
//优化2：用flag既表示当前层有交换，又表示当前层交换的最大下标，此下标为一层交换的终止下标
void bubble2(vector<int> &vi){if(vi.size()<=1) return ;int flag=vi.size();while(flag){int temp=0;for(int j=1;j<flag;++j){if(vi[j]<vi[j-1]){swap(vi[j],vi[j-1]);//vi[j]已有序，也就是第j+1位有序了temp=j;//设置下次让第j位有序}}flag=temp;}
}int main(){vector<int> vi;vi={1,8,2,3,7,6,9,5,4};
//    bubble(vi);
//    bubble1(vi);bubble2(vi);for(auto ieh: vi)cout<<ieh<<" ";cout<<endl;return 0;
}