在很多大厂的面试中,算法是最基本的要求,像基础的算法,冒泡,选择,插入等,基本上都会问到。 很多同学往往忽略了其重要程度,只注重编程语言,小编并不建议这样子,今天我们来梳理一下算法,汇总一下面试的一些基础算法。 冒泡排序原理:每次冒泡排序操作都会将相邻的两个元素进行比较,看是否满足大小关系要求,如果不满足,就交换这两个相邻元素的次序,一次冒泡至少让一个元素移动到它应该排列的位置,重复N次,就完成了冒泡排序。 代码实现: /*** 冒泡算法* @author:溪云阁* @date:2020年5月3日* 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。* 如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复n 次,* 就完成了 n 个数据的排序工作。*/public static void bubbleSort(Integer[] arr) {// 如果只有一个元素就不用排序了if (arr.length <= 1) {return;} else {// 打印排序后的数组System.out.println('排序前的数组:' + Arrays.toString(arr));for (int i = 0; i < arr.length; ++i) {// 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素,这个数组就已经是有序的了boolean flag = false;// 此处你可能会疑问的j<n-i-1,因为冒泡是把每轮循环中较大的数飘到后面,for (int j = 0; j < arr.length - i - 1; ++j) {// 数组下标又是从0开始的,i下标后面已经排序的个数就得多减1,总结就是i增多少,j的循环位置减多少if (arr[j] > arr[j + 1]) {// 即这两个相邻的数是逆序的,交换位置final int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;flag = true;}}if (!flag)// 没有数据交换,数组已经有序,退出排序break;}// 打印排序后的数组System.out.println('排序后的数组:' + Arrays.toString(arr));}} 选择排序原理:先遍历数组,然后找到一个最大或者最小的元素(这个看需要),把这个元素放到第一个位置,接着在剩余的数组中继续找,找到比第一个大或者小的元素,放到第二个位置,依次这样子做,从而完成排序。 代码实现:
插入排序原理:这个比较抽象,但是我来划分来辅助理解 一组无序序列{A1,A2,........An} 先取出A1,然后从A2与A1比较,比较完之后序列状况是{A1,A2}{A3..........An},这时候其中{A1,A2}就变成有序 然后取出A3 ,放到{A1,A2}有序序列合适位置,从而形成{A1,A2,A3}{A4........An} 重复这个过程,直到取出An放入{A1,A2........An-1}有序序列中 代码实现: /*** 插入排序* @author 溪云阁* @param ins* @return int[]* 一组无序序列{A1,A2,........An}* 先取出A1,然后从A2与A1比较,比较完之后序列状况是{A1,A2}{A3..........An},这时候其中{A1,A2}就变成有序* 然后取出A3 ,放到{A1,A2}有序序列合适位置,从而形成{A1,A2,A3}{A4........An}* 重复这个过程,直到取出An放入{A1,A2........An-1}有序序列中*/public static int[] insertSort(int[] ins) {for (int i = 1; i < ins.length; i++) {// 保存每次需要插入的那个数final int temp = ins[i];int j;for (j = i; j > 0 && ins[j - 1] > temp; j--) {// 把大于需要插入的数往后移动。最后不大于temp的数就空出来jins[j] = ins[j - 1];}// 将需要插入的数放入这个位置ins[j] = temp;}return ins;} 希尔排序原理:希尔排序是插入排序的改进版,它将数组按照约定的数量分成N列,对每一列执行插入排序,接着缩小步长,不断重复这过程,最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法。 代码实现:
归并排序原理:归并其实就是分而治之的思想,对于每一个数组,每个递归过程涉及三个步骤 1、分解::把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素. 2、治理::对每个子序列分别调用归并排序MergeSort, 进行递归操作 3、合并:合并两个排好序的子序列,生成排序结果. 代码实现: /*** 两路归并算法,两个排好序的子序列合并为一个子序列* @author 溪云阁* @param a* @param left* @param mid* @param right void*/public static void merge(int[] a, int left, int mid, int right) {// 辅助数组final int[] tmp = new int[a.length];// p1、p2是检测指针,k是存放指针int p1 = left, p2 = mid + 1, k = left;while (p1 <= mid && p2 <= right) {if (a[p1] <= a[p2])tmp[k++] = a[p1++];elsetmp[k++] = a[p2++];}while (p1 <= mid) {// 如果第一个序列未检测完,直接将后面所有元素加到合并的序列中tmp[k++] = a[p1++];}while (p2 <= right) {// 同上tmp[k++] = a[p2++];}// 复制回原素组for (int i = left; i <= right; i++) {a[i] = tmp[i];}}/*** 归并排序* @author 溪云阁* @param a* @param start* @param end void*/public static void mergeSort(int[] a, int start, int end) {// 当子序列中只有一个元素时结束递归if (start < end) {// 划分子序列final int mid = (start + end) / 2;// 对左侧的序列进行递归排序mergeSort(a, start, mid);// 对右侧的序列进行递归排序mergeSort(a, mid + 1, end);// 合并merge(a, start, mid, end);}} 快速排序原理:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。 代码实现:
|
|
来自: taotao_2016 > 《计算机》