python 网站开发 环境,河南网站建设路,官方网站改版建议,网站怎么做后期维护算法#xff08;Algorithm#xff09;可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤#xff0c;或者看成按照要求设计好的有限的确切的计算序列#xff0c;并且这样的步骤和序列可以解决一类问题。算法代表着用系统的方法描述解决问题的策略机制#xff0c…算法Algorithm可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤或者看成按照要求设计好的有限的确切的计算序列并且这样的步骤和序列可以解决一类问题。算法代表着用系统的方法描述解决问题的策略机制它能够对一定规范的输入在有限时间内获得所要求的输出。如果一个算法有缺陷或不适合于某个问题执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法分类 非线性时间比较类排序通过比较来决定元素间的相对次序由于其时间复杂度不能突破O(nlogn)因此称为非线性时间比较类排序。 线性时间非比较类排序不通过比较来决定元素间的相对次序它可以突破基于比较排序的时间下界以线性时间运行因此称为线性时间非比较类排序。 算法特征
有穷性(Finiteness)算法的有穷性是指算法必须能在执行有限个步骤之后终止确切性(Definiteness)算法的每一步骤必须有确切的定义输入项(Input)一个算法有0个或多个输入以刻画运算对象的初始情况所谓0个输入是指算法本身定出了初始条件输出项(Output)一个算法有一个或多个输出以反映对输入数据加工后的结果。没有输出的算法是毫无意义的可行性(Effectiveness)算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤即每个计算步骤都可以在有限时间内完成也称之为有效性。
算法复杂度 时间复杂度 算法的时间复杂度是指执行算法所需要的计算工作量。因此问题的规模越大算法执行的时间的增长率与的增长率正相关称作渐进时间复杂度Asymptotic Time Complexity。 空间复杂度 算法的空间复杂度是指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似一般都用复杂度的渐近性来表示。同时间复杂度相比空间复杂度的分析要简单得多。
1. 冒泡排序
这是一种简单的排序算法通过重复遍历要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。
var arr [1,56,9,6,3,5,8,2]
function sort(arr){for(let i 0;iarr.length-1;i){for(let j 0;jarr.length-1-i;j){if(arr[j]arr[j1]){let temp arr[j1];arr[j1] arr[j];arr[j] temp}}}return arr
}
sort(arr)
console.log(arr);算法描述
比较相邻的元素。如果第一个比第二个大就交换它们两个对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对这样在最后的元素应该会是最大的数针对所有的元素重复以上的步骤除了最后一个重复步骤1~3直到排序完成。
2. 插入排序
这是一种简单直观的排序算法。它的工作原理是通过构建有序序列对于未排序数据在已排序序列中从后向前扫描找到相应位置并插入。
var arr [1,56,9,6,3,5,8,2]
function sort(arr){for(var i 1;iarr.length;i){var val arr[i];var last i-1;while(last0 arr[last]val){arr[last1] arr[last]last--}arr[last1] val}return arr
}
sort(arr)
console.log(arr);算法描述
从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤3直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5。
3. 快速排序
快速排序使用分治的原理它选择一个元素作为基准然后将所有其他元素分成两组第一组包括所有小于基准的元素第二组包括所有大于或等于基准的元素。然后对这两组进行递归排序。这就是分治策略的基本步骤。
var arr [1,56,9,6,3,5,8,2]
function quickSort(arr){if(arr.length2){return arr}var mid Math.floor(arr.length/2)var pivot arr.splice(mid,1)[0]var left [];var right [];for(var i 0;iarr.length;i){if(arr[i]pivot){left.push(arr[i])} else {right.push(arr[i])}}return quickSort(left).concat(pivot,quickSort(right))
}
console.log(quickSort(arr));算法描述
从数列中挑出一个元素称为 “基准”pivot重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序。
4. 归并排序
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组再合并数组。
var arr [1,56,9,6,3,5,8,2];
function mergeSort(arr) {var len arr.lengthif(len2){return arr}var mid Math.floor(arr.length/2)var left arr.slice(0,mid)var right arr.slice(mid)return merge(mergeSort(left),mergeSort(right))
}
function merge(left,right) {var result []while(left.length0 right.length0){if(left[0]right[0]){result.push(right.shift())} else {result.push(left.shift())}}while(left.length){result.push(left.shift())}while(right.length){result.push(right.shift())}arr resultreturn arr
}
mergeSort(arr)
console.log(arr);算法描述
把长度为n的输入序列分成两个长度为n/2的子序列对这两个子序列分别采用归并排序将两个排序好的子序列合并成一个最终的排序序列。
5. 希尔排序
希尔排序是插入排序的一种更高效的改进版本也称为缩小增量排序。它通过比较相距一定间隔的元素来工作各趟比较所用的距离随着算法的进行而减小直到只比较相邻元素的最后一趟排序为止。
var arr [1,56,9,6,3,5,8,2]
function sort(arr){var gap arr.lengthfor(gap Math.floor(arr.length/2);gap0;gap Math.floor(gap/2)){for(var igap;iarr.length;i){var val arr[i];var j i;while(j-gap0 arr[j-gap]val){arr[j] arr[j-gap]j j-gap}arr[j] val}}return arr
}
sort(arr)
console.log(arr);算法描述
选择一个增量序列t1t2…tk其中titjtk1按增量序列个数k对序列进行k 趟排序每趟排序根据对应的增量ti将待排序列分割成若干长度为m 的子序列分别对各子表进行直接插入排序。仅增量因子为1 时整个序列作为一个表来处理表长度即为整个序列的长度。
6. 堆排序
堆排序是一种树形选择排序是对直接选择排序的有效改进。堆的定义如下具有n个元素的序列h1,h2,…,hn)当且仅当满足hih2i,hih2i1或hih2i,hih2i1 (i1,2,…,n/2)时称之为堆。在这里只讨论满足hih2i,hih2i1且hjhkjk的堆称为对于堆排序来说最重要的一步是将待排序的序列构造成一个大顶堆或小顶堆。
var arr [1,56,9,6,3,5,8,2]
var len;
function buildMaxHeap(arr) {len arr.lengthfor(var i 0;iMath.floor(arr.length/2);i){heapify(arr,i)}
}
function heapify(arr,i){var left i*21;var right i*22;var largest i;if(leftlen arr[left]arr[largest]){largest left}if(rightlen arr[right]arr[largest]){largest right}if(largest ! i){swap(arr,i,largest)heapify(arr,largest)}
}
function swap(arr,i,j){var temp arr[i];arr[i] arr[j];arr[j] temp
}
function heapSort(arr){buildMaxHeap(arr) for(var i arr.length-1;i0;i--){len-1;swap(arr,0,i)heapify(arr,0)}return arr
}
console.log(heapSort(arr));算法描述
将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆此堆为初始的无序区将堆顶元素R[1]与最后一个元素R[n]交换此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]R[n]由于交换后新的堆顶R[1]可能违反堆的性质因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆然后再次将R[1]与无序区最后一个元素交换得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1则整个排序过程完成。
7. 计数排序
计数排序是一种非比较型的排序算法适合于对一定范围内的整数排序。它的基本思想是通过为每个整数x计算其出现的次数得到一个频率表然后依次输出每个整数x出现的次数实现排序。
var arr [1,56,9,6,3,5,8,2];
function countingSort(arr, maxValue){var bucket new Array(maxValue1)var index 0for(var i 0;iarr.length;i){if(!bucket[arr[i]]){bucket[arr[i]] 0}bucket[arr[i]]}for(var j 0;jbucket.length;j){while(bucket[j]0){arr[index] jbucket[j]--}}return arr
}
console.log(countingSort(arr,56));算法描述
找出待排序的数组中最大和最小的元素统计数组中每个值为i的元素出现的次数存入数组C的第i项对所有的计数累加从C中的第一个元素开始每一项和前一项相加反向填充目标数组将每个元素i放在新数组的第C(i)项每放一个元素就将C(i)减去1。
8. 选择排序
这是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完。
var arr [1,56,9,6,3,5,8,2]
function sort(arr){for(let i 0;iarr.length-1;i){var indexlet min ifor(let j i1;jarr.length;j){if(arr[j]arr[min]){min j}}var temp arr[i];arr[i] arr[min];arr[min] temp}return arr
}
sort(arr)
console.log(arr);算法描述
初始状态无序区为R[1…n]有序区为空第i趟排序(i1,2,3…n-1)开始时当前有序区和无序区分别为R[1…i-1]和R(i…n。该趟排序从当前无序区中-选出关键字最小的记录 R[k]将它与无序区的第1个记录R交换使R[1…i]和R[i1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区n-1趟结束数组有序化了。
