上学期间,最不用功的一门课就是数据结构与算法,现在后悔了! 数据结构和算法这个东西,如果你不去学,可能真的这辈子都用不到,也感受不到它的好。但是一旦掌握,你就会常常被它的强大威力所折服。之前你可能需要费很大劲儿来优化的代码,需要花很多心思来设计的架构,用了数据结构和算法之后,很容易就可以解决了。 我准备开一个“数据结构与算法”的话题,来补上学时的遗憾!先从排序算法开始!
排序是一个非常经典的问题,它以一定的顺序对一个数组(或一个列表)中的项进行重新排序(可以进行比较的,例如整数,浮点数,字符串等)。
有许多不同的排序算法,每个都有其自身的优点和局限性。
基于比较的排序算法:
它们比较数组的元素并决定是否交换它们
不基于比较的排序算法:
我们来逐一破解这些排序算法。
本文分析冒泡排序、选择排序和插入排序。
假设数组arr长度为N,冒泡排序的过程为:
在arr[0~N-1]范围上:
在arr[0~N-2]范围上,重复上面的过程,但最后一步是arr[N-3]和arr[N-2],谁大谁来到N-2位置
在arr[0~N-3]范围上,重复上面的过程,但最后一步是arr[N-4]和arr[N-3],谁大谁来到N-3位置
…
最后在arr[0~1]范围上,重复上面的过程,但最后一步是arr[0]和arr[1],谁大谁来到1位置
整个过程将最大的元素移动到最右侧,也就是最大的元素浮动到最右边,像冒泡一样。
如图所示:
冒泡排序
如图展示了第1趟排序的过程。
自己会动的才是好图:
冒泡排序动画演示
代码实现:
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};
sort(arr);
}
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//想要让0~i位置上有序,i一开始在数组的最大索引位置上,每比完1次,减1
for (int i = arr.length - 1; i > 0; i--) {
//0~i
//0~(i-1)
//0~(i-2)...
//0~1
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("0~" + i + "位置比较结果:" + Arrays.toString(arr));
}
}
}
执行结果:
第0趟比较结果:[15, 13, 17, 6, 18, 15, 9, 20]
第1趟比较结果:[13, 15, 6, 17, 15, 9, 18, 20]
第2趟比较结果:[13, 6, 15, 15, 9, 17, 18, 20]
第3趟比较结果:[6, 13, 15, 9, 15, 17, 18, 20]
第4趟比较结果:[6, 13, 9, 15, 15, 17, 18, 20]
第5趟比较结果:[6, 9, 13, 15, 15, 17, 18, 20]
第6趟比较结果:[6, 9, 13, 15, 15, 17, 18, 20]
第7趟比较结果:[6, 9, 13, 15, 15, 17, 18, 20]
时间复杂度的计算:
比较和交换需要一个以常量为界的时间,我们称之为c。
Bubble Sort中有两个嵌套循环。
外循环正好运行N次迭代。但内部循环运行变得越来越短:
当 i = 0,(N-1)次迭代(比较和可能交换)时。
当 i = 1,(N-2)次迭代时,...
当 i =(N-2)时,1次迭代,
当 i=(N-1),0迭代.
因此,总迭代次数=(N-1)+(N-2)+ ... + 1 + 0 = N ×(N-1)/ 2
总时间= c × N ×(N-1)/ 2 = O(N²)。
给定 N 个元素和 L = 0 的数组,选择排序过程为:
手绘选择排序过程:
手绘选择排序过程
动画演示:
选择排序动画演示
代码实现:
public class SelectionSort {
public static void main(String[] args) {
int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};
sort(arr);
}
public static void sort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
//目的:找到最小值的位置,并将该位置的数与i位置的数交换
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[j] > arr[minIndex] ? minIndex : j;
}
//找到最小值后,与i位置的数交换
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
System.out.println("第" + i + "~" + (arr.length - 1) + "位置上的最小值索引为" + minIndex + ",最小值为:" + arr[minIndex] + ",本次排序结果:" + Arrays.toString(arr
));
}
}
}
运行结果:
第0~7位置上的最小值索引为4,最小值为:18,本次排序结果:[6, 15, 13, 17, 18, 20, 15, 9]
第1~7位置上的最小值索引为7,最小值为:15,本次排序结果:[6, 9, 13, 17, 18, 20, 15, 15]
第2~7位置上的最小值索引为2,最小值为:13,本次排序结果:[6, 9, 13, 17, 18, 20, 15, 15]
第3~7位置上的最小值索引为7,最小值为:17,本次排序结果:[6, 9, 13, 15, 18, 20, 15, 17]
第4~7位置上的最小值索引为6,最小值为:18,本次排序结果:[6, 9, 13, 15, 15, 20, 18, 17]
第5~7位置上的最小值索引为7,最小值为:20,本次排序结果:[6, 9, 13, 15, 15, 17, 18, 20]
第6~7位置上的最小值索引为6,最小值为:18,本次排序结果:[6, 9, 13, 15, 15, 17, 18, 20]
总结一下选择排序的过程:
arr[0~N-1]范围上,找到最小值所在的位置,然后把最小值交换到0位置。
arr[1~N-1]范围上,找到最小值所在的位置,然后把最小值交换到1位置。
arr[2~N-1]范围上,找到最小值所在的位置,然后把最小值交换到2位置。
…
arr[N-1~N-1]范围上,找到最小值位置,然后把最小值交换到N-1位置。
估算:很明显,如果arr长度为N,每一步常数操作的数量,如等差数列一般,所以,总的常数操作数量 = a*(N²) + b*N + c (a、b、c都是常数)
所以选择排序的时间复杂度为O(N²)。
这个算法比较好理解,想像一下平时打扑克牌,我们很自然的就会把一张牌和手里的牌挨个比较一下,并把它插入到合适的位置。
扑克牌插入排序
过程:
…
估算时发现这个算法流程的复杂程度,会因为数据状况的不同而不同。
如果某个算法流程的复杂程度会根据数据状况的不同而不同,那么必须要按照最差情况来估计。
很明显,在最差情况下,如果arr长度为N,插入排序的每一步常数操作的数量,还是如等差数列一般。
所以,总的常数操作数量 = a*(N²) + b*N + c (a、b、c都是常数)
所以插入排序排序的时间复杂度为O(N²)。
代码实现:
public class InsertionSort {
public static void main(String[] args) {
int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};
sort(arr);
}
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//想让0~i位置上有序,从i位置往前看,一直到左边的数不比自己大了,停止往左看
for (int i = 1; i < arr.length; i++) {
//j=i表示从i位置开始,j--表示往前看
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
System.out.println("从" + i + "位置往前看,直到左边的数不比自己大,本次结果:" + Arrays.toString(arr));
}
}
}
运行结果:
从1位置往前看,直到左边的数不比自己大,本次结果:[15, 18, 13, 17, 6, 20, 15, 9]
从2位置往前看,直到左边的数不比自己大,本次结果:[13, 15, 18, 17, 6, 20, 15, 9]
从3位置往前看,直到左边的数不比自己大,本次结果:[13, 15, 17, 18, 6, 20, 15, 9]
从4位置往前看,直到左边的数不比自己大,本次结果:[6, 13, 15, 17, 18, 20, 15, 9]
从5位置往前看,直到左边的数不比自己大,本次结果:[6, 13, 15, 17, 18, 20, 15, 9]
从6位置往前看,直到左边的数不比自己大,本次结果:[6, 13, 15, 15, 17, 18, 20, 9]
从7位置往前看,直到左边的数不比自己大,本次结果:[6, 9, 13, 15, 15, 17, 18, 20]
看完点赞,养成习惯。 举手之劳,赞有余香。