平度网站整站优化外包公司,长春做网站的,网站建设 制作公司,电脑网站打不开了但是有网查找与排序
查找
查找与排序都在程序设计中常被用到的算法。查找相对而言简单#xff0c;一般都是顺序查找#xff0c;二分查找#xff0c;哈希表查找#xff0c;和二叉排序树查找。其中二分查找是我必须熟悉的一种。哈希表和二叉排序树主要点在于他的数据结构而不是算法…查找与排序
查找
查找与排序都在程序设计中常被用到的算法。查找相对而言简单一般都是顺序查找二分查找哈希表查找和二叉排序树查找。其中二分查找是我必须熟悉的一种。哈希表和二叉排序树主要点在于他的数据结构而不是算法。哈希表主要的优点是我们利用他能在O(1)的时间查找某个元素是效率最高的查找方式。但是缺点是需要额外空间来实现哈希表二叉排序树查找算法对应的数据结构是二叉搜索树或者叫二叉查找树之前我们已经着重讨论过这种数据结构原理以及自己的实现。
排序
排序比查找要复杂例如经常选择一种排序算法的时候经常会对各种排序算法进行比较插入排序冒泡排序归并排序快速排序等不同算法的优劣。而这些都是必须掌握的排序算法我们必须能从空间福再度时间复杂度等方面去分析他们的优缺点。其中快速排序是重中之重。可见的几种排序算法在之前的章节中也用动图的方式给出来详细的解释实现。
实际案例
快排是重要的排序算法但是在具体场景下我们需要选择最优最合适的算法例如下情况 实现一个排序算法实际复杂度空间复杂度必须不超过O(n)对公司所有员工年龄进行排序。分析上题中重点空间复杂度实际复杂度O(n)排序对象员工年龄我们假设员工都是100 岁以下量级也不大一个公司最多 也就10万这种情况数组区间范围是固定的而且基数不大最理想的排序算法是计数排序
另类用法旋转数组中的最小数字
题目将数组最开始的若干个元素搬到数组的末尾我们称为数组的旋转。输入一个递增数组的旋转输出旋转数组的最小元素例如数组{3,41,5,12}是{1,23,45}的一个旋转明显最小值是1
分析 直观来看找最小值一次遍历就能搞定时间复杂度O(n)但是这个并没有利用这个数组的特性已排序旋转后两部分有序肯定有更优解 旋转后两部分数组都有序并且递增必然有序部分后面大于前面 然后分界处必然是最小值的特点 由上部分分析我们自然想到二分查找寻找最小值。 流程如下 定义指针minmax分别指向数组两端按题意第一个元素应该大于等于 最后一个元素因为旋转过。接着找中间元素mid max min/2, 如果中间元素大于min则min到mid之间处于递增则最小值必然在中间元素后面此时我们将min指针移动到mid位置同样如果中间元素mid 小于min则表示最小值在mid或者mid的左边此时我们将max指针移动到mid位置依次对minmax之间的数组部分进行如上流程直到 max - min 1 为止此时最大最小是相邻则找出最小值 如下实际案例{3,45,12} min指针指向第0个元素 3 max指向最后一个2中间元素55 3min移动到mid位置也就是min指向5再次中间元素变为1,15,此时最小值在min右边将max移动到mid位置也就是max指向1 此时max - min 1得到最小值max位置。 代码实现
/*** author liaojiamin* Date:Created in 11:39 2021/3/16*/
public class FindRotateMin {public static int findMin(int[] array){if(array null || array.length 0){return -1;}if(array.length 1){return array[0];}if(array.length 2){return array[0] array[1] ? array[0] : array[1];}int index1 0;int index2 array.length -1;int indexMin index1;while (array[index1] array[index2]){if(index2 - index1 1){indexMin index2;break;}indexMin (index2 index1)/2;if(array[indexMin] array[index1]){index1 indexMin;}else if(array[indexMin] array[index1]){index2 indexMin;}}return indexMin;}public static void main(String[] args) {int[] array {3,4,5,0,1,2};System.out.println(array[findMin(array)]);}
}问题上述代码中我们每次判断都会有等于的情况当index1 index2,两个相同的时候并且他们中介的数字indexMin也相同这个时候我们符合第一个判断将indexMin赋值给了index1此时默认最小数字在后面其实不一定对如下反例数组{1,01,11} 和数组{1,11,01} 都可以看成递增排序{0,11,11}的旋转但是下图中最小值分别在左边和右边 如上情况首尾数字中介位置数字都是1 但是却有两种不同的最小值位置因此这种特殊情况当两个指针数字以及中间数字都一样的时候无法判断最小值的位置我们不得不采取遍历的方式。修改代码如下
/*** 二分排序另类用法* Created by jiamin5 on 2021/3/15.*/
public class FindRotateMin {public static int finMin(int[] array){if(array.length 0){return -1;}if(array.length 1){return array[0];}if(array.length 2){return array[1];}int index1 0;int index2 array.length -1;int indexMin index1;while (array[index1] array[index2]){if(index2 index1 1){indexMin index2;break;}indexMin (index1index2)/2;if(array[index1] array[index2] array[indexMin] array[index1]){return findMinList(array, index1, index2);}if(array[index1] array[indexMin]){index1 indexMin;}else if(array[indexMin] array[index2]){index2 indexMin;}}return array[indexMin];}public static int findMinList(int array[], int index1, int index2){int result array[index1];for (int i index1; i index2; i){if(array[i] result){result array[i];}}return result;}public static void main(String[] args) {int[] array {4,5,6,7,8,0,1,1,1,2,2,2,3,3,3,3,4,4};System.out.println(finMin(array));}
}测试用例
输入旋转数组数组中没有重复数字边界值测试只有一个两个数字的数组输入特殊null值输入重复数字的数组
上一篇数据结构与算法–利用栈实现队列 下一篇数据结构与算法–再谈递归与循环斐波那契数列
