Java基础算法-排序-冒泡排序

实现原理

冒泡排序是最基础的排序算法，就像水底的气泡一个个冒出来一样。
冒泡排序算法的运作如下：（从后往前）—-参考百科

  • 1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
  • 3.针对所有的元素重复以上的步骤，除了最后一个。
  • 4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

时间复杂度

总的来说，像冒泡排序最理想的时间复杂度为O(n)，这个是在本身数据有序的情况下，
最坏情况的事件复杂度是O(n^2),平均的时间复杂度也为O(n^2)，接下来让我们来看看java版本的代码实现吧：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class BubbleSort
{
	public static void main(String[] args){
		int[] num = {705,826,680,654,694};
		int temp;//临时变量
		//第一个循环控制比较的轮数
		for(int i = 0;i < num.length - 1;i++){
			//第二个循环控制每轮比较的次数
			for(int j = 0;j < num.length - 1 - i; j++){
				if(num[j] > num[j + 1]){
					temp = num[j];
					num[j] = num[j + 1];
					num[j + 1] = temp;
				}
			}
		}
		System.out.println("使用冒泡排序后的数列是");
		for(int i = 0; i< num.length; i++){
			System.out.println(num[i]+" " );
		}
	}
}
输出以及过程如下：
/*
705,826,680,654,694
705,680,654,694,826  第一轮
680,654,694,705,826  第二轮
654,680,694,705,826
654,680,694,705,826
*/

最简单的也是基础的也是最会被问的，与诸君共勉。

Algorithms
算法基础