插入排序---类似于扑克牌那般,每获取到新数值后,就按顺序排序。这种方式,在算法运行的过程中,就会产生,循环不变式和剩余参数。
循环不变式:循环第一次迭代之前,它为真;如果循环的某次迭代之前为真,那么下次迭代依旧为真;在循环终止时,不变式为我们提供一个有用的性质。
public static void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int j = i; while (j > 0 && arr[j] < arr[j - 1]) { swap(arr,j,j-1); j--; } } }
冒泡排序---顾名思义:从某一角度(最大或最小)浮出水面;取一数,按照某一方向相邻的两个数字进行比较,取最大或最小,直至遍历最后,故将那个数字“浮”出数组。其他数字以此类推。
public static void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { boolean flag = true;//设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已然完成。 for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { swap(arr,j,j+1); flag = false; } } if (flag) { break; } } }
选择排序:选择最大(最小)的数字,进行装箱排序。简单来说,任取两数对比留下最大数字,循环对比其他的数字,直至遍历结束后,剩下的数字为最大数字。故:选择最大的数字的排序方式。
public static void selectSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int min = i;//每一趟循环比较时,min用于存放较小元素的数组下标,这样当前批次比较完毕最终存放的就是此趟内最小的元素的下标,避免每次遇到较小元素都要进行交换。 for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[min]) { min = j; } } //进行交换,如果min发生变化,则进行交换 if (min != i) { swap(arr,min,i); } } }
分析算法:预算估计运行算法所需要的内存,通信带宽或计算机这种硬件设施。所以关注点会放在--运行时间和输入规模
算术指令:加减乘除,取余,向上取整,向下取整
数据移动:装入,存储,复制
控制指令:条件与无条件转移,子程序的调用或返回
输入规模:数据量的大小,
运行时间:指执行的基本操作或步数。
算法的运行时间:执行每条语句的运行时间之和。
最坏情况分析:最坏情况分析给出了任何输入的运行时间的一个上界。
当数据量足够大时:我们真正感兴趣的是运行时间的增长率和增长量级。