算法 - 1

作者: Kris_lee | 来源:发表于2018-04-16 16:27 被阅读12次

路径规划文集
大数据实例 | 你想知道搜索引擎排名怎么来的嘛---PageRa
算法1
算法 - 1
算法（1）
算法 1
[算法] 1
算法（1）
算法1
算法1

1. 快速排序
2. 二分查找
3. 归并排序
4. 冒泡排序
- 4.1 冒泡排序的Demo实现
- 4.2 冒泡排序的图解
5. 总结

分而治之的一种思想
能够快递进行排序，相比选择排序要高效的多。实属优雅代码的典范。

<h4 id="1.1">学习分而治之</h4>
D&C算法

找出简单的基线条件；
确定如何缩小问题的规模，使其符合基线条件；

(D&C并非可用与解决问题的算法，而是一种解决问题的思路)

图1

如图，我们想要找到一个可以平均分配该土地并且都是正方形的方法，这样，我们可以通过数据的思想，首先-先找到 1680和640的最大公约数。不难发现，这个最大公约数就是我们想要得到的答案。那么这个最大公约数其实也是这里的基线条件。

<h4 id="1.2">快速排序的Demo方法</h4>


       　function quickSort(arr){
            //如果数组<=1,则直接返回
            if(arr.length<=1){return arr;}
            var pivotIndex=Math.floor(arr.length/2);
            //找基准，并把基准从原数组删除
            var pivot=arr.splice(pivotIndex,1)[0];
            //定义左右数组
            var left=[];
            var right=[];

            //比基准小的放在left，比基准大的放在right
            for(var i=0;i<arr.length;i++){
                if(arr[i]<=pivot){
                    left.push(arr[i]);
                }
                else{
                    right.push(arr[i]);
                }
            }
            //递归
            return quickSort(left).concat([pivot],quickSort(right));
        }  


        function test(){
        
            let arr = [1,5,6,3,7,0];
            console.log(quickSort(arr));
        }
        
        test();

<h4 id="1.3">快速排序的图解</h4>

快速排序.png

限定元素区间
待查找元素在区间的某个位置吗
不在。
那么看看待查找元素是不是在当前未知的左边或右边

二分查找是一种快速从一个有序数组中找到某个元素未知的查找，这点有点类似于猜数字游戏，通过不断的询问是大于还是小于这样的问题，最终猜出目标数字；

二分查找.png

<h4 id="2.3">二分demo</h4>

function binary_search(arr,low,high,key){
    
    if (low > high) { return -1}
        var mid = parseInt(high+low)/2;

    if(arr[mid] == key){
        return mid;
    }else if(arr[mid] > key){
        high = mid-1;
        return binary_search(arr, low, high, key);
    }else if(arr[mid] < key){
        low = mid +1;
        return binary_search(arr, low, high, key);
    }

}

把元素分成两部分，对每一个部分采用递归的归并排序
比较已经排好序的元素
合并已经排好序的元素
排序完毕

<h4 id="3.1"> 归并排序概念</h4>
归并排序也是一种“分而治之”的递归算法
<h4 id="3.2"> 归并排序图解</h4>

归并排序.png

<h4 id="3.3"> 归并排序demo</h4>


    function merge(left, right) {  
    var result = [];  
    while(left.length > 0 && right.length > 0) {  
       if(left[0] < right[0]) {  
           result.push(left.shift());  
       }  
       else {  
           result.push(right.shift());  
       }  
   }  
   /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */  
   return result.concat(left).concat(right);  
}  
    function mergeSort(arr){  
        if(arr.length==1) {return arr};  
        var mid=Math.floor(arr.length/2);  
        var left_arr=arr.slice(0,mid),right_arr=arr.slice(mid);  
        return merge(mergeSort(left_arr),mergeSort(right_arr));  
    }

<h3 id="4">冒泡排序</h3>
解析：

1.比较相邻的两个元素，如果前一个比后一个大，则交换位置。
2.第一轮的时候最后一个元素应该是最大的一个。
3.按照步骤一的方法进行相邻两个元素的比较，这个时候由于最后一个元素已经是最大的了，所以最后一个元素不用比较。

<h4 id="4.1">冒泡排序的Demo实现</h4>

function sortArr(arr,type){
   for(let i = 0; i < arr.length - 1;i++){
        for(let j=0;j < arr.length -i-1;j++){
            if(arr[j]>arr[j+1]){
                var temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
   }
   if(type){
    arr.reverse();
   }
}

<h4 id="4.2">冒泡排序的图解</h4>