//归并排序须知:
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
1.自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第2种方法）
2.自下而上的迭代
// 将数组从中间分开 通过对比左右两个数组 索引为0的值 如果左边的小于右边的 将左边数组的第一个值 push到一个新数组中
// 否则 将右边数组的第一个值 push到新数组中
// 如果left/right 有一个 的值为空 进入下面的程序
// 如果left.length > 0 就将left里面剩余的值全部push到新数组中
// 否则 right.length > 0 就将right里面剩余的值全部push到新数组中
// 以此遍历递归 进行排序
代码
function mergeSort1 (arr) {
var len = arr.length;
if( len < 2 ) {
return arr
}
var middle = Math.floor(len/2);
var left = arr.slice(0, middle);
var right = arr.slice(middle);
return merge1(mergeSort1(left),mergeSort1(right))
}
function merge1(left, right) {
var result = [];
while(left.length > 0 && right.length > 0) {
if(left[0] < right[0]) {
result.push(left.shift())
}
else {
result.push(right.shift())
}
}
while(left.length) result.push(left.shift())
while(right.length) result.push(right.shift())
return result
}
冒泡排序
function bubbleSort(arr) {
var len = arr.length;
for (let i = 0; i < len; i++) {
for (let j = i + 1; j < len; j++) {
if(arr[i] > arr[j]) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr
}
console.log(bubbleSort(arr));
// 选择排序
function selectSort(arr) {
var len = arr.length;
var minIndex,temp;
for(var i = 0; i < len-1; i++) {
minIndex = i;
for(var j = i+1;j < len; j++) {
if(arr[j] < arr[minIndex]) {
minIndex = j
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp
}
return arr
}
console.log(selectSort(arr))
快速排序
var quickSort = function(arr) {
if (arr.length <= 1) {//如果数组长度小于等于1无需判断直接返回即可
return arr;
}
var pivotIndex = Math.floor(arr.length / 2);//取基准点
var pivot = arr.splice(pivotIndex, 1)[0];//取基准点的值,splice(index,1)函数可以返回数组中被删除的那个数
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]);//比基准点大的放在右边数组
}
}
//递归执行以上操作,对左右两个数组进行操作，直到数组长度为<=1；
return quickSort(left).concat([pivot], quickSort(right));
};
console.log(quickSort(arr))
