【アルゴリズム導論】バブルソート法

バブルソートほう
時間複雑度:O(n*n)
基本思想:配列の最後の要素から、前の要素と順番に比較し、前の要素より小さい場合は位置を交換し、現在の前の要素と比較して、それより大きい要素に出会うまで比較します.例えば、配列をa[5]={3,4,2,5,1}と仮定する.演算過程は、まず1と5を比較し、1<5により位置を交換し、配列がa[5]={3,4,2,1,5}になる.そして1は、現在の前の要素2と比較して、上記の操作を繰り返し、1サイクル経過すると、配列はa[5]={1,3,4,2,5}となる.2回目のサイクルは逆数の2番目の要素から・・・、合計n-1回で正しい結果が得られる.総じて,まず最小の要素を配列の前に配置し,次に最小の要素を配置する.上記の手順は、
3
4
2
5
1
3
4
2
1
5
3
4
1
2
5
3
1
4
2
5
1
3
4
2
5
注意:ここの赤は比較する要素です.
具体的には、次のようになります.

#include<stdio.h>

void BubbleSort(int* arrayA,int n);

void main()
{
	int arrayA[]={2,3,5,6,2,7,1,5};
	int n=sizeof(arrayA)/sizeof(int);

	BubbleSort(arrayA,n);

	for(int i=0;i<n;i++)
		printf("%d ",arrayA[i]);
}

void BubbleSort(int* arrayA,int n)
{
	for(int i=0;i<n-1;i++)
	{
		for(int j=n-1;j>i;j--)//j>i               
		{
			int temp=0;
			if(arrayA[j]<arrayA[j-1])
			{
				temp=arrayA[j];
				arrayA[j]=arrayA[j-1];
				arrayA[j-1]=temp;
			}
			

		}	
	}
}

注意:私はvs 2008で実行して、vc 6.0と少し異なって、主に循環体の中の循環変数の作用域で、間違いは循環変数の繰り返し定義に現れます.たとえば、vs 2008またはvs 2010では、プログラムは次のとおりです.
#include void main() { int i=0; for(int i=0;i<5;i++) printf("%d ",i); }
VC 6.0では、次のように変更する必要があります.
#include void main() { int i=0; for(i=0;i<5;i++) printf("%d ",i); }　
原文:http://blog.csdn.net/tengweitw/article/details/9707525
作者:nineheadedbird