快速排序

原理:首先选取一个基准数,然后设置左右哨兵i,j,首先右哨兵左移找到比基准数小的元素,左哨兵右移找到比基准数大的元素,然后进行交换,一直循环到左右哨兵相遇,此时将左哨兵右边的元素就为基准本身应该处于的位置。

冒泡排序中是相邻的元素进行交换,让最大的元素移动到正确的位置。而快速排序中是跳跃式的交换元素,所以效率比冒泡排序高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function quickSort(arr, start, end){
while(start >= end){
return;
}
var i = start;
var j = end;
//将所有满足条件的i和j进行交换
while(i < j){
while(arr[j] > arr[start] && i < j){
j--;
}
while(arr[i] <= arr[start] && i < j){
i++
}
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//交换完成后,将基准值交换到正确的位置
var temp2 = arr[i];
arr[i] = arr[start];
arr[start] = temp2;
quickSort(arr, start, i-1);
quickSort(arr, i+1, end);
return arr;
}
var arr = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
console.log(quickSort(arr, 0, arr.length-1))
//[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

二分查找

二分法之所以查找高效是因为数组是一个有序的数组,这样通过中间值在进行比较的时候,就可以将比较的范围划分的更小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//方法一 递归
function binarySearch(arr, low, high, target){
if(low > high){
return -1;
}
var i = Math.floor((low+high)/2);
if(target > arr[i]){
return binarySearch(arr, i+1, high, target);
} else if(target < arr[i]){
return binarySearch(arr, low, i-1, target);
} else{
return i;
}
}
arr = [0, 1, 3, 5, 9, 12]
console.log(binarySearch(arr, 0, 5, 9));
//4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//循环
function binarySearch(arr, targrt){
var low = 0;
var high = arr.length-1;
var mid = Math.floor((low + high) / 2);
while(low <= high){
if(targrt > arr[mid]){
low += 1;
} else if(targrt <= high){
high -= 1;
} else{
return mid;
}
mid = Math.floor((low + high) / 2);
}
return -1;
}
console.log(binarySearch([1, 2, 4, 5, 6, 7], 4));
//2

简单排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function insert(arr){
let newArr = [];
newArr.push(arr[0]);
for(let i = 1; i < arr.length; i++){
for(let j = newArr.length - 1; j >= 0; j--){
if(arr[i] > newArr[j]){
//插入功能,第一个参数(插入位置),第二个参数(0),第三个参数(插入的项)。
newArr.splice(j+1, 0, arr[i]);
break
}
if(j == 0){
newArr.unshift(arr[i])
}
}
}
return newArr;
}
let arr = [12, 1, 33, 4, 5, 3, 12];
console.log(insert(arr));
//[ 1, 3, 4, 5, 12, 12, 33 ]