现在IT这块找工作,不会几个算法都不好意思出门,排序算法恰巧是其中最简单的,我接触的第一个算法就是它,但是你知道怎么分析一个排序算法么?有很多时间复杂度相同的排序算法,在实际编码中,那又如何选择呢?下面我们带着问题一起学习一下。
归并排序
快速排序
冒泡排序
选择排序
计数排序
计数排序
堆排序
从三个方面入手
算法消耗可以通过空间复杂度来衡量
原地排序算法:特指空间复杂度是O(1)的排序算法。
默认从小到大未有序
逆序度=满有序度-有序度排序的过程实际上就是增加有序度,减少逆序度的过程
// 冒泡排序,a 表示数组,n 表示数组大小
public void bubbleSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 0; i < n; ++i) {
// 提前退出冒泡循环的标志位
boolean flag = false;
for (int j = 0; j < n - i - 1; ++j) {
if (a[j] > a[j+1]) { // 交换
int tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag = true; // 表示有数据交换
}
}
if (!flag) break; // 没有数据交换,提前退出
}
}
将数据分为两个区间,已排序区间和未排序区间,初始已排序区间只有一个元素(即第一个数据),我们取未排序区间的元素,在已排序的区间中找到合适的位置插入位置插入,并保证已排序区间数据一直有序,重复过程,直到未排序区间中没有元素
运行过程中看得出来,不需要额外的存储空间,所以空间复杂度为0(1),也是原地排序算法
同样值的元素,前后顺序保持不变,是稳定的排序算法
时间复杂度:
最好时间复杂度为O(n)
最坏时间复杂度为O(n2)
平均时间复杂度为O(n2)
代码实现:
// 插入排序,a 表示数组,n 表示数组大小
public void insertionSort(int[] a, int n) {
if (n <= 1) return;
for (int i = 1; i < n; ++i) {
int value = a[i];
int j = i - 1;
// 查找插入的位置
for (; j >= 0; --j) {
if (a[j] > value) {
a[j+1] = a[j]; // 数据移动
} else {
break;
}
}
a[j+1] = value; // 插入数据
}
}
大家不妨试着分析一下其他的几种算法。
看再多遍都不如写一篇来得深刻,建议大家多敲。
以上内容为个人的学习笔记,仅作为学习交流之用。
欢迎大家关注公众号,不定时干货,只做有价值的输出
作者:Dawnzhang
出处:https://www.cnblogs.com/clwydjgs/p/9815690.html
版权:本文版权归作者
转载:欢迎转载,但未经作者同意,必须保留此段声明;必须在文章中给出原文连接;否则必究法律责任
原文:https://www.cnblogs.com/clwydjgs/p/9815690.html