<h3 id="1">快速排序</h3>
- 分而治之的一种思想
- 能够快递进行排序，相比选择排序要高效的多。实属优雅代码的典范。
<h4 id="1.1">学习分而治之</h4>
D&C算法
- 找出简单的基线条件；
- 确定如何缩小问题的规模，使其符合基线条件；
(D&C并非可用与解决问题的算法，而是一种解决问题的思路)
如图，我们想要找到一个可以平均分配该土地并且都是正方形的方法，这样，我们可以通过 数据的思想，首先-先找到 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>
<h3 id="2">二分查找</h3>
- 限定元素区间
- 待查找元素在区间的某个位置吗
- 不在。
- 那么看看待查找元素是不是在当前未知的左边或右边
<h4 id="2.1">二分概念</h4>
二分查找是一种快速从一个有序数组中找到某个元素未知的查找，这点有点类似于猜数字游戏，通过不断的询问是大于还是小于这样的问题，最终猜出目标数字；
<h4 id="2.2">二分图解</h4>
<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>
<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>
<h3 id="5">总结</h3>
这里还有更多排序方式和方法；这里归纳的一些复杂度；之后会慢慢总结整理出来
