Repository navigation
算法 #18
Description
算法
排序算法
快速排序
快速排序（quick sort）是公认最快的排序算法之一，有着广泛的应用。
时间复杂度
- 最佳情况：O(nlogn)
- 最差情况：O(n2)
- 平均情况：O(nlogn)
基本思想
先确定一个“支点”（pivot），将所有小于“支点”的值都放在该点的左侧，大于“支点”的值都放在该点的右侧，然后对左右两侧不断重复这个过程，直到所有排序完成。
具体做法
- 确定“支点”（pivot）。虽然数组中任意一个值都能作为“支点”，但通常是取数组的中间值。
- 建立两端的指针。左侧的指针指向数组的第一个元素，右侧的指针指向数组的最后一个元素。
- 左侧指针的当前值与“支点”进行比较，如果小于“支点”则指针向后移动一位，否则指针停在原地。
- 右侧指针的当前值与“支点”进行比较，如果大于“支点”则指针向前移动一位，否则指针停在原地。
- 左侧指针的位置与右侧指针的位置进行比较，如果前者大于等于后者，则本次排序结束；否则，左侧指针的值与右侧指针的值相交换。
- 对左右两侧重复第2至5步。
CODE
function quickSort(arr) {
function change(index1, index2) {
[arr[index1], arr[index2]] = [arr[index2], arr[index1]];
}
function partition(left, right) {
const pivot = arr[Math.floor((left + right) / 2)];
let i = left;
let j = right;
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
change(i, j);
i++;
j--;
}
}
if (left < i - 1) {
partition(left, i - 1);
}
if (i < right) {
partition(i, right);
}
}
if (arr.length < 2) return arr;
partition(0, arr.length - 1);
return arr;
}
二路归并
将两个按值有序序列合并成一个按值有序序列
CODE
function merge(left, right) {
var result = [],
il = 0,
ir = 0;
while (il < left.length && ir < right.length) {
if (left[il] < right[ir]) {
result.push(left[il++]);
} else {
result.push(right[ir++]);
}
}
// 将剩余的的复制到result
while(left[il]){
result.push(left[il++]);
}
// 将剩余的的复制到result
while(right[ir]){
result.push(right[ir++]);
}
return result;
}
查询算法
二分查找法
递归实现
CODE
function binarySearch(arr, val, low = 0, high = arr.length) {
if (low > high)
return -1;
const mid = Math.floor((low + high) / 2);
if (arr[mid] < val) {
return binarySearch(arr, val, mid + 1, high);
} else if (arr[mid] > val) {
return binarySearch(arr, val, low, high - 1);
} else {
return mid;
}
}
字符串操作
翻转字符串
CODE
function reverseString(str){
return [...str].reverse().join('');
}
生成指定长度随机字符串
CODE
function randomString(n){
var str = 'abcdefghijklmnopqrstuvwxyz0123456789';
var tmp = '';
for(var i=0; i<n; i++) {
tmp += str.charAt(Math.round(Math.random()*str.length));
}
return tmp;
}
数组操作
数组去重
indexOf方法
CODE
var array = [1, 2, 1, 1, '1'];
function unique(array) {
var res = array.filter(function(item, index, array){
return array.indexOf(item) === index;
})
return res;
}
console.log(unique(array));
ES6 Set数据结构方法
CODE
var array = [1, 2, 1, 1, '1'];
function unique(array) {
return Array.from(new Set(array));
}
console.log(unique(array)); // [1, 2, "1"]
简化如下：
function unique(array) {
return [...new Set(array)];
}
var unique = (a) => [...new Set(a)]
其他
生成n到m之间的随机整数
CODE
function random(n, m){
return Math.floor(Math.random()*(m-n))+n;
}
Activity