前言
最近编程状态很自由，我挺喜欢这种感觉。不过还是要给自己制定一个计划，每天学习一小节《
Java数据结构与算法》和看一小节刘宇波老师的《数据结构与算法》视频，还有就是学习Spring Boot项目课程。然后每天晚上的时候，写一篇简书总结自己一天回顾的知识。
从简单的冒泡排序开始
冒泡排序算法运行起来十分慢，但在概念上它是排序算法中最简单的，因此冒泡排序算法在开始研究排序技术时是一个非常好的算法。
什么是冒泡排序?
对几个无序的数字进行排序，最常用的方法是所谓的冒泡排序。算法思想是每次比较2个相邻的数字，将小的放在前面，将较大的放在后面，这样就可以将这些数中最大的找出来放在到最后。然后再比较剩下的数字，再在这些数字中找出最大的，直到所有的数字按照从小到大的顺序进行排序。
提炼思想
-
在算法执行的时候，最大的数据项总是冒泡到数据的顶端。
-
假如有
N个数字需要进行排序，在对所有的数字进行了第一趟排序之后，进行了N - 1次比较，并且按照数字之间的初始位置，进行了最少0次，最多N - 1次交换，数组最末端的数据项就此排定。 -
我们进行第二趟排序的时候，再一次地从左到右，两两比较，并且在适当的时候交换数字之间的顺序，这一次只需要比较到右边第二个数字(位置
N - 2)就行了，因为最大的数字已经到了最后位置，既N - 1号位置。
开始练手
- 只有把思路理清楚了，才能开始写代码。
public class BubbleSortDemo {
public static int[] a = { 2, 4, 6, 8, 3, 6, 9, 12 };
public static void main(String[] args) {
sort();
display();
}
public static void sort() {
int count = a.length;
for (int i = 0; i < count - 1; i++) {
for (int k = 0; k < count - 1 - i; k++) {
if (a[k] > a[k + 1]) {
swap(k, k + 1);
}
}
}
}
public static void swap(int x, int y) {
int temp = a[x];
a[x] = a[y];
a[y] = temp;
}
public static void display() {
int count = a.length;
for (int i = 0; i < count; i++) {
System.out.print(a[i] + " ");
}
System.out.println("");
}
}
- 运行程序，看控制台输出结果。
image.png
性能优化
我们使用的是一个独立的swap()方法来执行交换操作的。它只是交换数组中的两个数据项的值，使用一个临时变量来存储第一个数据项的值，然后把第二项的值赋给第一项，之后再让第二项的值等于临时变量。实际上，使用一个独立的swap()方法不一定好，因为方法调用会增加一些额外的开销，如果写自己使用的排序程序，最好将交换操作这段代码直接放到程序中，这样可以提高一些速度。
冒泡排序的效率
-
我们发现在第一趟排序时进行了
9次比较，第二趟排序时进行了8次比较，以此类推，直到最后一趟进行了一次比较。那么10个数据项，一共就进行了9 + 8 + ... + 1 = 45次，也就是N * （N - 1）/ 2。如果初始数据项时逆序的时候，我们每次比较都需要交换。可以知道冒泡排序运行需要O(N^2)时间级别，这样速度是很慢的。 -
只要看到了一个循环嵌套在另一个循环中，就可以怀疑这个算法的运行时间为
O（N^2）级。
尾言
勿以善小而不为。
网友评论