排序:把某个乱序的数组变成升序或者降序的数组(JS:sort())
搜索:找出数组中某个元素的下标(JS:indexOf())
排序算法演示网站
排序算法
冒泡算法
时间复杂度:O(n2)
1 | Array.prototype.bubbleSort() = function() { |
选择排序
找到数组中最小的值,选中它并将其放在第一位;
找到数组中第二小的值,选中它并将其放在第二位;
以此类推,执行n-1轮
时间复杂度:O(n2)
1 | Array.prototype.selectionSort() = function() { |
插入排序
从第二个数开始往前比;
比它大就往后排;
以此类推进行到最后一个数
时间复杂度:O(n2)
1 | Array.prototype.insertionSort() = function() { |
归并排序
分:把数组劈成两半,再递归地对子数组进行“分”操作,直到分成一个个单独的数。
合:把两个数合并成有序数组,再对有序数组进行合并,直到全部子数组合并为一个完整数组。
时间复杂度:分(O(logN)),合(O(n)),分合(O(n * logN))
1 | Array.prototype.mergeSort() = function() { |
快速排序
分区:从数组中任意选择一个基准,所有比基准小的元素放在基准前,所有比基准大的元素放在基准后面。
递归:递归地对基准前后的子数组进行分区。
时间复杂度:递归(O(logN)),分区(O(n)),分合(O(n * logN))
1 | Array.prototype.quickSort() = function() { |
搜索算法
顺序搜索
1、遍历数组
2、找到跟目标值相等的元素,就返回它的下标
3、遍历结束后,如果没有搜索到目标值,就返回-1
时间复杂度:O(n)
1 | Array.prototype.sequentialSearch() = function(item) { |
二分搜索
前提:数组是有序的
从数组的中间元素开始,如果中间元素正好是目标值,则搜索结束
如果目标值大于或小于中间元素,则在大于或小于中间元素的那一半数组中搜素
时间复杂度:O(logN)
1 | Array.prototype.binarySearch() = function(item) { |
leetcode
21、374
chrome的排序方法Array.prototype.sort()内部实现原理