Sorting Algorithm-Bubble Sort

バブルソート-Bubble Sort
Algorithm:
バブルソートは交換ソートであり、隣接するレコードのキーワードを2つ比較し、逆シーケンスであれば交換し、逆シーケンスの記録がないことを知るまでの基本思想である.
Ex:
4,3,1,2            
3,1,2,4最大要素4が正しい位置にある
1,2,3,4より前の最大要素3が正しい位置に着いた
1,2,3,4の前の最大要素2が正しい位置に着いた
Code:

void Bubble_Sort(vector<int> &v)
{
	for (int i = 0; i < v.size(); i++)
		for (int j = 0; j < v.size() - i - 1; j++)
		{
			if (v[j]>v[j + 1])
			{	
				int temp = v[j];
				v[j] = v[j + 1];
				v[j + 1] = temp;
			}		
		}
}

Optimize:
バブルソートの最適化は,シーケンスが{2,1,3,4,5,6,7,8,9}である場合,すなわち,第1および第2のキーワードが交換される必要がある以外は正常な順序である.i=1の場合、2および1が交換され、シーケンスは秩序化されているが、アルゴリズムは、データが交換されていないにもかかわらず、i=2〜9および各サイクルのjサイクルを繰り返し実行したが、その後の大量の比較は大幅に余計であった.
シーケンスがこのとき秩序化されていれば後のループ判定作業を継続しないことを実現するために,コードを改善し,タグ変数flagを増やしてこのアルゴリズムの改善を実現することができる.
コード:

void Bubble_Sort2(vector<int> &v)   //    
{
	int i, j;
	bool flag = true;
	for (i = 0; i < v.size() && flag == true; i++)
	{//                    ，flag=false，    ，    
		flag = false;
		for (j = 0; j < v.size() - i - 1; j++)
		{
			if (v[j]>v[j + 1])
			{
				int temp = v[j];
				v[j] = v[j + 1];
				v[j + 1] = temp;
				flag = true;
			}
		}
	}
}

Analysis:
部分的に秩序化されたシーケンスに適しています
1、時間複雑度
Worst-case:O(n^2)逆順
Best-case:O(n)が秩序化されたシーケンスであれば,改良されたコードに基づいてn-1回の比較である.
Average-case   O(n^2)
2、空間複雑度:O(1)
3、Stable Sort