算法01 常用排序算法
所有算法的动画演示
冒泡排序（Bubble Sort）
对相邻的两个对象进行比较，如果后者小于前者，把小的放前面
时间复杂度：O(n²)
// 对比arr中的第j+1项和第j项，如果第j+1项小于第j项，就把第j+1项和第j项调换位置。
// 如果没达到最终的顺序（从小到大），就继续找，继续换，直到达到最终效果
function bubbleSort(arr) {
for (var i = 0; i < arr.length - 1; i++) {
for (var j = 0; j < arr.length - 1; j++) {
if (arr[j + 1] < arr[j]) {
[tempArr[j], tempArr[j + 1]] = [tempArr[j + 1], tempArr[j]];
}
}
}
return arr;
}
（2018.4.3补充）
发现在内层循环时，可以改变内层循环的范围为 j<arr.length-1-i, 原因是
- 当
i=0的时候，里面的循环完整执行，第一遍排序，结果是将最大的数排到了最后 - 当
i=1的时候，里面的循环再次完整执行，由于最大的数已经在最后了，没有必要去比较数组的最后两项，这也是j<arr.length-1-i的巧妙之处
优化冒泡排序算法
对冒泡排序进行优化，设定一个变量flag，用于表明是否进行了位置交换，如果没有交换位置，则说明当前排序完成，结束循环
时间复杂度：O(n²)
function bubbleSort(arr) {
let isOver = false;
for (var i = 0; i < arr.length - 1; i++) {
isOver = true;
for (var j = 0; j < arr.length - 1; j++) {
if (arr[j + 1] < arr[j]) {
[tempArr[j], tempArr[j + 1]] = [tempArr[j + 1], tempArr[j]];
isOver = false;
}
}
// 内部循环一轮都不需要调换位置，说明全部排序已完成，没有必要再继续外部循环
if (isOver) {
return arr;
}
}
return arr;
}
选择排序（Selection Sort）
首先在乱序的数组中选择出最小的值，然后和每次循环后的数组第一位进行交换
时间复杂度：O(n²)
const x = [0, 5, 3, 2, 4, 1, 10];
function chooseSort (arr) {
let tempArr = [...arr];
for (let i = 0; i < tempArr.length; i++) {
let maxIndex = i;
for (let j = i; j < tempArr.length; j++) {
if (tempArr[j] > tempArr[maxIndex]) {
maxIndex = j
}
}
if (maxIndex !== i) {
[tempArr[i], tempArr[maxIndex]] = [tempArr[maxIndex], tempArr[i]];
}
}
return tempArr;
}
console.log(chooseSort(x))
插入排序（Insert Sort）
对数组进行循环，当循环到i时，认为i之前的项目都已经排好序了，对i+1进行处理，将i+1项插入到已经排好序的队列中，插入的方法就是从i+1开始，向回循环，两两比较，根据比较结果进行换位
时间复杂度：O(n²)
const x = [0, 5, 3, 2, 4, 1, 10];
function insertSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j > 0; j--) {
if (arr[j - 1] < arr[j]) {
[arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
}
}
}
return arr;
}
console.log(insertSort(x))
归并排序（Merge Sort）
把一个数组分为两个数组，左边排好序，右边排好序，然后合并到一起排序。
归并排序是分治法的典型实例，指的是将两个已经排序的序列合并成一个序列的操作
时间复杂度：O(nlogn)
排序过程：
var arr = [-11, 17, 12, 19, 0, -222];
function mergeSort(arr, s, e) {
if (s > e) { //起始位置大于终点位置，返回空数组
return [];
} else if (s == e) {
return [arr[s]]; //起始位置等于终点位置，说明数组里只有一个数字，返回只含一个数字的数组
}
var mIndex = Math.floor((s + e) / 2); //中间位置的Index
var arrL = mergeSort(arr, s, mIndex); //将左边的数组排序
var arrR = mergeSort(arr, mIndex + 1, e); //将右边的数组排序
var resultArr = []; //结果数组
while (arrL.length > 0 && arrR.length > 0) { //当左右两个数组都不为空时
if (arrL[0] < arrR[0]) {
resultArr.push(arrL.shift());
} else {
resultArr.push(arrR.shift());
}
if (arrL.length == 0) { //当左边的数组为空时
resultArr = resultArr.concat(arrR);
break;
} else if (arrR.length == 0) {
resultArr = resultArr.concat(arrL);
break;
}
}
return resultArr;
}
document.write(mergeSort(arr, 0, arr.length - 1));
快速排序（quickSort）
- 在数据集之中，选择一个元素作为"基准"（pivot）
- 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
- 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
var arr = [77, -33, 22, 32, 0, 2, 11];
function quickSort(arr) {
// 递归结束条件
if (arr.length <= 1) {
return arr;
}
// 选择基准元素，并且从原数组中暂时剔除
const index = Math.floor(arr.length / 2);
const base = arr.splice(index, 1)[0];
// 将数组分为左右组
let left = [];
let right = [];
// 对所有元素进行遍历，将大于基准值的放在左边，小于基准值的放在右边
for (let i = 0; i < arr.length; i++) {
(arr[i] < base ? right : left).push(arr[i])
}
// quickSort(left)对左边的合集进行递归
// quickSort(right)对右边的合集进行递归
// 连接起来，再加上基准元素就是完整合集
return quickSort(left).concat([base], quickSort(right))
}
document.write(quickSort(arr));
计数排序
时间复杂度为O(N)
用空间换时间的算法，适用于提前知道数字范围，并且相差范围不大的情况
将数字放到对应的数组对象中，然后进行排序
这种方法不能对应数组中有负数的情况
let arr = [100, 2, 3, 1, 5, 22, 33, 11, 22, 33];
function sort(arr) {
let temp = [];
for (let i = 0; i < arr.length; i++) {
if (!temp[arr[i]]) {
temp[arr[i]] = 1;
}
else {
temp[arr[i]]++;
}
}
let result = [];
for (let j = 0; j < temp.length; j++) {
if (temp[j]) {
for (let k = 0; k < temp[j]; k++) {
result.push(j)
}
}
}
return result;
}
console.log(sort(arr))