冒泡排序
执行时间
image.png
let arr = [];
for (let i = 0; i < 80000; i++) {
arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');
function sort(arr) {
let temp;
// 优化点，如果某次冒泡并没有交换，那后面都不需要交换了
let flag = false;
for (let i = 1; i < arr.length; i++) {
for (let j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) {
flag = true;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
if (flag) {
flag = false;
} else {
break;
}
}
}
选择排序
执行时间
image.png
let arr = [];
for (let i = 0; i < 80000; i++) {
arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');
function sort(arr) {
let temp;
for (let i = 0; i < arr.length - 1; i++) {
let minIndex = i;
temp = arr[i];
for (let j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
插入排序
执行时间
image.png
let arr = [];
for (let i = 0; i < 80000; i++) {
arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');
console.log(arr);
function sort(arr) {
for (let i = 1; i < arr.length; i++) {
let insert = i - 1;
let temp = arr[i];
while (insert >= 0 && temp < arr[insert]) {
arr[insert + 1] = arr[insert];
insert--;
}
arr[insert + 1] = temp;
}
}
希尔排序-
-
交换法
执行时间
image.png
let arr = [];
for (let i = 0; i < 80000; i++) {
arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');
function sort(arr) {
let len = arr.length;
let temp;
do {
len = Math.floor(len / 2);
for (let i = len; i < arr.length; i++) {
for (let j = i - len; j >= 0; j -= len) {
if (arr[j + len] < arr[j]) {
temp = arr[j];
arr[j] = arr[j + len];
arr[j + len] = temp;
}
}
}
} while (len > 1);
}
-
插入法
执行时间
let arr = [];
for (let i = 0; i < 80000; i++) {
arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr);
console.timeEnd('x');
function sort(arr) {
let gap = Math.floor(arr.length / 2);
while (gap >= 1) {
for (let i = gap; i < arr.length; i++) {
let j = i - gap;
let temp = arr[i];
while (j >= 0 && temp < arr[j]) {
arr[j + gap] = arr[j];
j -= gap;
}
arr[j + gap] = temp;
// let j = i;
// let temp = arr[j];
// if (arr[j] < arr[j - gap]) {
// while (j - gap >= 0 && temp < arr[j - gap]) {
// arr[j] = arr[j - gap];
// j -= gap;
// }
// arr[j] = temp
// }
}
gap = Math.floor(gap / 2);
}
}
快速排序
执行时间
image.png
let arr = [];
for (let i = 0; i < 80000; i++) {
arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr, 0, arr.length - 1);
console.timeEnd('x');
function sort(arr, left, right) {
let l = left;
let r = right;
const middle = arr[Math.floor((left + right) / 2)];
let temp;
while (l < r) {
while (arr[l] < middle) {
l++;
}
while (arr[r] > middle) {
r--;
}
if (l == r) {
r -= 1;
l += 1;
break;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
// 减少一次没必要的比较
if(arr[l]==middle){
r--;
}else if(arr[r]==middle){
l++;
}else{
l++;
r--;
}
}
if (left < r) {
sort(arr, left, r)
}
if (right > l) {
sort(arr, l, right)
}
}
归并排序
执行时间
let arr = [];
for (let i = 0; i < 80000; i++) {
arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr, 0, arr.length - 1);
console.timeEnd('x');
function sortOrigin(arr, left, mid, right) {
let i = left;
let j = mid + 1;
let temp = [];
let t = 0;
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
temp[t] = arr[i];
i++;
} else {
temp[t] = arr[j];
j++;
}
t++;
}
while (i < mid) {
temp[t] = arr[i];
i++;
t++;
}
while (j < right) {
temp[t] = arr[j];
j++;
t++;
}
t = 0;
while (left <= right) {
arr[left] = temp[t];
t++;
left++;
}
}
function sort(arr, left, right) {
if (left < right) {
let mid = Math.floor((left + right) / 2);
sort(arr, left, mid);
sort(arr, mid + 1, right);
sortOrigin(arr, left, mid, right)
}
}
基数排序
执行时间
let arr = [];
for (let i = 0; i < 80000; i++) {
arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr, 0, arr.length - 1);
console.timeEnd('x');
function sort(arr) {
var max = 0;
for (let i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
var maxLength = (max + '').length;
let bet = [];
for (let i = 0; i < 10; i++) {
bet[i] = [];
}
let betLength = new Array(10).fill(0);
for (let i = 0, step = 1; i < maxLength; i++, step *= 10) {
for (let j = 0; j < arr.length; j++) {
let num = Math.floor(arr[j] / step) % 10;
bet[num][betLength[num]] = arr[j];
betLength[num]++;
}
let t = 0;
for (let k = 0; k < 10; k++) {
if (betLength[k]) {
for (let d = 0; d < betLength[k]; d++) {
arr[t] = bet[k][d];
t++;
}
betLength[k] = 0;
}
}
}
}
sort(arr);
堆排序
执行时间
image.png
let arr = [];
for (let i = 0; i < 80000; i++) {
arr[i] = Math.floor(Math.random() * 80000);
}
console.time('x');
sort(arr, 0, arr.length - 1);
console.timeEnd('x');
function start(arr) {
var i = Math.floor(arr.length / 2) - 1
for (var j = i; j >= 0; j--) {
sort(arr, j, arr.length)
}
var temp;
for (var j = arr.length - 1; j > 0; j--) {
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
sort(arr, 0, j)
}
}
function sort(arr, i, len) {
let temp = arr[i];
for (let j = i * 2 + 1; j < len; j = j * 2 + 1) {
if (j + 1 < len && arr[j] < arr[j + 1]) {
j++;
}
if (temp < arr[j]) {
arr[i] = arr[j]
i = j
} else {
break;
}
}
arr[i] = temp;
}
start(arr)
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2hny1q3rjeyo8
