算法(五)--阶段思考
2018-03-22 本文已影响0人
yu580
这短时间学习了各种基本排序算法。我们来捋一捋这些算法。
选择和冒泡排序:
大多数人最先接触的排序,因为好理解,在处理数据量不大的情况也能很好的应对。
插入排序:
插入排序和选择排序的区别就是插入排序可以提前结束。
执行时 插入排序比选择排序慢 因为不停的交换位置比较耗时,可以优化。
但是对于一个近乎有序的数组进行排序,插入排序性能要远远优于选择排序
所以插入排序是很有实际意义的。(例如我们在查日志的时候,要按时间排序,因为偶尔的问题导致个别不是按时间的 这个时候插入排序的优势就能完全发挥出来了)
归并和快速排序:
归并算法和快速排序的算法都采用了分治算法的思想:
顾名思义。分而治之,就是将原有问题分割成同等结构的子问题。之后将子问题逐一解决后,原问题也就解决。
快排学习了之后我们能解决那些问题呢?
例如我们要知道一个值在数组排好序之后的位置。
我们只需要稍微改一下快速排序就可以很快的实现:
/**
* 查询数组中排在第m位的值
* @param {*查询的数组} arr
* @param {* 数组长度} n
* @param {* 查询的下标+1} m //查询数组的第多少位
*/
this.selectionOne = (arr, n, m) => {
var _this = this
__quickSort(arr, 0, n - 1, m)
function __quickSort(arr, l, r, m) {
if (l >= r) {
return
}
//基本上所有的高级排序在底层都可以采用插入排序进行优化
// if (r - l <= 10) {
// _this.insertionSort2(arr, l, r)
// return
// }
let p = __partition(arr, l, r)
if (p > m) {
__quickSort(arr, l, p - 1, m)
} else if (p < m) {
__quickSort(arr, p + 1, r, m)
} else {
log(arr[p])
}
}
//对arr进行partition操作返回一个索引下标 p
//满足 arr[l,p1]里面所有的值都小于 arr[p] , arr[p+1,r]里面所有的值都大于 arr[p]
function __partition(arr, l, r) {
let n = Math.floor(Math.random() * (r - l + 1) + l, 10)
swap(arr, l, n)
let v = arr[l]
let i = l + 1, p = r
while (true) {
while (i <= r && arr[i] < v) {
i++
}
while (p >= l + 1 && arr[p] > v) {
p--
}
if (i > p) {
break
}
swap(arr, i, p)
i++
p--
}
swap(arr, l, p)
return p
}
}
下面我们说一下数组打乱:
方法一:
[12,4,16,3].sort(function() {
return .5 - Math.random();
});
该方法打乱数组不是完全的,根据网上资料:
chrome v8引擎 在处理 sort 方法时,使用了插入排序和快排两种方案。
当目标数组长度小于10时,使用插入排序;反之,使用快排
Math.random 的随机数生成器和 java 一样以当前时间为随机数种子
这样在测试数据很大的时候会导致打乱的不是很均匀。
方法二:
称之为洗牌算法:
this.shuffle = (arr, n) => {
for (let i = 1; i < arr.length; i++) {
const random = Math.floor(Math.random() * (i + 1));
[arr[i], arr[random]] = [arr[random], arr[i]];
}
return arr;
};
顺序拿到数组中的一位,和数组中随机一位进行换位,保证每个位置都被打乱过。
以上都是个人理解如有不对之处还望指正交流!