算法-冒泡排序

发表于 | 分类于

算法第二篇

冒泡排序

冒泡排序呢是使用得很广泛的一种排序方式，它是让要排序的数每次比较相邻的数，如果位置错误就把他们交换顺序，最终找到每个数合适的位置。首先第一轮的时候让第一个数和第二个数比较，直至找到最小的数，放在最后一位，第二轮还是从第一个数开始，不过不用比较最后一位与倒数第二位了，因为最后一位已经是最小的了，到倒数第二位的已经是第二小的了，所以依次的比较，直至将顺序排好
下面是算法的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int a[100],i,j,t,n;
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
for(i = 1;i <= n-1;i++){
	a[i] = scan.nextInt();
}
for(i = 1;i <= n - 1;i++){
	for(j = 1; j <= n - i;j++){
		if(a[j] < a[j + 1]){
			t = a[j];
			a[j] = a[j + 1];
			a[j + 1] = t;
		}
	}
}
for(i = 1;i <= n - 1;i++){
	System.out.print(a[i]);
}

这个算法的核心是这个嵌套循环，还有就是要想清楚为什么是i < n - 1，由于是一个一个得到数，因此当到达第i个数是只需要比较n - i个数就可以了，再往后比较就是多余的了。这个算法的时间复杂度为O(n^2),这是一个时间复杂度非常高的算法，因此这个算法的研究价值不是很大，是一个很有用的基础算法。