慕课网《算法与数据结构》 Java 代码,虽然讲师已经给出最佳代码,仍然自己写一遍,帮助记忆。 同时放在了自己的博客上
O(n²) 时间复杂度 虽然时间复杂度相对较高,但是同样也有好处
- 编码相对简单
- 在某些情况下,这些算法反而更有效
- 可以从简单的方法中衍生出复杂的算法
- 作为子过程,经过修改变为复杂的算法
重要的思想:
逆序数:排序的过程就是消除逆序数的过程,所以逆序数的个数影响排序的性能(也可以从这个角度来思考排序的性能) - N个互异数的数组的平均逆序数是
$N(N-1)/4$ (数对的一半) - 通过交换相邻元素进行排序的任何算法平均都需要
$Ω(N^2)$ - 对于归并排序,归并过程中,可以一次消除多个逆序数,提高算法效率。
从未排序的数组中逐一选择最小的元素进行排序
KEY:寻找数组中最小的元素
大约需要
可以考虑对算法进行升级,不仅仅对整型进行排序,对浮点型甚至对对象进行排序(采用Comparable接口,然后通过compareto进行比较)
特点:
- 运行时间和输入无关(这样对于最开始就基本有序的数组就没有优势了)
- 数据移动最少
public class SelectionSort{
public static void SelectionSort(Comparable[] arr) {
int n = arr.length;
for (int i = 0; i < n; i++) {
int minindex = i;
//注意是从i+1开始的
for (int j = i + 1; j < n; j++) {
if(arr[j].compareTo(arr[minindxe]) < 0){
minindex = j;
}
}
swap(arr,minindex,i);
}
}
public static void swap(Object[] arr, int i, int j){
Object e = arr[i];
arr[i] = arr[j];
arr[j] = e;
}
}
优化前,一次遍历仅仅可以找到最小的排好序,优化后,一次遍历可以找到最小的以及最大的两个元素排好序
选择排序优化
插入排序由N-1趟排序组成。对于p到N-1趟,插入排序保证从位置0到位置p上的元素为已排状态。
KEY:比前面一个小就进行交换,否则结束这一次插入(比选择排序优秀的地方,可以提前结束)
- 平均情况下,插入排序需要$\frac{N^2}{4}$次比较与$\frac{N^2}{4}$次交换
- 逆序数思考维度,每一次交换都是在减少一个逆序数,那么就需要逆序数次交换。
- 对插入排序进行优化:之前的插入排序每一次插入都要进行很多次交换,然而每次交换都是三次赋值的时间,所以很浪费时间,这样可以牺牲一个时间复杂度,将要插入的元素跟之前的元素进行比较,但是先不交换,等到找到要交换的元素,再进行一次交换,这样每一次插入都只进行一次交换。
插入排序为$O(n^2)$,如果输入数组时反序的时候,复杂度为$\Theta(N^2)$,如果输入已经预先排序,那么复杂度为$O(N^2)$。正因如此如果输入几乎被排序,那么插入排序将运行的更快。
它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
冒泡排序
- 希尔排序通过比较一定间隔的元素来工作,,各趟比较所用的距离随着算法的进行而减小,知道只比较相邻元素的最后一趟排序为止。
-
$h_k$ 排序的一般做法是,对于$h_k$,$h_{k+1}$,···$N-1$中的每一个位置i,把其上的元素放到i,$i-h_k$,$i-2h_k$,···中的正确位置上。
- 希尔排序的一个重要性质就是一个$h_k$排序的文件保持它的$h_k$排序性(我的理解就是,经过$h_k$排序后,逆序对不会再增加)
- 使用希尔增量时希尔排序的最坏情形运行时间为$\Theta(N^2)$
O(nlgn)复杂度的排序算法
分治算法的思想(分而治之)
归并排序 重点在合(如何合)
快速排序 重点在分(如何分)
KEY:将两个有序的数组合并为一个有序的数组
牺牲了存储空间,获得了时间上的减少。
首先进行分层,然后对每一层使用归并排序
归并排序的逻辑 递归的思想,这也是递归的一个很好的例子。对于递归的效率分析也是一个很好的技巧(叠缩求和与带入法)
优化:
- 对近乎有序的数组进行优化要判断要不要进行归并
- 由于对于小数据量的元素使用插入排序更加迅速, 所及可以考虑分层进行到一部分的时候改用插入排序(一部分是怎么确定的?)
不使用递归,只用迭代性能相对来说要差一点点
并没有使用到数组的特性(通过下标寻找元素),所以对于链表很适用。
对于数组要思考到越界的问题
自底向上归并排序
key:如何将数组分为大小两个(Partition)
递归思想,分别使用快速排序
围绕着枢纽元进行大小分离,不进行排序,只区分大小
性能测试 针对两种数组,快速排序的表现
- 对递归的理解很关键,通过运用归并排序的方法,使得求逆序数的复杂度变为
$O(nlogn$ )
求逆序数个数 归并排序 - 如果利用先排序再找到第n个最大值,那么这个算法的复杂度为$O(nlogn)$,但是利用快速排序的思想可以很好的解决这个问题,使得复杂度变为$O(n)$
取出数组中第n大的元素 快速排序