算法 - 1

• 1. 快速排序
  • 1.1 学习分而治之
  • 1.2 快速排序的Demo方法
  • 1.3 快速排序的图解
• 2. 二分查找
  • 2.1 二分查找的概念
  • 2.2 二分查找的图解
  • 2.3 二分查找的demo
• 3. 归并排序
  • 3.1 归并排序的概念
  • 3.2 归并排序的图解
  • 3.3 归并排序的demo
• 4. 冒泡排序
  • 4.1 冒泡排序的Demo实现
  • 4.2 冒泡排序的图解
• 5. 总结

<h3 id="1">快速排序</h3>

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

<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

<h3 id="2">二分查找</h3>

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

<h4 id="2.1">二分概念</h4>

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

<h4 id="2.2">二分图解</h4>

二分查找.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);
    }

}

<h3 id="3">归并排序</h3>

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

<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>

冒泡排序.png

<h3 id="5">总结</h3>

这里还有更多排序方式和方法；这里归纳的一些复杂度；之后会慢慢总结整理出来

排序复杂度.png