JavaScript数据结构--快速排序, 冒泡排序, 二分查找

快速排序

主要思路: 不断拆分成两个数组, 小的放左边, 大的放右边.

时间复杂度: O (nlogn)
数组有n个元素,因为要递归运算,算出支点pivot的位置,然后递归调用左半部分和有半部分,这个时候理解上是若第一层的话就是n/2,n/2,若是第二层就是n/4,n/4,n/4,n/4这四部分,即n个元素理解上是一共有几层2^x=n,x=logn,然后每层都是n的复杂度,那么平均就是O(nlogn)的时间复杂度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function quickSort(arr) { //如果数组
// 如果数组小于1, 则直接返回
if (arr.length <= 1) {
return arr;
}
let pivot = arr.splice(Math.floor(arr.length / 2), 1)[0]; // 找基准,并把基准从原数组删除
// 定义左右数组
let left = [];
let right = []; // 比基准小的放在left,比基准大的放在right
for (let 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)); // 递归
}

冒泡排序

太简单, 没啥说的
时间复杂度: O(n²)

1
2
3
4
5
6
7
8
9
10
11
12
13
function maopao(arr) {
let i, j, length = arr.length;
for (i = 0; i < length; i++) {
for (j = i; j < length; j++) {
if (arr[i] > arr[j]) {
let c = arr[i];
arr[i] = arr[j];
arr[j] = c;
}
}
}
return arr;
}

二分查找

二分查找关键, 数组有序

时间复杂度为:O(log2n)
因为二分查找每次排除掉一半的不适合值,所以对于n个元素的情况:
一次二分剩下:n/2
两次二分剩下:n/2/2 = n/4
m次二分剩下:n/(2^m)
在最坏情况下是在排除到只剩下最后一个值之后得到结果,所以为
n/(2^m)=1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
a.sort((a, b)=>a-b)
function findMy(params, start, end, find) {
const index = Math.floor((start + end) / 2)
if (start > end) {
console.log({ index: -1, find: 'not find' })
return
} else if (params[index] > find ) {
findMy(params, start, (index - 1), find)
} else if (params[index] < find ) {
findMy(params, (index + 1), end, find)
} else if (params[index] == find) {
console.log({ index: index, find: find, })
return
}
}
findMy(a, 0, 9, -1)
越来越多的平台(微信公众平台,新浪微博,简书,百度打赏等)支持打赏功能,付费阅读时代越来越近,特此增加了打赏功能,支持微信打赏和支付宝打赏。坚持原创技术分享,您的支持将鼓励我继续创作!