结论
冒泡排序 < 选择排序 < 插入排序 < 归并排序 < 快速排序（优）
1、冒泡排序
比较任何两个相邻的项，如果前者比后者大，则将它们互换位置。
const bubbleSort = (arr = []) => {
let len = arr.length
for (let i = 0; i < len; i++) {
// for (let j = 0; j < len - 1; j++) {
for (let j = 0; j < len - 1 - i; j++) { // 优化 len - 1 - i
if (arr[j] > arr[j + 1]) {
// 置换
let oldArr = arr[j];
let newArr = arr[j + 1];
arr[j] = newArr;
arr[j + 1] = oldArr;
}
}
}
return arr;
}
console.time(); // 用于测试程序执行的时长，结合console.timeEnd()使用
const bubble = bubbleSort(arr);
console.log('冒泡排序');
console.timeEnd();
// arr
// [9, 8, 7, 1]
// i = 0
// [8, 9, 7, 1]
// [8, 7, 9, 1]
// [8, 7, 1, 9]
// i = 1
// [7, 8, 1, 9]
// [7, 1, 8, 9]
// i = 2
// [1, 7, 8, 9]
// i = 3
// return arr
2、选择排序
找到数据结构中的最小值并将其放置在第一位，接着找到第二个最小值并将其放到第二位,依次类推。
const selectionSort = (arr) => {
let len = arr.length;
let indexMin;
for (let i = 0; i < len - 1; i++) {
indexMin = i;
for (let j = i; j < len; j++) {
if (arr[indexMin] > arr[j]) {
indexMin = j;
}
}
if (i !== indexMin) {
// 置换
let oldArr = arr[i];
let newArr = arr[indexMin];
arr[i] = newArr;
arr[indexMin] = oldArr;
}
}
return arr;
};
console.time();
const selection = selectionSort(arr)
console.log('选择排序');
console.timeEnd();
// arr
// [9, 8, 7, 1]
// i = 0
// [1, 8, 7, 9]
// i = 1
// [1, 7, 8, 9]
// i = 2
// return arr
3、插入排序
假定第一项已经排序，接着第二项和第一项比较， 第 N 项和前 N-1 项比较，最终将整个数组从小到大依次排序。
const insertionSort = (arr) => {
let len = arr.length;
let j;
let temp;
for (let i = 1; i < len; i++) {
j = i;
temp = arr[i];
while (j > 0 && arr[j - 1] > temp) {
// 置换
let oldArr = arr[j];
let newArr = arr[j - 1];
arr[j] = newArr;
arr[j - 1] = oldArr;
j--;
}
arr[j] = temp;
}
return arr;
};
console.time();
const insertion = insertionSort(arr)
console.log('插入排序');
console.timeEnd();
// arr
// [9, 8, 7, 1]
// i = 1
// [8, 9, 7, 1]
// i = 2
// [8, 7, 9, 1]
// [7, 8, 9, 1]
// i = 3
// [7, 8, 1, 9]
// [7, 1, 8, 9]
// [1, 7, 8, 9]
// return arr
4、插入排序
假定第一项已经排序，接着第二项和第一项比较， 第 N 项和前 N-1 项比较，最终将整个数组从小到大依次排序。
const insertionSort = (arr) => {
let len = arr.length;
let j;
let temp;
for (let i = 1; i < len; i++) {
j = i;
temp = arr[i];
while (j > 0 && arr[j - 1] > temp) {
// 置换
let oldArr = arr[j];
let newArr = arr[j - 1];
arr[j] = newArr;
arr[j - 1] = oldArr;
j--;
}
arr[j] = temp;
}
return arr;
};
console.time();
const insertion = insertionSort(arr)
console.log('插入排序');
console.timeEnd();
// arr
// [9, 8, 7, 1]
// i = 1
// [8, 9, 7, 1]
// i = 2
// [8, 7, 9, 1]
// [7, 8, 9, 1]
// i = 3
// [7, 8, 1, 9]
// [7, 1, 8, 9]
// [1, 7, 8, 9]
// return arr
5、归并排序（分治算法）
将原始数组切分成较小的数组，直到每个小数组只有一个元素，接着将小数组归并成较大的数组，最后变成一个排序完成的大数组。
归并排序.jpg
const mergeSortRec = (arr) => {
let len = arr.length;
if (len === 1) {
return arr;
}
let mid = Math.floor(len / 2);
let left = arr.slice(0, mid);
let right = arr.slice(mid, len);
return merge(mergeSortRec(left), mergeSortRec(right));
}
// 合并方法
const merge = (left, right) => {
let result = [];
let l = 0;
let r = 0;
while (l < left.length && r < right.length) {
if (left[l] < right[r]) {
result.push(left[l++]);
} else {
result.push(right[r++]);
}
}
while (l < left.length) {
result.push(left[l++]);
}
while (r < right.length) {
result.push(right[r++]);
}
return result;
}
console.time();
const mergeS = mergeSortRec(arr);
console.log('归并排序');
console.timeEnd();
// arr
// [9, 8, 7, 1]
// 1
// [9] [8] [7] [1]
// [8,9] [1,7]
// 2
// [8,9] [1,7] // 1与8比较，1 push，7与8比较，7 push，然后一次把8 9 push
// [1, 7, 8, 9]
// return result
6、快速排序（分治算法）
找基准（一般是以中间项为基准）；遍历数组，小于基准的放在left，大于基准的放在right；递归。
const quickSort = (arr) => {
//如果数组<=1,则直接返回
if (arr.length <= 1) {
return arr;
}
let pivotIndex = Math.floor(arr.length / 2);
//找基准，并把基准从原数组删除
let pivot = arr.splice(pivotIndex, 1)[0];
//定义左右数组
let left = [];
let right = [];
//比基准小的放在left，比基准大的放在right
let len = arr.length;
for (let i = 0; i < len; i++) {
if (arr[i] <= pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
//递归
return quickSort(left).concat([pivot], quickSort(right));
}
console.time();
const quick = quickSort(arr);
console.log('快速排序');
console.timeEnd();
// arr
// [9, 8, 7, 1]
// 1
// 基准为7，1比7小，左边为[1]，9、8比7大，右边为[9,8]
// [9,8]
// 基准为8，左边为[8]，右边为[9]
// [1,7,9,8]
性能测试：生成指定个数的随机数组
const generateArr = (num = 10) => {
let arr = []
for (let i = 0; i < num; i++) {
let item = Math.floor(Math.random() * (num + 1))
arr.push(item)
}
return arr
}
// 生成60个项的数组
const arr = generateArr(9999)
console.time(); // 用于测试程序执行的时长，结合console.timeEnd()使用
const bubble = bubbleSort(arr);
console.log(bubble);
console.timeEnd();
网友评论