冒泡排序及其優(yōu)化

冒泡排序的基本思路是（以升序為例）：每次將相鄰兩個數(shù)字進行比較，將小的數(shù)字放在大的前邊。例如已知六個數(shù)字為9,8,5,4,2,0，第一次現(xiàn)將最前邊的9和8進行調(diào)換，其次再將9和5進行調(diào)換......如圖（只進行了兩趟交換）

如此進行下去，如果有n個數(shù)，就要進行n-1趟比較；在第一趟要進行n-1次交換，在第j次就要進行n-j次交換。

void bubble_sort(int *p,int sz)              //冒泡排序
{
	int i = 0;
	int temp = 0;
	for(i=0; i<sz-1; i++)
	{
		int j = 0;
		for(j=0; j<sz-i-1; j++)
		{
			if(*(p+j) > *(p+j+1))
			{
				temp = *(p+j);
				*(p+j) = *(p+j+1);
				*(p+j+1) = temp;
			}
		}			
	}
}

假設(shè)有一組數(shù)字：1 2 3 4 5 6 7 8 9 0，那么用上邊的方法也是可以實現(xiàn)的，但是，對于前邊9個數(shù)字來說它們已經(jīng)是有序的了，如果還用這種方法就會使效率降低很多（假設(shè)有n個數(shù)），因此，在此基礎(chǔ)上可以將代碼優(yōu)化——每趟比較時，如果相鄰兩個數(shù)字之間滿足升序或者降序的要求，那就不在交換，如果不滿足，就前后交換。

void bubble_sort(int *p,int sz)              //冒泡排序--優(yōu)化
{
	int flag = 1;
	int i = 0;
	int temp = 0;
	for(i=0; i<sz-1; i++)
	{
		int j = 0;
		flag = 1;
		for(j=0; j<sz-i-1; j++)
		{
			if(*(p+j) > *(p+j+1))
			{
				temp = *(p+j);
				*(p+j) = *(p+j+1);
				*(p+j+1) = temp;
				flag = 0;
			}
		}			
		if(flag == 1)
		{
			return ;
		}
	}
}