前言
作为前端开发者而言，算法虽然是一种只需要涉猎的领域，但它对于我而言，确是一道不得不踏过的槛。原因有俩，其一，前端在遇到复杂的逻辑问题时可以有更好地去理解与分析；其二，个人的竞争力也会比较突出（大厂面经必备）
友情提示5道基础算法题，阅读时间为5-10分钟
下面来看下有哪些排序算法
冒泡排序
主要思路：比较相邻两个项，如果第一个比第二个大，就交换位置。
var bubbleSort = function (array) {
var len = array.length;
//循环length不减一，用于获取数组循环轮数，以便于相邻数值的比较
for(var i =0; i < len; i++){
for(var j =0; j < len - 1; j++){
if(array[j] > array[j+1]){
var firstVal = array[j];
array[j] = array[j+1];
array[j+1] = firstVal;
}
}
}
}
选择排序
选择排序，也称为原址比较算法。主要思路是，找到数据结构中的最小值并将其放置在第一位，接着找到第二小值放到第二位。以此类推。
var selectionSort = function (array) {
var indexMin;
for (var i = 0; i < array.length-1; i++) {
indexMin = i;
//循环length不减一，用于获取数组最后一个元素与前一个元素进行比较
for (var j = i; j < array.length; j++) {
if (array[indexMin] > array[j]) {
indexMin = j;
}
}
if (i !== indexMin) {
var ux = array[i];
array[i] = array[indexMin];
array[indexMin] = ux;
}
}
}
插入排序
插入排序，相较前两种算法性能是有所提高，思路是将第一项与第二项比较，得出正确排序；接着与第三项比较，得出1，2，3项的正确排序，以此类推
var insertionSort = function (array) {
for (var i = 0; i < array.length; i++) {
var j = i;
var temp = array[i];
while(j > 0 && array[j-1] > temp) {
array[j] = array[j-1];
j--;
}
array[j] = temp;
}
}
归并排序
归并排序,是一个比较优化的算法,思路是将其递归分解数列,再合并数列
var mergeSort = function (array) {
var len = array.length;
if (len <= 1) {
return array;
}
var mid = Math.floor(len / 2);
var left = array.slice(0, mid);
var right = array.slice(mid, len);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var i = 0, j = 0, result = [];
while(i < left.length && j < right.length) {
if (left[i] > right[j]) {
result.push(right[j++]);
} else {
result.push(left[i++]);
}
}
while (i < left.length) {
result.push(left[i++]);
}
while (j < left.length) {
result.push(left[j++]);
}
return result;
}
快速排序
快速排序，常用的一种排序方法。主要思路是取一个基准点，以基准点为中心，分割成小于基准点或者大于基准点的两个数组，按顺序递归排列
var quickSort = function (array) {
if (array.length <= 1) {
return array;
}
var mid = Math.floor(array.length / 2);
var temp = array.splice(mid, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < array.length; i++) {
if (array[i] < temp) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return quickSort(left).concat(temp, quickSort(right));
}
思考
这几种算法有哪些优缺点？
首先，选择排序跟冒泡排序是比较简单的算法，然而这两种排序算法在运行性能上都是比较差的。只考虑用于学习；
其次，插入排序跟前两者一样，都是通过比较来进行排序，在小型数组方面性能相对较好，但还是不支持用于实战；
对于归并排序与快速排序而言，两者的相同点在于采用分治的思想，只不过快排没有将数组切割。而在实用性方面，归并与快排都是能进行实用的算法，但快排应该是最常用的一种。
其他排序算法呢？
其实排序算法还有堆排序、希尔排序、计数排序、桶排序、基数排序等，只不过对这几种掌握不深，不敢班门弄斧。后面对算法更熟悉些，会进行这几种算法的学习并且与前几种算法的优势比较
网友评论