冒泡排序
执行时间
image.png
代码语言：javascript复制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
代码语言：javascript复制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
代码语言：javascript复制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
代码语言：javascript复制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
代码语言：javascript复制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
代码语言：javascript复制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)
