Java算法学习笔记之冒泡排序

—、最基础的排序——冒泡排序 

冒泡排序是许多人最早接触的排序算法,由于逻辑简单,所以大量的出现在计算机基础课本上,作为一种最基本的排序算法被大家所熟知。

设无序数组a[]长度为N,以由小到大排序为例。冒泡的原理是这样的: 

1.比较相邻的前两个数据,如果前面的数据a[0]大于后面的数据a[1] (为了稳定性,等于不交换),就将前面两个数据进行交换。在将计数器 i ++; 

2.当遍历完N个数据一遍后,最大的数据就会沉底在数组最后a[N-1]。 

3.然后N=N-1;再次进行遍历排序将第二大的数据沉到倒数第二位置上a[N-2]。再次重复,直到N=0;将所有数据排列完毕。

1 无序数组:25471683

2 遍历1次后:24516738

3 遍历2次后:24156378

4   ...

5 遍历7次后:12345678

可以轻易的得出,冒泡在 N– 到 0 为止,每遍近似遍历了N个数据。所以冒泡的时间复杂度是 -O(N^2)。

按照定义实现代码如下:

Java算法学习笔记之冒泡排序_第1张图片

你可能感兴趣的