【c++数据结构】关于冒泡排序的两种改进方法_c语言问题 b: 【数据结构10-4】改进的冒泡排序

一种是检查前缀向量（左侧）是否已经是有序向量的冒泡排序。

void bubblesort1(vector<int>& v,int lo,int hi){
	bool sorted =false;//初始化
	int i;
	while (!sorted){
		sorted = true;//假设有序
		i = lo;
		while (++i < hi){
			if (v[i - 1]>v[i]){
				swap(v[i - 1], v[i]);
				sorted = false;
			}
		}
		--hi;
	}
}

一种是检查后缀向量（右侧）是否已经是有序向量的冒泡排序。

void bubblesort2(vector<int>& v, int lo, int hi){
	while (lo<hi){
		int i = lo;
		int last = i;//最右侧逆序对初始化为[lo-1,lo]
		while (++i < hi){
			if (v[i - 1]>v[i]){
				swap(v[i - 1], v[i]);
				last = i;//更新最右侧逆序对位置记录
			}
		}
		hi=last;
	}
}