选择排序与归并排序
1.选择排序：1.选择排序：选择排序是一个简单直观的排序方法，重复“从待排序的数据中寻找最小值，将其与序列最左边的数字进行交换”选择排序使用了线性查找来寻找最小值，因此在第 1 轮中需要比较 n -1 个数字，第2 轮需要比较 n -2 个数字……到第 n -1 轮的时候就只需比较 1 个数字了。因此，总的比较次数与冒泡排序的相同，都是 (n-1)+(n-2)+…+1 ≈ n2 /2 次。
//选择排序
function selsetSort(arr){
var len = arr.length;
var index;
for(var i=0;i<len-1>arr[j]){//寻找最小值
index=j;//保存最小值的索引
}
}
if(index!=i){
var temp =arr[i];
arr[i]=arr[index];
arr[index]=temp; }
}
return arr;
}</len-1> 2.归并排序：归并排序中，分割序列所花费的时间不算在运行时间内（可以当作序列本来就是分割好的）。在合并两个已排好序的子序列时，只需重复比较首位数据的大小，然后移动较小的数据，因此只需花费和两个子序列的长度相应的运行时间。也就是说，完成一行归并所需的运行时间取决于这一行的数据量。
function mergeSort (arr) {
let len = arr.length
if (len < 2) {
return arr
}
let middle = Math.floor(len/2)
//拆分成两个子数组
let left = arr.slice(0, middle)
let right = arr.slice(middle,len)
//递归拆分
let mergeSortLeft = mergeSort(left)
let mergeSortRight = mergeSort(right)
//合并
return merge( mergeSortLeft,mergeSortRight)
}
const merge = (left, right) => {
const result = [];
while (left.length && right.length) {
// 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
if (left[0] <= right[0]) {
result.push(left.shift()); //每次都要删除left或者right的第一个元素，将其加入result中
} else {
result.push(right.shift());
}
}
//将剩下的元素加上
while (left.length) result.push(left.shift());
while (right.length) result.push(right.shift());
return result;
}; 
投递牛客等公司10个岗位 >
