各种算法实现

水深无声 2022-03-09 10:08 162阅读 0赞

排序算法

1，冒泡排序（稳定）———时间复杂度O(n^2)  
冒泡排序是比较任何两个相邻元素，如果第一个比第二个大就交换两个的位置。那么较大的值就会一点一点移动到后面正确的位置。

//第一种写法
    function bubbleSort(arr){
    	var len = arr.length;
    	for(var i =0 ; i<len-1;i++){
    		for(var j= 0;j<len-1-i;j++){
    			if(arr[j] > arr[j+1]){
    					var temp = arr[j+1];
    					arr[j+1] = arr[j];
    					arr[j] = temp;
    			}
    		}
    	}
    	return arr;
    }
    
    
    //第二种写法
    function bubbleSort(arr){
    	var len = arr.length;
    	while(len > 0){
    		var pops =0;
    		for(var i =0;i<len;i++{
    			if(arr[i] > arr[i+1]){
    				pops = i;
    				var temp = arr[i];
    				arr[i] = arr[i+1];
    				arr[i+1] =temp 
    			}
    		}
    		len = pops;
    	}
    	return arr
    }

2,插入排序（稳定）——时间复杂度O(n^2)  
通过构建有序数列，对于未排序的数据，再已排序数列中从后向前扫描，找到相应的位置并插入，需要把已排序的元素逐步向后挪，为新元素提供插入空间。

3，归并排序（稳定）——时间复杂度O(n log n) 仅次于快速排序  
原理是将一个数组分成两个部分，然后将两个部分分别排序再合并  
步骤：  
1，将数组分为左右两个子序列  
2，再分别将左右两边的子序列分成两个  
3，直到分为每个序列只有1个元素时。就不用对每个部分进行排序了，直接两两合并就行了

4，选择排序（不稳定）——时间复杂度O(n^2)  
工作原理是：首先在序列中找到最小的元素，存放在排序序列的起始位置，然后再再剩下的元素中寻找最小的元素放大序列末尾，直到所有元素均排序完毕。

5，希尔排序（不稳定）——时间复杂度O(n log n)  
是简单插入排序的改进版，它与插入排序的不同之处在于，它会优先比较距离较远的元素，（又叫缩小增量排序）；增量的值就是两个元素隔了几个元素相互比较。  
希尔排序的核心在于间隔序列的设定，既可以提前设置好间隔序列，又可以动态定义间隔序列。

希尔排序实质上是一种插入排序，对数列进行等间隔分组处理，在每一组中做插入排序,使得原来的时间复杂度O(n^2)降为O(n log n)

希尔排序是按一定的间隔对序列进行分组，  
6，快速排序（不稳定）——时间复杂度O(n log n) 最快的算法  
通过 的递归的方法将数据依次分解为包含较小元素和较大元素的不同子序列。  
首先要在列表中选择一个元素作为基准值。数据排序围绕基准值进行，将列表中小于基准值的元素移到数组的底部，将大于基准值的元素移到数组顶部

7，堆排序（不稳定）——时间复杂度O(n log n)

***常见的查找算法***

1，顺序查找算法  
从列表第一个元素元素开始，逐个对每个元素进行判断，直到找到为止,或者到最后都没有找到， 叫顺序查找，或者 线性查找

function  seqSearch(arr,target){
    	for(var i=0;i<arr.length;i++){
    		if(target === arr[i]){
    			return i;
     		}
        }
        return -1
    }

2，二分查找算法 时间复杂度是 —— O(log2n)  
是针对有序序列的，所以在使用二分查找时序列先要排好序，  
基本思想：  
1，确定数组的中间位置m  
2，将要查找的值target与arr\[m\]比较，若相等就直接返回m位置，否则确定新的查找区域，继续二分查找。（比如该数组的升序，如果target<arr\[m\]则左边的区域为新的查找区域，将左边区域进行二分查找算法）

代码实现  
1，非递归实现

2，递归实现