各种排序算法的时间复杂度和空间复杂度(阿里)
二分查找法的时间复杂度:O(logn) redis,kafka,B+树的底层都采用了二分查找法
参考:二分查找法 redis的索引底层的 跳表原理 实现 聊聊Mysql索引和redis跳表 —redis的跳表原理 时间复杂度O(logn)(阿里)
参考:二分查找法 kafka如何实现高并发存储-如何找到一条需要消费的数据(阿里)
参考:二分查找法:一步步分析为什么B+树适合作为索引的结构 以及索引原理 (阿里面试)
1.二分查找
二分查找也称为折半查找,它是一种效率较高的查找方法。二分查找的使用前提是线性表已经按照大小排好了序。这种方法充分利用了元素间的次序关系,采用分治策略。基本原理是:首先在有序的线性表中找到中值,将要查找的目标与中值进行比较,如果目标小于中值,则在前半部分找,如果目标小于中值,则在后半部分找;假设在前半部分找,则再与前半部分的中值相比较,如果小于中值,则在中值的前半部分找,如果大于中值,则在后半部分找。以此类推,直到找到目标为止。
假设我们要在 2,6,11,13,16,17,22,30中查找22,上图所示,则查找步骤为:
首先找到中值:中值为13(下标:int middle = (0+7)/2),将22与13进行比较,发现22比13大,则在13的后半部分找;
在后半部分 16,17,22,30中查找22,首先找到中值,中值为17(下标:int middle=(0+3)/2),将22与17进行比较,发现22比17大,则继续在17的后半部分查找;
在17的后半部分 22,30查找22,首先找到中值,中值为22(下标:int middle=(0+1)/2),将22与22进行比较,查找到结果。
二分查找大大降低了比较次数,二分查找的时间复杂度为:O(logn),即。
示例代码:
public class BinarySearch { public static void main(String[] args) { int arr[] = {2, 6, 11, 13, 16, 17, 22, 30}; System.out.println("非递归结果,22的位置为:" + binarySearch(arr, 22)); System.out.println("递归结果,22的位置为:" + binarySearch(arr, 22, 0, 7)); } //非递归 static int binarySearch(int[] arr, int res) { int low = 0; int high = arr.length-1; while(low <= high) { int middle = (low + high)/2; if(res == arr[middle]) { return middle; }else if(res <arr[middle]) { high = middle - 1; }else { low = middle + 1; } } return -1; } //递归 static int binarySearch(int[] arr,int res,int low,int high){ if(res < arr[low] || res > arr[high] || low > high){ return -1; } int middle = (low+high)/2; if(res < arr[middle]){ return binarySearch(arr, res, low, middle-1); }else if(res > arr[middle]){ return binarySearch(arr, res, middle+1, high); }else { return middle; } } }
其中冒泡排序加个标志,所以最好情况下是o(n)
直接选择排序:
排序过程:
1 、首先在所有数据中经过 n-1次比较选出最小的数,把它与第 1个数据交换,
2、然后在其余的数据内选出排序码最小的数,与第 2个数据交换…… 依次类推,直到所有数据排完为止。
在第i 趟排序中选出最小关键字的数据,需要做 n-i次比较。
//冒泡排序,大的数不断向后冒泡 void buddle(vector<int>& nums) { int len=nums.size(); for(int i=0;i<len-1;i++) { for(int j=0;j<len-1-i;j++) { if(nums[j]>nums[j+1]) swap(nums[j],nums[j+1]); } } }
线性排序算法
计数排序
假设:有n个数的集合,而且n个数的范围都在0~k(k = O(n))之间。
运行时间:Θ(n+k)
待排序数组A如图2.1所示,需要辅助数组B(存储最后排序结果),数组C(存储元素的个数)。基于上述的假设,数组C的大小为k,C[i]表示数组A中元素i(0 <= i < k)的个数(如图2.2所示),为了保证计数排序的稳定性,数组C变化为图2.3,C[i]表示小于或者等于i的个数。代码如下:
1: /* 2: 输入:待排序数组A,存储排序后的数组B,数组A的大小,数组C的大小 3: 功能:计数排序 4: */ 5: void CountingSort(int A[], int B[], int len, int k) 6: { 7: int *CountArr = new int[k]; 8: int i; 9: for (i = 0; i < k; i++) 10: { 11: CountArr[i] = 0; 12: } 13: 14: for (i = 0; i < len; i++) 15: { 16: CountArr[A[i]]++; 17: } 18: 19: for (i = 1; i < k; i++) 20: { 21: CountArr[i] += CountArr[i-1]; 22: } 23: 24: // 从右至左保证算法的稳定性 25: for (i = len-1; i >=0; i--) 26: { 27: B[CountArr[A[i]]-1] = A[i]; 28: CountArr[A[i]]--; 29: } 30: }
9-12行和19-22行的运行时间Θ(k),14-17行和25-29行的运行时间为Θ(n),所以总的运行时间为Θ(2(n+k)) = Θ(n+k)。
基数排序
基数排序:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序分为两种LSD和MSD。
LSD(Least significant digital):最低有效位优先,即从右向左开始排序。
MSD(Most significant digital):最高有效位优先,即从左往右开始排序。
以下是LSD方式的基数排序的伪代码
1: RadixSort(A,d)
2: for i <- 1 to d
3: 用稳定的排序算法排列数组A中元素的第i位
如图3:先牌个位,然后十位,最后百位。为数组的某一位排序的时候一定需要稳定的算法。
运行时间为Θ(d(n+k))。在基数排序中排列数组各位的算法是计数排序所以运行时间为Θ(n+k),又d是数组中数的最大位数。
桶排序
桶排序:将数组分到有限个桶子内,然后再对桶子里面的序列进行排序,运行时间Θ(n)。桶排序基于一个假设:输入的数据由随机过程构成,否则在最坏情况下都分配到一个桶子里面,如果又不满足计数排序的假设要求,那么只能使用基于比较的排序算法进行排序,运行时间就退化到Ω(nlogn)。
排序算法稳定性
排序算法稳定性:假设待排序序列中有两个元素相等,而且在排序前和排序后两个相等的元素的相对位置不变,即有 a = b,排序前a在b前面,那么排序后,a还是要在b前面。排序算法的稳定性是要看具体的算法实现,比如一般情况下,直接选择排序,快速排序,希尔排序,堆排序都不是稳定排序算法,基数排序,计数排序,归并排序,插入排序,冒泡排序都是稳定排序算法。
快速排序:A = {2, 2, 1},排序后A = {1,2,2}。
希尔排序:A = {1,2,5,4,4,7},排序后(k = 2);A = {1, 2, 4, 4, 5, 7} 。
堆排序:A = {2,2,1},排序后A = {1,2, 2}。
直接选择排序: A = {4, 4, 2, 5},排序后 A = {2,4, 4, 5}。
以上举例都不满足稳定性。