[TOC]
排序算法
1. 冒泡排序
算法描述:
- 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
- 针对所有的元素重复以上的步骤,除了最后一个;
- 重复步骤1~3,直到排序完成。
function sort(arr) {
var ar = []; var tmp;
for (var i = 0; i < arr.length; i++) {
for (var j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp;
}
}
}
console.log(arr)
}
sort([3, 9, 2])
2. 快读排序
快速排序,又称划分交换排序。以分治法为策略实现的快速排序算法。
数组中指定一个元素作为标尺,比它大的放到该元素后面,比它小的放到该元素前面,然后在新的两边中重复上面的步骤。
快速排序分三步:
- 选基准:在数据结构中选择一个元素作为基准(pivot)
- 划分区:参照基准元素值的大小,划分无序区,所有小于基准元素的数据放入一个区间,所有大于基准元素的数据放入另一区间,分区操作结束后,基准元素所处的位置就是最终排序后它应该所处的位置
- 递归:对初次划分出来的两个无序区间,递归调用第 1步和第 2步的算法,直到所有无序区间都只剩下一个元素为止。
function quickSort(arr) {
if (arr.length <= 1) return arr;
// 找基准点
var pivot = arr.splice(0, 1)[0];
var left = [];
var right = [];
// 划分区域,小的在左边,大的在右边
for (var 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));
}
var arr = [10, 2, 9, 20, 4, 1, 7, 15];
console.log(quickSort(arr));
十大经典排序算法:
https://www.cnblogs.com/onepixel/articles/7674659.html
https://www.cnblogs.com/beli/p/6297741.html
https://www.cnblogs.com/liyongshuai/p/7197962.html