4.1.7、基数排序
- O(n) 空间复杂度O(rd) 稳定(基数排序必须依赖于另外的排序方法 实质是多关键字排序)
是通过比较数字将其分配到不同的“桶里”来排序元素的。他是线性排序算法之一。 - 解决方案：1、最高位优先法MSD 2、最低位优先法LSD
- 算法步骤
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
- 从最低位开始，依次进行一次排序
- 从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列
- 基数排序图解如下
参考代码
public class RadixSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝，不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); int maxDigit = getMaxDigit(arr); return radixSort(arr, maxDigit); } /** * 获取最高位数 */ private int getMaxDigit(int[] arr) { int maxValue = getMaxValue(arr); return getNumLenght(maxValue); } private int getMaxValue(int[] arr) { int maxValue = arr[0]; for (int value : arr) { if (maxValue < value) { maxValue = value; } } return maxValue; } protected int getNumLenght(long num) { if (num == 0) { return 1; } int lenght = 0; for (long temp = num; temp != 0; temp /= 10) { lenght++; } return lenght; } private int[] radixSort(int[] arr, int maxDigit) { int mod = 10; int dev = 1; for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10) int[][] counter = new int[mod * 2][0]; for (int j = 0; j < arr.length; j++) { int bucket = ((arr[j] % mod) / dev) + mod; counter[bucket] = arrayAppend(counter[bucket], arr[j]); } int pos = 0; for (int[] bucket : counter) { for (int value : bucket) { arr[pos++] = value; } } } return arr; } private int[] arrayAppend(int[] arr, int value) { arr = Arrays.copyOf(arr, arr.length + 1); arr[arr.length - 1] = value; return arr; } }
4.1.8、桶排序
- O(n) 将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序
- 适用场景：外部排序中(磁盘中，内存有限，无法将数据全部加载到内存中)
- 算法步骤
- 设置固定数量的空桶。
- 把数据放到对应的桶中。
- 对每个不为空的桶中数据进行排序。
- 拼接不为空的桶中数据，得到结果
- 动画演示
4.1.9、计数排序
- 桶排序的一种特殊形式：每个桶中的数据相同
- 算法步骤
- 设置固定数量的空桶。
- 把数据放到对应的桶中。
- 对每个不为空的桶中数据进行排序。
- 拼接不为空的桶中数据，得到结果
- 基数排序图解如下
4.1.10、排序方法的选择？
- n代表数据量
- 1、n较小，可以采用直接插入或直接选择排序
- 2、若文件初始状态基本有序，应选用直接插入、冒泡或随机的快速排序
- 3、n较大，采用复杂度为O(nlgn)的方法：快排/堆排/归并
- 4、在实际的软件开发中，为什么我们更倾向于使用插入排序而不是冒泡排序算法？
- 从代码实现上来看，冒泡排序的数据交换要比插入排序的数据移动要复杂，冒泡排序需要3个赋值操作，而插入排序只需要1个，所以在对相同数组进行排序时，冒泡排序的运行时间理论上要长于插入排序。
如果数据存储在链表中，这三种排序算法还能工作吗？
一般而言，考虑只能改变节点位置，冒泡排序相比于数组实现，比较次数一致，但交换时操作更复杂；
插入排序，比较次数一致，不需要再有后移操作，找到位置后可以直接插入，但排序完毕后可能需要倒置链表；
选择排序比较次数一致，交换操作同样比较麻烦。综上，时间复杂度和空间复杂度并无明显变化，若追求极致性能，冒泡排序的时间复杂度系数会变大，插入排序系数会减小，选择排序无明显变化。
4.2、排序工具类Arrays？如何实现一个通用的、高性能的排序函数？(Java语言采用堆排序实现排序函数，C语言使用快速排序实现排序函数)
- Arrays拥有一组static方法(equals():比较两个array是否相等/fill():将值填入array中/sort():用来对array进行排序/binarySearch():在排好序的array中寻找元素/system.arraycopy():array的复制)
- Jdk7中Arrays.sort()和Collections.sort()排序方法使用注意: jdk1.6中的arrays.sort（）和 collections.sort（）使用的是MergeSort； jdk1.7中内部实现转换成了TimSort方法，
- 对对象间比较的实现
1、有两个参数，第一个是比较的数据，第二个是比较的规则，如果comparator为空，则使用comparableTimSort的sort实现
2、传入的待排序数组若小于MIN_MERGE（Java实现中为32）则从数组开始处找到一组连接升序或严格降序（找到后翻转）的数
BinarySort：使用二分查找的方法将后续的数插入之前的已排序数组
3、开始真正的TimSort过程（选取minRun大小，之后待排序数组将被分成以minRun大小为区块的一块块子数组）
Timsort的思想：找到已经排好序的数据子序列，然后对剩余部分排序，最后合并起来 - java提供的默认排序算法
1、对于基础数据类型，目前使用的是所谓双轴快速排序（Dual-Pivot QuickSort），是一种改进的快速排序算法，早期版本是相对传统的快速排序；
2、而对于对象数据类型，目前则是使用TimSort，思想上也是一种归并(Merge)和二分插入排序（binary Sort）结合的优化排序算法。
思路是查找数据集中已经排好序的分区（这里叫run 连续升或降的序列），然后合并这些分区来达到排序的目的。 - Java8引入了并行排序算法(直接使用parallelSort方法)，这是为了充分利用现代多核处理器的计算能力，底层实现基于fork-join框架,当处理的数据集比较小的时候，差距不明显，甚至还表现差一点；但是,当数据集增长到数万或百万以上时,提高就非常大了，具体还是取决于处理器和系统环境.
- fork-join框架的适用场景：计算密集型，而非IO密集型，踩过坑
4.3、常见的查找算法？
- 1、二分查找法(考虑好边界条件，不要被面试官抓住漏洞)(使用Arrays工具类的binarySearch方法)
思路：先确定数组的中间位置，然后将要查询的值与数组中间位置的值进行比较，若小于数组中间值，则要查找的值应位于该中间值之前，依次类推；
算法： 1、如果关键字小于中央元素，只需继续在数组的前半部分进行搜索；2、如果关键字与中央元素相等，则搜索结束，找到匹配元素；3、如果关键字大于中央元素，只需继续在数组的后半部分进行搜索
限制：用于顺序链表或排序后的链表
注意事项：1、循环退出条件low<=high;2、mid的取值(low+(high-low)>>1)因为相比除法运算来说，计算机处理位运算要快得多;3、low和high的更新low=mid+1,high=mid-1
时间复杂度：O(lgn)
public int bsearch(int[] a, int n, int value) { int low = 0; int high = n - 1; while (low <= high) { int mid = (low + high) / 2;//或者int mid = low+((high-low)>>1)； if (a[mid] == value) { return mid; } else if (a[mid] < value) { low = mid + 1; } else { high = mid - 1; } } return -1; }
- 2、4种常见的二分查找变形问题
第一种：查找第一个值等于给定值的元素
public int bsearch(int[] a, int n, int value) { int low = 0; int high = n - 1; while (low <= high) { int mid = low + ((high - low) >> 1); if (a[mid] > value) { high = mid - 1; } else if (a[mid] < value) { low = mid + 1; } else { if ((mid == 0) || (a[mid - 1] != value)) return mid; //mid不是第一个数或mid左边的数不是 else high = mid - 1; } } return -1; }
第二种：查找最后一个值等于给定值的元素
public int bsearch(int[] a, int n, int value) { int low = 0; int high = n - 1; while (low <= high) { int mid = low + ((high - low) >> 1); if (a[mid] > value) { high = mid - 1; } else if (a[mid] < value) { low = mid + 1; } else { if ((mid == n - 1) || (a[mid + 1] != value)) return mid; else low = mid + 1; } } return -1; }
第三种：查找第一个大于等于给定值的元素
public int bsearch(int[] a, int n, int value) { int low = 0; int high = n - 1; while (low <= high) { int mid = low + ((high - low) >> 1); if (a[mid] >= value) { if ((mid == 0) || (a[mid - 1] < value)) return mid; else high = mid - 1; } else { low = mid + 1; } } return -1; }
第四种：查找最后一个小于等于给定值的元素
public int bsearch7(int[] a, int n, int value) { int low = 0; int high = n - 1; while (low <= high) { int mid = low + ((high - low) >> 1); if (a[mid] > value) { high = mid - 1; } else { if ((mid == n - 1) || (a[mid + 1] > value)) return mid; else low = mid + 1; } } return -1; }
- 3、如果有序数组是一个循环有序数组，比如4，5，6，1，2，3。针对这种情况，如何实现一个求“值等于给定值”的二分查找算法呢？
public int search(int[] nums, int target) { if (nums.length == 1 && nums[0] == target) return 0; int left = 0; int right = nums.length - 1; int mid = 0; while (left < right) { mid = (left + right) >> 1; if (nums[left] == target) return left; if (nums[right] == target) return right; if (nums[mid] == target) return mid; if (nums[mid] > nums[left]) { // 第一种情况 if (target > nums[mid]) { left = mid + 1; //在mid到左侧最大值区间 } else {//target小于中间值 if (target > nums[left]) { right = mid - 1; } else { left = mid + 1; //在右侧区间 } } } else { // 第二种情况 mid小于最左值 if (target > nums[mid]) {//两种情况：1、在mid右侧 2、在左侧 if (target < nums[right]) { left = mid + 1; //1、在mid右侧 } else { right = mid - 1; //2、在左侧 } } else { //在右侧的左边区域 right = mid - 1; } } } return -1; }
- 4、x的平方根 LeetCode69 实现int sqrt(int x)函数。计算并返回x的平方根，其中x是非负整数,由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去
- 方法1：java自带API
public int mySqrt(int x) { return (int)Math.sqrt(x); }
- 方法2：二分搜索
int mySqrt(int x) { //注：在中间过程计算平方的时候可能出现溢出，所以用long long。 long i=0; long j=x/2+1;//对于一个非负数n，它的平方根不会大于（n/2+1） while(i<=j) { long mid=(i+j)/2; long res=mid*mid; if(res==x) return mid; else if(res<x) i=mid+1; else j=mid-1; } return j; }
方法3：牛顿迭代法 求c的算术平方根就是求f(x)=x^2-c的正根 迭代公式：xn+1=1/2(xn+c/xn)
int mySqrt(int x) { if (x == 0) return 0; double last=0; double res=1; while(res!=last) { last=res; res=(res+x/res)/2; } return int(res); }
4.4、复杂度分析
常见的时间复杂度？（表示的是一个算法执行效率与数据规模增长的变化趋势）
| 时间复杂度 | 概念 |
- O(1) 常数阶| 常量级别的时间复杂度：只要代码的执行时间不随n的增大而增长，这样代码的时间复杂度我们都记作O(1)。
2、O(logn)对数阶、O(nlogn)线性对数阶| 代码循环执行的次数呈现对数关系
3、O(m+n)、O(m*n) | 代码的复杂度由两个数据的规模来决定
空间复杂度：(表示算法的存储空间与数据规模之间的增长关系)
常见的空间复杂度就是O(1)、O(n)、O(n2)
- 平均时间复杂度(加权平均时间复杂度)：加了概率
- 均摊时间复杂度：对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。
- 算法的最好情况和最坏情况？
最好情况：算法执行最佳的数据排列。如：二分搜索时，目标值正好位于搜索的数据中心，时间复杂度为0；
最差情况：给定算法的最差输入。如：快速排序中，如果选择的关键值是列表中最大或最小值，最差情况就会发生，时间复杂度会变成O(n^2)
4.5、如何高效地判断无序数组中是否包含某特定值？
// 方法1：使用list (**最常使用**) public static boolean useList(String[] arr, String targetValue) { return Arrays.asList(arr).contains(targetValue); } // 方法2：使用Set 低效 >public static boolean useSet(String[] arr, String targetValue) { Set<String> set = new HashSet<String>(Arrays.asList(arr)); return set.contains(targetValue); } // 方法3：使用一个简单循环 最高效 >public static boolean useLoop(String[] arr, String targetValue) { for(String s: arr){ if(s.equals(targetValue)) return true; } return false; }
- 方法4：Arrays.binarySearch()方法：数组必须是有序的(有序数组时，使用列表或树可达到O(lgn),使用hashset可达到O(1))
4.6、查找算法实战？
- 1、我们要给电商交易系统中的“订单”排序。订单有两个属性(下单时间，订单金额) 需求是按金额从小到大对订单数据排序。对金额相等的订单，按下单时间从早到晚排序
稳定性概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变
思路：先按下单时间给订单排序，排完序之后，使用稳定排序算法，按订单金额重新排序(稳定排序算法可以保持金额相同的两个对象，在排序之后的前后顺序不变) - 2、O(n)时间复杂度内求无序数组中的第K大元素？(利用分区的思想) 代码放在eclipse中
我们选择数组区间A[0…n-1]的最后一个元素A[n-1]作为pivot，对数组A[0…n-1]原地分区，这样数组就分成了三部分，A[0…p-1]、A[p]、A[p+1…n-1]。
如果p+1=K，那A[p]就是要求解的元素；如果K>p+1, 说明第K大元素出现在A[p+1…n-1]区间，我们再按照上面的思路递归地在A[p+1…n-1]这个区间内查找。同理，如果K<p+1，那我们就在A[0…p-1]区间查找。 - 3、现在你有10个接口访问日志文件，每个日志文件大小约300MB，每个文件里的日志都是按照时间戳从小到大排序的。你希望将这10个较小的日志文件，合并为1个日志文件，合并之后的日志仍然按照时间戳从小到大排列。如果处理上述排序任务的机器内存只有1GB，你有什么好的解决思路
answer：先构建十条io流，分别指向十个文件，每条io流读取对应文件的第一条数据，然后比较时间戳，选择出时间戳最小的那条数据，将其写入一个新的文件，然后指向该时间戳的io流读取下一行数据，然后继续刚才的操作，比较选出最小的时间戳数据，写入新文件，io流读取下一行数据，以此类推，完成文件的合并， 这种处理方式，日志文件有n个数据就要比较n次，每次比较选出一条数据来写入，时间复杂度是O(n)，空间复杂度是O（1）,几乎不占用内存。
