本文是第一站,大战冒泡排序。你还在为每次写排序算法的时候发愁吗? 喝了本专栏,保证你能手撸冒泡排序。
原理:
比较两个相邻的元素,符合要求(看自己的需求是从小到大,还是从大到小)即交换两个元素的位置。
输入一个数组,按小到大顺序排列。
input:
[5,4,6,1,3,2]output:
[1,2,3,4,5,6]
咱们就以这个题为例子,来讲解和演示一下冒泡排序的过程。
初始值就是:
我们最终通过冒泡排序要得到的结果:
第一趟冒泡:
第1次:
5与4相比,5>4,所以换位置
第2次:
5与6相比,5< 6,所以不换位置
第3次:
6与1相比,6>1,所以换位置
第4次:
6与3相比,6>3,所以换位置
第5次:
6与2相比,6>2,所以换位置
第6次:
此时已经到达了第一趟的最后一个元素了,所以第一趟结束。
第一趟结束,得到第一趟冒泡的结果:
[4,5,1,3,2,6]
以此类推,最终就得到了:
[1,2,3,4,5,6]
例如有一个数组:A=[5,2,3];
1、第1次比较,首先比较第1和第2个数,(如果A[1]>A[2],则交换位置)将大的数放在后面,将小的数放在前面;
2、第2次比较,比较第2和第3个数,如果第2个大于第3个数,则交换位置。
…
以此类推,每一趟都减少一次。
注释的很清楚了,看明白应该是没问题的。
package 排序算法.冒泡排序;
import java.util.Arrays;
/**
* @Auther: truedei
* @Date: 2020 /20-6-2 20:15
* @Description:冒泡排序
*/
public class BubbleSort {
public static int[] sort(int A[]){
//一共冒泡A.length趟排序 如果有6个元素要排序,那么就需要6次
for (int i = 0; i < A.length; i++) {
//第二层循环为什么是(A.length -i -1)
// 减i是:每趟都忽略已经排好
// 减1是:每次一趟的每一次到最后一个元素了
for (int j = 0; j < A.length -i - 1 ; j++) {
//比较i和j+1
//例如有:[3,2,5,4,...] 现在遍历到第1个了,A[j]=3; A[j+1]=2
if(A[j] > A[j+1]){// 3 > 2 符合要求,则进入交换
int temp = A[j]; //定义一个临时变量,用于交换数据
A[j] = A[j+1];
A[j+1] = temp;
}
}
}
return A;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(sort(new int[]{3,9,4,1,6})));
}
}
运行之后,就可以得到结果:
[1, 3, 4, 6, 9]
上面这是从小到大排序的,下面这个是从大到小排序的:
只需要修改一下判断条件: if(A[j] < A[j+1]){ } 即可
package 排序算法.冒泡排序;
import java.util.Arrays;
/**
* @Auther: truedei
* @Date: 2020 /20-6-2 20:15
* @Description:冒泡排序
*/
public class BubbleSort {
public static int[] sort(int A[]){
//一共冒泡A.length趟排序 如果有6个元素要排序,那么就需要6次
for (int i = 0; i < A.length; i++) {
//第二层循环为什么是(A.length -i -1)
// 减i是:每趟都忽略已经排好
// 减1是:每次一趟的每一次到最后一个元素了
for (int j = 0; j < A.length -i - 1 ; j++) {
//比较i和j+1
//例如有:[3,2,5,4,...] 现在遍历到第1个了,A[j]=3; A[j+1]=2
if(A[j] < A[j+1]){// 3 < 2 符合要求,则进入交换
int temp = A[j]; //定义一个临时变量,用于交换数据
A[j] = A[j+1];
A[j+1] = temp;
}
}
}
return A;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(sort(new int[]{3,9,4,1,6})));
}
}
分析算法的时间复杂度,通常都是分析最坏的时间复杂度的情况。让程序在最坏的情况下,也能保证流畅的服务。这才是分析的目的。
对于冒泡排序的最坏的情况就是逆序的情况。
例如:[6,5,4,3,2,1]
每一次比较,都去交换元素
对于这个排序算法:在做分析的时候,通常不会把for循环拿出来做分析的
public static int[] sort(int A[]){
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A.length -i - 1 ; j++) {
//比较j和j+1
if(A[j] < A[j+1]){
int temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
}
return A;
}
而真正实现排序的是下面这段代码:
if(A[j] < A[j+1]){
int temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
就拿:[6,5,4,3,2,1] 来说
第一趟:
6与5比较,然后交换
6与4比较,然后交换
6与3比较,然后交换
6与2比较,然后交换
6与1比较,然后交换
第二趟:
5与4比较,然后交换
5与3比较,然后交换
5与2比较,然后交换
5与1比较,然后交换
第三趟:
4与3比较,然后交换
4与2比较,然后交换
4与1比较,然后交换
…
…
…
以此类推
元素比较的次数为:
(N−1)+(N−2)+(N−3)+...+2+1 (N-1)+(N-2)+(N-3)+...+2+1 (N−1)+(N−2)+(N−3)+...+2+1
= N∗(N−1)/2 N*(N-1)/2 N∗(N−1)/2 推导过后,得出冒泡排序时间复杂度是: O(N2) O(N^{2}) O(N2)
(1)O(1) 这个针对的是常数;对于一个N,不管这个N是如何增长,这个时间是不变的。
例如下面这些代码的时间复杂度都是O(1):
/**
* @Auther: truedei
* @Date: 2020 /20-6-2 22:01
* @Description:
*/
public class Test {
public static void main(String[] args) {
System.out.println("你好,我叫郑晖");
System.out.println("你好,我叫郑晖");
System.out.println("你好,我叫郑晖");
System.out.println("你好,我叫郑晖");
}
}
还有这种:
我有一个数组,我知道了我需要的这个数据所在的索引,然后去拿这个值,咋这种也是O(1)
/**
* @Auther: truedei
* @Date: 2020 /20-6-2 22:01
* @Description:
*/
public class Test {
public static void main(String[] args) {
String[] names = {"小明","小红","郑晖"};
System.out.println("你好,我叫"+names[2]);
}
}
O(n)是一个线性增长的。
经常用在for()循环当中
例如下面这种代码:
/**
* @Auther: truedei
* @Date: 2020 /20-6-2 22:01
* @Description:
*/
public class Test {
public static void main(String[] args) {
String[] names = {"小明","小红","郑晖"};
for (int i = 0; i < names.length; i++) {
System.out.println("你好,我叫"+names[i]);
}
}
}
是一个平方级的的增长。经常出现在两层for循环
。
例如本文所写的:
public static int[] sort(int A[]){
for (int i = 0; i < A.length; i++) {
for (int j = 0; j < A.length -i - 1 ; j++) {
.....
}
}
return A;
}
是一个立方级的增长。经常出现在遍历一个三层的for循环
中
for (...) {
for (...) {
for (...) {
.....
}
}
}
是一个对数级。
在二分查找法里就是O(lg n)
。
每次执行N是以一个倍数的形式是递减的:
比如第1次:1/2
比如第2次:1/4
比如第3次:1/8
比如第4次:1/16
…
快速的让N的规模变小。
在排序中经常见到的
指数级的
排序法 | 最差时间分析 | 平均时间复杂度 | 稳定度 | 空间复杂度 |
---|---|---|---|---|
冒泡排序 | O(n^2) | O(n^2) | 稳定 | O(1) |
快速排序 | O(n^2) | O(n*log2n) | 不稳定 | O(log2n)~O(n) |
选择排序 | O(n^2) | O(n^2) | 不稳定 | O(1) |
二叉树排序 | O(n^2) | O(n*log2n) | 不稳定 | O(n) |
插入排序 | O(n^2) | O(n^2) | 稳定 | O(1) |
堆排序 | O(n*log2n) | O(n*log2n) | 不稳定 | O(1) |
希尔排序 | O | O | 不稳定 | O(1) |
如果对你有帮助,可以分享给你身边的朋友。 水平有限,难免会有疏漏或者书写不合理的地方,欢迎交流讨论。 作者:
TrueDei
如果喜欢我的文章,还没看够可以关注我,我会用心写好每一篇文章。