c 是用来做网站的吗,自己怎么制作图片,网上申报食品经营许可证流程,深圳燃气公司待遇文章目录 前言一、排序1. 冒泡排序2. 选择排序3. 插入排序4. 快速单边循环排序5. 快速双边循环排序6. 二分查找 二、集合1.List2.Map 前言
提示#xff1a;以下是本篇文章正文内容#xff0c;下面案例可供参考
一、排序
1. 冒泡排序 冒泡排序就是把小的元素往前调或者把大… 文章目录 前言一、排序1. 冒泡排序2. 选择排序3. 插入排序4. 快速单边循环排序5. 快速双边循环排序6. 二分查找 二、集合1.List2.Map 前言
提示以下是本篇文章正文内容下面案例可供参考
一、排序
1. 冒泡排序 冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较交换也发生在这两个元素之间。所以如果两个元素相等是不会再交换的如果两个相等的元素没有相邻那么即使通过前面的两两交换把两个相邻起来这时候也不会交换所以相同元素的前后顺序并没有改变所以冒泡排序是一种稳定排序算法。 时间复杂度On²
public class BubbleSort {/*** 冒泡排序* 1. 比较相邻的元素。如果第一个比第二个大就交换他们两个。* 2. 对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对。在这一点最后的元素应该会是最大的数。* 3. 针对所有的元素重复以上的步骤除了最后一个。* 4. 持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较*/Testpublic void bubbleSortDemo() {Integer[] array {1, 12, 6, 19, 18, 9, 66, 89};for (int i 0; i array.length - 1; i) {boolean mark false; //标记是否有交换数据如果没有交换数据则表明数组已是有序数组无需再进行排序for (int j 0; j array.length - 1 - i; j) {if (array[j] array[j 1]) {int temp array[j];array[j] array[j1];array[j1] temp;mark true ;}}if(!mark){//没有交换数据则表明数组已是有序数组无需再进行排序break;}System.out.println(Arrays.toString(array));}
// System.out.println(Arrays.toString(array));}/*** 冒泡排序加强版* 记录最后一次交换索引的位置**/Testpublic void bubbleSortPlusDemo() {Integer[] array {1, 12, 6, 19, 18, 9, 66, 89};int lastIndex array.length - 1;while (true) {int index 0;for (int j 0; j lastIndex; j) {System.out.println(array : Arrays.toString(array) ::: j);if (array[j] array[j 1]) {int temp array[j];array[j] array[j1];array[j1] temp;//记录最后一次交换索引的位置index j;}}//记录最后一次交换索引的位置lastIndex index;if(lastIndex0){break;}System.out.println(Arrays.toString(array));}
// System.out.println(Arrays.toString(array));}
}2. 选择排序 选择排序Selection sort是一种简单直观的排序算法。它的工作原理是第一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置然后再从剩余的未排序元素中寻找到最小大元素然后放到已排序的序列的末尾。以此类推直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法 最好复杂度O(n^2) 最差复杂度O(n^2)
public class SelectionSort {/*** 选择排序 是一种简单直观的排序算法。* 1. 第一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置* 2. 再从剩余的未排序元素中寻找到最小大元素然后放到已排序的序列的末尾。* 3. 以此类推直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法*/Testpublic void selectionSortDemo() {Integer[] array {1, 12, 6, 19, 18, 9, 66, 89};for (int i 0; i array.length; i) {int tempIndex i;//用于记录最小索引for (int j i; j array.length; j) {//判断最小值if(array[tempIndex] array[j]){tempIndex j; // 获取最小索引}}//与最小索引进行替换int temp array[i];array[i] array[tempIndex];array[tempIndex] temp;}System.out.println(Arrays.toString(array));}
}
3. 插入排序 插入排序一般也被称为直接插入排序。对于少量元素的排序它是一个有效的算法 。 插入排序是一种最简单的排序方法它的基本思想是将一个记录插入到已经排好序的有序表中从而一个新的、记录数增1的有序表。在其实现过程使用双层循环外层循环对除了第一个元素之外的所有元素内层循环对当前元素前面有序表进行待插入位置查找并进行移动 空间复杂度O(1) 时间复杂度O(N^(1-2))
public class InsertionSort {/*** 插入排序* 将数组分为两个区域排序区和未排序区每一轮从未排序区选取第一个元素与排序区做对比直到对比结束。默认第一个是排序好的* 例[6, 5, 2]* 1. 默认6是排序好的5是未排序的 --- 65 交换位置 --[5, 6, 2]* 2. 56是排序好的2是未排序的 --- 26 6往后移一位然后2还要与5比较 25 --》[2 5 6] 直到2找到合适位置*/Testpublic void insertionSortDemo() {Integer[] array {1, 12, 6, 19, 18, 9, 66, 89};for (int i 1; i array.length; i) {//默认第一个是排序好的所以要从索引为1的位置开始int insertVal array[i]; // 待插入的值int index i - 1; //待比较的索引while (index 0) {if (insertVal array[index]) {//如果待插入的值比前面的值小array[index 1] array[index]; //那么比较的值往后移一位index--;}else{break;}}//插入值array[index 1] insertVal;System.out.println(Arrays.toString(array));}
// System.out.println(Arrays.toString(array));}Testpublic void insertionSortDemo02() {Integer[] array {1, 12, 6, 19, 18, 9, 66, 89};for (int i 1; i array.length; i) {for (int j i - 1; j 0; j--) {if (array[j 1] array[j]) {int temp array[j 1];array[j 1] array[j];array[j] temp;} else {break;}}System.out.println(Arrays.toString(array));}
// System.out.println(Arrays.toString(array));}
}
4. 快速单边循环排序 快速排序采用的是分治思想即在一个无序的序列中选取一个任意的基准元素pivot利用pivot将待排序的序列分成两部分前面部分元素均小于或等于基准元素后面部分均大于或等于基准元素然后采用递归的方法分别对前后两部分重复上述操作直到将无序序列排列成有序序列 public class QuickSort {Testpublic void quickSortDemo() {Integer[] array {1, 12, 6, 19, 18, 9, 66, 89};recursionQuickSort(array, 0, array.length - 1);System.out.println(Arrays.toString(array));}/*** 递归调用** param array* param startIndex* param endIndex*/public void recursionQuickSort(Integer[] array, Integer startIndex, Integer endIndex) {if (startIndex endIndex) {//如果起始边界大于等于结束边界 结束递归return;}//获取基准点的索引位置此时比基准点小的全在左侧比基准点大的全在右侧,可以分而治之Integer pvIndex quickSort(array, startIndex, endIndex);//分而治之--对基准点左侧元素递归调用recursionQuickSort(array, startIndex, pvIndex - 1);//分而治之--对基准点右侧元素递归调用recursionQuickSort(array, pvIndex 1, endIndex);}/*** 单边循环快速排序----基准点选择最右侧得元素* 1. 选择右侧元素做为基准点* 2. I 指针维护小于基准点的边界也就是每次交换的目标索引* 3. J 指针负责找到比基准点小的元素一旦找到则与 I 索引交换* 4. 最后交换基准点与 I 交换 因为基准点选择是的右侧的, I 一定是大于基准点的所以大于基准点的放在右** param array*/public int quickSort(Integer[] array, Integer startIndex, Integer endIndex) {int pv array[endIndex];//设置基准点 基准点选择最右侧得元素int j startIndex; //设置比基准点小的元素索引for (int i startIndex; i endIndex; i) {if (array[i] pv) { //如果当前元素比基准点小 那么将当前元素与基准点大的元素进行交换int temp array[i];array[i] array[j];array[j] temp;j; //默认比基准点小的元素索引为0一旦发现比基准点小的元素就与J交换位置,此时就能保证比基准点小的元素全在基准点的左侧}}//调换基准点元素因为基准点选择的是最右侧得元素所以与 j(此时的j是后的) 互换位置换过去的一定是大于基准点的元素array[endIndex] array[j];array[j] pv;
// System.out.println(Arrays.toString(array));return j;}
}5. 快速双边循环排序 快速排序采用的是分治思想即在一个无序的序列中选取一个任意的基准元素pivot利用pivot将待排序的序列分成两部分前面部分元素均小于或等于基准元素后面部分均大于或等于基准元素然后采用递归的方法分别对前后两部分重复上述操作直到将无序序列排列成有序序列 public class QuickSort {Testpublic void quickSortDemo() {Integer[] array {1, 12, 6, 19, 18, 9, 66, 89};recursionQuickSort(array, 0, array.length - 1);System.out.println(Arrays.toString(array));}/*** 递归调用** param array* param startIndex* param endIndex*/public void recursionQuickSort(Integer[] array, Integer startIndex, Integer endIndex) {if (startIndex endIndex) {//如果起始边界大于等于结束边界 结束递归return;}//获取基准点的索引位置此时比基准点小的全在左侧比基准点大的全在右侧,可以分而治之Integer pvIndex quickSort(array, startIndex, endIndex);//分而治之--对基准点左侧元素递归调用recursionQuickSort(array, startIndex, pvIndex - 1);//分而治之--对基准点右侧元素递归调用recursionQuickSort(array, pvIndex 1, endIndex);}/*** 双边循环快速排序----基准点选择最左侧的元素* 1. 选择左侧元素做为基准点* 2. rl指针负责从右向左找比基准点小的元素lr指针负责从左向右找比基准点大的元素。* 3. 一旦找到二者交换 直到 rl lr 说明两个指针重合结束循环* 4. 最后交换基准点位置** param array*/public int quickSort(Integer[] array, Integer startIndex, Integer endIndex) {Integer pv array[startIndex]; //确定基准点--以最左侧为基准点Integer lrIndex startIndex;//确定比基准点大的索引--》左-右Integer rlIndex endIndex;//确定比基准点小的索引--》右-左while (rlIndex lrIndex) {//从右向左找比基准点小的索引while (rlIndex lrIndex pv array[rlIndex]) {rlIndex--;}//从左向右找比基准点大的索引while (rlIndex lrIndex pv array[lrIndex]) {lrIndex;}//互换位置int temp array[lrIndex];array[lrIndex] array[rlIndex];array[rlIndex] temp;}//基准点换位置array[startIndex] array[rlIndex];array[rlIndex] pv;return rlIndex;}
}
6. 二分查找 折半查找法也称为二分查找法它充分利用了元素间的次序关系采用分治策略可在最坏的情况下用O(log n)完成搜索任务。它的基本思想是这里假设数组元素呈升序排列将n个元素分成个数大致相同的两半取a[n/2]与欲查找的x作比较如果xa[n/2]则找到x算法终止如 果xa[n/2]则我们只要在数组a的左半部继续搜索x如果xa[n/2]则我们只要在数组a的右 半部继续搜索x。 public class BinarySearch {Testpublic void binarySearchDemo() {//二分查找默认有序数组Integer[] array {1, 6, 9, 12, 18, 19, 66, 89};//调用二分查找方法int index binarySearch(array, 0, array.length, 12);System.out.println(index);}/*** 二分查找* 折半查找法也称为二分查找法它充分利用了元素间的次序关系采用分治策略可在最坏的情况下用O(log n)完成搜索任务。* 它的基本思想是这里假设数组元素呈升序排列将n个元素分成个数大致相同的两半取a[n/2]与欲查找的x作比较如果xa[n/2]则找到x* 算法终止如 果xa[n/2]则我们只要在数组a的左半部继续搜索x如果xa[n/2]则我们只要在数组a的右 半部继续搜索x。** param array* param leftRange 左边界* param rightRange 右边界* param target 目标元素* return*/public int binarySearch(Integer[] array, Integer leftRange, Integer rightRange, Integer target) {while (rightRange leftRange) {//获取中间索引位置 防止整数溢出int middleIndex (leftRange rightRange) 1; // 第一种解决办法//推导middleIndex (leftRange rightRange)/2 leftRange - leftRange/2 rightRange/2 leftRange (rightRange - leftRange) / 2;
// int middleIndex leftRange (rightRange - leftRange) / 2; // 第二解决办法if (array[middleIndex] target) {//中间值与目标值正好相等return middleIndex;} else if (array[middleIndex] target) {//中间值小于目标值leftRange middleIndex 1; // 设置左边界} else if (array[middleIndex] target) {//中间值大于目标值rightRange middleIndex - 1;// 设置右边界}}return -1;}
}
二、集合
1.List
深入了解Collection的实现类
1. ArrayList扩容机制 ArrayList是懒惰扩容机制即没有添加元素前即使指定了容量也不会真正创建数组add(E e)首次扩容为10非首次扩容为上次数组长度的1.5倍addAll(Collection? extends E c) 首次扩容会将默认长度10与集合长度做对比那个大用哪个非首次扩容会对比原容量的1.5倍与集合长度做对比那个大用哪个。 2. ArrayList遍历时可以修改集合吗 ArrayList是 fail-fast 的典型代表遍历时不可以修改集合。在遍历时会拿到集合的长度如果集合增加或减少那么长度就会改变遍历时发现长度变化则会直接报错。 CopyOnWriteArrayList是 fail-safe 的典型代表,遍历时可以修改集合。在遍历时会复制集合当集合被修改时会创建新的集合不会影响遍历的集合 3. ArrayList 和 LinkedList的区别 ArrayList的底层是数组内存是连续的可以利用cpu缓存。 LinkedList的底层是双向链表内存无需连续。ArrayList基于索引的随机访问效率高基于内容的随机访问效率和 LinkedList一样都需要从头开始遍历。ArrayList的尾部插入删除速度快无需移动数组越靠近头部的插入删除越慢因为需要移动数组。LinkedList头尾插入删除性能高。中间插入删除效率低主要因为从头遍历比较耗时。 2.Map
1. Map 1,7 和 1.8有何不同 1.7底层使用数组链表 1.8底层使用数组链表或红黑树 2. 为何使用红黑树为何不直接用红黑树 防止链表长度超长时影响性能所以使用红黑树。树化是一种偶然情况是用来防止攻击的。正常情况下在负载因子为0.75.链表长度为8出现的概率是极低的。链表长度设置为8就是为了降低树化的机率。链表的查询效率为O(1)红黑树的查询效率为O(log2 N)而且红黑树的TreeNode比链表Node更占空间。 3. 链表何时会树化红黑树何时会退化成链表 链表长度超过阈值(8)且数组长度大于64满足以上链表会进化成红黑树。数组扩容时拆分红黑树的元素个数小于等于6则会退化成链表。删除树节点时若root 、root.left、root.right、root.let.let有一个为null也会退化成链表。 4. 多线程下对Map进行put造成数据错乱 5. Map1.7 扩容为什么会造成死链 因为JDK1.7 Map使用头插法在多线程下扩容时容易造成死链。例链表中有a,b两个元素其中a的下一个元素是b当线程T1,T2同时对数组进行扩容时假设T2先执行因为头插法扩容后的顺序为ba此时b的下一个元素时a。由于扩容不会对元素进行更改此时b指向a同时a又指向b当T1线程对数组进行扩容时就会造成死链。 6. Map的key是否可以为null对象作为key应如何处理 HashMap的key可以为null其余Map的实现则不可以tableMap。对象作为key应重写hashCode方法和equals方法且key的内容不可以被修改。
