- 首页 > it技术 > >
function createArray(num) {
let res = [];
for (let i = 0;
i < num;
i++) {
res.push(Math.floor(Math.random() * num));
}
return res;
}function checkArraySorted(arr) {
let res = true;
for (let i = 0, length = arr.length - 1;
i < length;
i++) {
if (arr[i] > arr[i + 1]) {
res = false;
break;
}
}
return res;
}let arr = createArray(10000);
/**
* 冒泡排序
* 复杂度: O(n2)
* 327.085ms
*/
function bubbleSort(arr) {
let length = arr.length;
for (let i = 0;
i < length;
i++) {
for (let j = 0;
j < length - i - 1;
j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
}/**
* 选择排序
* 复杂度: O(n2)
* 94.6 ms
*/
function selectSort() {
let length = arr.length;
for (let i = 0;
i < length;
i++) {
let minIndex = i;
for (let j = i + 1;
j < length;
j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex > i) {
[arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
}
}
}/**
* 插入排序
* 时间复杂度: 最差为O(n2), 空间复杂度: O(1)
* 5.284ms
* 思想: 假设前 i - 1 个元素已经排序好了, 为第 i 个元素在前 i 个元素中找到正确的位置
* 适合: nearly sorted数组
* 特性: 稳定;
对于 nearly sorted 数组, 时间复杂度降为 O(1)
*/
function insertSort(arr) {
let length = arr.length;
for (let outer = 1;
outer < length;
outer++) {
let inner = outer;
while (inner > 0 && arr[outer] < arr[inner - 1]) {
arr[inner] = arr[inner - 1];
inner--;
}
arr[inner] = arr[outer];
}
}/**
* 归并排序
* 时间复杂度: O(nlogn) 空间复杂度: O(nlogn)
* 27.349ms
*/
function mergeSort(arr) {
if (arr.length > 1) {
let mid = arr.length >> 1;
let left = mergeSort(arr.slice(0, mid));
let right = mergeSort(arr.slice(mid));
arr = merge(left, right);
}
return arr;
function merge(left, right) {
let i = j = 0;
let res = [];
while (left[i] && right[j]) {
if (left[i] < right[j]) {
res.push(left[i]);
i++;
} else {
res.push(right[j]);
j++;
}
}
return res.concat(left[i] ? left.slice(i) : right.slice(j));
}
}/**
* 快速排序
* 时间复杂度: O(nlogn)
* 22.066ms
*
*/
function quickSort(arr) {
if (arr.length < 2) {
return arr;
}
let base = arr[0];
let less = [];
let greater = [];
for (let i = 1, length = arr.length;
i < length;
i++) {
if (arr[i] > base) {
greater.push(arr[i]);
} else {
less.push(arr[i]);
}
}return quickSort(less).concat(base).concat(quickSort(greater));
}function quickSort2(arr) {
return quick(arr, 0, arr.length - 1);
function quick(arr, left, right) {
if (right > left) {
let index = partition(arr, left, right);
if (left < index - 1) {
quick(arr, left, index - 1);
}
quick(arr, index, right);
}
return arr;
}
function partition(arr, left, right) {
let pivot = arr[(left + right) >> 1];
while (left <= right) {
while (arr[left] < pivot) {
left++;
}
while (arr[right] > pivot) {
right--;
}
if (left <= right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
return left;
}
}console.time();
arr = quickSort2(arr);
console.timeEnd();
console.log(checkArraySorted(arr));
推荐阅读
