选择排序
递归写法
思路：每次找到最小的数放在前面，然后后面的数做一样的事情
let min = (numbers) => {
if (numbers.length > 2) {
return min([numbers[0], min(numbers.slice(1))]);
} else {
return Math.min.apply(null, numbers);
}
}; //求数组最小值
let minIndex = (numbers) => numbers.indexOf(min(numbers)); //拿到最小值的下标
let sort = (numbers) => {
if (numbers.length > 2) {
let index = minIndex(numbers); //最小值下标
let min = numbers[index]; //找到最小值
numbers.splice(index, 1); //把当前最小值从数组冲剔除
return [min].concat(sort(numbers)); //递归：继续排序剩余数组
} else {
return numbers[0] < numbers[1] ? numbers : numbers.reverse();
}
};
循环写法
思路大致相同：先把最小值放在前面，后面执行i++
let minIndex = (numbers) => {
let index = 0;
for (let i = 1; i < numbers.length; i++) {
if (numbers[i] < numbers[index]) {
index = i; //遍历过程中每遇到一个比当前数小的数就认为是最小值，直到遍历结束
}
}
return index;
};
let swap = (array, i, j) => {
let temp = array[i]; //把i放入容器temp
array[i] = array[j]; //j给i
array[j] = temp; //容器中的内容i给j，实现交换
};
let sort = (numbers) => {
for (let i = 0; i < numbers.length - 1; i++) {
let index = minIndex(numbers.slice(i)) + i;
if (index != i) {
swap(numbers, index, i);
}
}
return numbers;
};
快速排序
思路：以某个数为基准，比它小的数放前面，比它大的数放后面，对每个数都做这样的操作实现排序
//快速排序 递归思路
let quickSort = (arr) => {
if (arr.length <= 1) {
return arr;
}
let pivotIndex = Math.floor(arr.length / 2); //设定基准数的下标
let pivot = arr.splice(pivotIndex, 1)[0]; //拿出基准数，因为会返回一个数组所以要标注第零项
let left = []; //比标准数字小的数组
let right = []; //比标准数大的数组
for (let 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)); //实现排序
};
归并算法
思路：不找基准数，左边一半排好序，右边一半排好序，最后左右两边进行归并。
let mergeSort = (arr) => {
if (arr.length === 1) {
return arr;
}
let left = arr.slice(0, Math.floor(arr.length / 2)); //左边数组截取为0到数组的2分之1
let right = arr.slice(Math.floor(arr.length / 2)); //右边数组截取为从2分之1开始
return merge(mergeSort(left), mergeSort(right)); //对左右两部分继续进行mergeSort的操作后进行归并
};
let merge = (a, b) => {
if (a.length === 0) return b;
if (b.length === 0) return a; //特殊情况a或者b为空数组则直接返回另一半
return a[0] > b[0]
? [b[0]].concat(merge(a, b.slice(1)))
: [a[0]].concat(merge(a.slice(1), b)); //实现归并排序
};
计数排序
思路：用一个哈希表做记录，发现数字N就记N：1，如果再次发现N就加一
最后把哈希表的key都打出来
let countingSort = (arr) => {
let hashTable = {};
let result = [];
let max = 0;
for (let i = 0; i < arr.length; i++) {
//遍历数组
if (!(arr[i] in hashTable)) {
hashTable[arr[i]] = 1; //把数组内容写进来
} else {
hashTable[arr[i]] += 1;
}
if (arr[i] > max) {
max = arr[i]; //max会成为数组内最大的
}
}
for (let n = 0; n <= max; n++) {
//遍历哈希表
if (n in hashTable) {
for (let i = 0; i < hashTable[n]; i++) {
//再次遍历,拿到哈希的value，实现多次输出
result.push(n);
}
}
}
return result;
};
以上四种算法的时间复杂度
选择排序 O(n^2)
快速排序 O(n log2 n)
归并排序 O(n log2 n)
计数排序 O(n + max)
还有四种排序算法是：
冒泡排序
插入排序
希尔排序
基数排序
网友评论