Skip to content

算法 #18

Open
Open
算法#18

Description

@Leechikit
Leechikit
opened on Mar 27, 2018

算法

排序算法

快速排序

快速排序（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;
}

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions