八种排序算法总结之

C++版本

五种简单排序算法

1、 冒泡排序  【稳定的】

void

 BubbleSort( 

int

* a,

int

 Count )  

//

实现从小到大的最终结果

{

int

 temp;

for

(

int

 i=1; i<Count; i++)  

//

外层每循环一次，将最小的一个移动到最前面

for

(

int

 j=Count-1; j>=i; j--)

if

( a[j] < a[j-1] )    

{

temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;

}

}

现在注意，我们给出

O 方法的定义：

若存在一常量

K 和起点 n0，使当 n>=n0 时，有 f(n)<=K*g(n),则 f(n) = O(g(n))。（呵呵，不

要说没学好数学呀，对于编程数学是非常重要的！！！）
现在我们来看

1/2*(n-1)*n，当 K=1/2，n0=1，g(n)=n*n 时，1/2*(n-1)*n<=1/2*n*n=K*g(n)。

所以

f(n) =O(g(n))=O(n*n)。所以我们程序循环的复杂度为 O(n*n)。 

 
2、 交换排序    【稳定的】

void

 ExchangeSort( 

int

 *a,

int

 Count)

{

int

 temp;

for

(

int

 i=0; i<Count-1; i++)

for

(

int

 j=i+1; j<Count; j++)

if

( a[j] < a[i] )

{

temp = a[j];
a[j] = a[i];
a[i] = temp;

}

}

时间复杂度为

O(n*n)。

3、 选择法   【不稳定的】