How to implement various sorting methods using js
Below I will share with you an article (detailed explanation) on the differences between various sorting methods and sort methods based on js. It has a good reference value and I hope it will be helpful to everyone.
I had a whim today and wanted to know whether the sort method has advantages over various sortings, so I made a test by referring to other people's codes. The results were surprising. Here is the code.
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width,initial-scale=1.0,maximum-scale=1.0,user-scalable=0">
<title>图片列表生成交互组件</title>
<style>
* {
margin: 0;
border: 0;
}
html, body {
height: 100%;
}
#p {
height: 100%;
width: 100%;
}
</style>
</head>
<body>
<p id="p"></p>
<script src="myNeedExtend.js"></script>
<script>
// ---------- 一些排序算法
Sort = {
// 利用sort进行排序
systemSort:function(array){
return array.sort(function(a, b){
return a - b;
});
},
// 冒泡排序
bubbleSort:function(array){
var i = 0, len = array.length,
j, d;
for(; i<len; i++){
for(j=0; j<len; j++){
if(array[i] < array[j]){
d = array[j];
array[j] = array[i];
array[i] = d;
}
}
}
return array;
},
// 快速排序
quickSort:function(array){
//var array = [8,4,6,2,7,9,3,5,74,5];
//var array =[0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
var i = 0;
var j = array.length - 1;
var Sort = function(i, j){
// 结束条件
if(i == j ){ return };
var key = array[i];
var tempi = i; // 记录开始位置
var tempj = j; // 记录结束位置
while(j > i){
// j <<-------------- 向前查找
if(array[j] >= key){
j--;
}else{
array[i] = array[j]
//i++ ------------>>向后查找
while(j > ++i){
if(array[i] > key){
array[j] = array[i];
break;
}
}
}
}
// 如果第一个取出的 key 是最小的数
if(tempi == i){
Sort(++i, tempj);
return ;
}
// 最后一个空位留给 key
array[i] = key;
// 递归
Sort(tempi, i);
Sort(j, tempj);
}
Sort(i, j);
return array;
},
// 插入排序
insertSort:function(array){
// http://baike.baidu.com/image/d57e99942da24e5dd21b7080
// http://baike.baidu.com/view/396887.htm
// var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
var i = 1, j, temp, key, len = array.length;
for(; i < len; i++){
temp = j = i;
key = array[j];
while(--j > -1){
if(array[j] > key){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = key;
}
return array;
},
// 希尔排序
shellSort:function(array){
// http://zh.wikipedia.org/zh/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
// var array = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10];
// var tempArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1];
// reverse() 在维基上看到这个最优的步长 较小数组
var tempArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1];
//针对大数组的步长选择
var i = 0;
var tempArrLength = tempArr.length;
var len = array.length;
var len2 = parseInt(len/2);
for(;i < tempArrLength; i++){
if(tempArr[i] > len2){
continue;
}
tempSort(tempArr[i]);
}
// 排序一个步长
function tempSort(temp){
//console.log(temp) 使用的步长统计
var i = 0, j = 0, f, tem, key;
var tempLen = len%temp > 0 ? parseInt(len/temp) + 1 : len/temp;
for(;i < temp; i++){// 依次循环列
for(j=1;/*j < tempLen && */temp * j + i < len; j++){
//依次循环每列的每行
tem = f = temp * j + i;
key = array[f];
while((tem-=temp) >= 0){
// 依次向上查找
if(array[tem] > key){
array[tem+temp] = array[tem];
}else{
break;
}
}
array[tem + temp ] = key;
}
}
}
return array;
}
};
testArrs = [];
for (var i = 10000000; i > 0; i--) {
testArrs.push(i);
}
function test(fun,arr) {
console.log(arr);
var oldTime = +new Date();
var new_arr = Sort[fun](arr);
var newTime = +new Date();
console.log(new_arr);
console.log(newTime-oldTime);
}
/*
* sort排序 systemSort
* 冒泡排序 bubbleSort
* 快速排序 quickSort
* 插入排序 insertSort
* 希尔排序 shellSort
*
* */
test("systemSort",testArrs);
</script>
</body>
</html>The above method passes the test time, and then analyzes which sorting method saves time. Time is life. Using the correct method can save a lot of time, especially when big data is running.
First look at the time it takes to process an array of 10,000 lengths:
* sort sorting systemSort 11
* Bubble sort bubbleSort 169
* quick sort quickSort 144
* insertion sort insertSort 139
* Hill sort shellSort 3
Test 100,000-long array data:
* sort sorting systemSort 63
* Bubble sorting bubbleSort 16268
* Quick sorting quickSort reports an error directly
* Insertion sorting insertSort 13026
* Hill sorting shellSort 8
Test an array with a length of one million:
* sort sort systemSort 575
* Bubble sort bubbleSort time unknown
* Quick sort quickSort reports an error directly
* Insertion sort insertSort crashes directly
* Hill sort shellSort 93
Test an array of 10 million long:
* sort sorting systemSort 7039
* Bubble sort bubbleSort not tested
* quick sort quickSort not tested
* insertion sort insertSort not tested
* Hill sorting shellSort 1225
Testing an array of 100 million long:
* sort systemSort crashes directly
* Bubble sort bubbleSort not tested
* Fast Sort quickSort Not tested
* Insertion sort insertSort Not tested
* Hill sort shellSort 19864
Finally passed the test,In the worst case , I found that Hill sorting is still the best, and it is even faster than the system sorting. It is really surprising. In this way, everyone can see what method needs to be used for sorting under what circumstances.
Then We test under random conditions:
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width,initial-scale=1.0,maximum-scale=1.0,user-scalable=0">
<title>图片列表生成交互组件</title>
<style>
* {
margin: 0;
border: 0;
}
html, body {
height: 100%;
}
#p {
height: 100%;
width: 100%;
}
</style>
</head>
<body>
<p id="p"></p>
<script src="myNeedExtend.js"></script>
<script>
// ---------- 一些排序算法
Sort = {
// 利用sort进行排序
systemSort:function(array){
return array.sort(function(a, b){
return a - b;
});
},
// 冒泡排序
bubbleSort:function(array){
var i = 0, len = array.length,
j, d;
for(; i<len; i++){
for(j=0; j<len; j++){
if(array[i] < array[j]){
d = array[j];
array[j] = array[i];
array[i] = d;
}
}
}
return array;
},
// 快速排序
quickSort:function(array){
//var array = [8,4,6,2,7,9,3,5,74,5];
//var array =[0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
var i = 0;
var j = array.length - 1;
var Sort = function(i, j){
// 结束条件
if(i == j ){ return };
var key = array[i];
var tempi = i; // 记录开始位置
var tempj = j; // 记录结束位置
while(j > i){
// j <<-------------- 向前查找
if(array[j] >= key){
j--;
}else{
array[i] = array[j]
//i++ ------------>>向后查找
while(j > ++i){
if(array[i] > key){
array[j] = array[i];
break;
}
}
}
}
// 如果第一个取出的 key 是最小的数
if(tempi == i){
Sort(++i, tempj);
return ;
}
// 最后一个空位留给 key
array[i] = key;
// 递归
Sort(tempi, i);
Sort(j, tempj);
}
Sort(i, j);
return array;
},
// 插入排序
insertSort:function(array){
// http://baike.baidu.com/image/d57e99942da24e5dd21b7080
// http://baike.baidu.com/view/396887.htm
// var array = [0,1,2,44,4,324,5,65,6,6,34,4,5,6,2,43,5,6,62,43,5,1,4,51,56,76,7,7,2,1,45,4,6,7];
var i = 1, j, temp, key, len = array.length;
for(; i < len; i++){
temp = j = i;
key = array[j];
while(--j > -1){
if(array[j] > key){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = key;
}
return array;
},
// 希尔排序
shellSort:function(array){
// http://zh.wikipedia.org/zh/%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F
// var array = [13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10];
// var tempArr = [1750, 701, 301, 132, 57, 23, 10, 4, 1];
// reverse() 在维基上看到这个最优的步长 较小数组
var tempArr = [1031612713, 217378076, 45806244, 9651787, 2034035, 428481, 90358, 19001, 4025, 836, 182, 34, 9, 1];
//针对大数组的步长选择
var i = 0;
var tempArrLength = tempArr.length;
var len = array.length;
var len2 = parseInt(len/2);
for(;i < tempArrLength; i++){
if(tempArr[i] > len2){
continue;
}
tempSort(tempArr[i]);
}
// 排序一个步长
function tempSort(temp){
//console.log(temp) 使用的步长统计
var i = 0, j = 0, f, tem, key;
var tempLen = len%temp > 0 ? parseInt(len/temp) + 1 : len/temp;
for(;i < temp; i++){// 依次循环列
for(j=1;/*j < tempLen && */temp * j + i < len; j++){
//依次循环每列的每行
tem = f = temp * j + i;
key = array[f];
while((tem-=temp) >= 0){
// 依次向上查找
if(array[tem] > key){
array[tem+temp] = array[tem];
}else{
break;
}
}
array[tem + temp ] = key;
}
}
}
return array;
}
};
testArrs = [];
for (var i = 0; i < 10000000; i++) {
testArrs.push(Math.random());
}
function test(fun,arr) {
var oldTime = +new Date();
var new_arr = Sort[fun](arr);
var newTime = +new Date();
console.log(fun);
console.log(newTime-oldTime);
}
/*
* sort排序 systemSort
* 冒泡排序 bubbleSort
* 快速排序 quickSort
* 插入排序 insertSort
* 希尔排序 shellSort
*
* */
test("systemSort",testArrs);
//test("bubbleSort",testArrs);
//test("quickSort",testArrs);
test("insertSort",testArrs);
test("shellSort",testArrs);
</script>
</body>
</html>Test a 10 million-long array:
* sort sorting systemSort 8842
* Bubble sort bubbleSort not tested
* Quick sort quickSort not tested
* Insertion sort insertSort 45
* Hill sort shellSort 1133
In unknown situations Under better circumstances, insertion sort is the most efficient
The above is what I compiled for everyone. I hope it will be helpful to everyone in the future.
Related articles:
Detailed explanation of the separation and combination of vue-admin and backend (flask)
Detailed explanation of the basics in Vue webpack Configuration
Explain the basic configuration in detail in Vue webpack
How to build a multi-person chat room in the nodejs express environment
The above is the detailed content of How to implement various sorting methods using js. For more information, please follow other related articles on the PHP Chinese website!
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
1657
14
1415
52
1309
25
1257
29
1229
24
How to set password protection for export PDF on PS
Apr 06, 2025 pm 04:45 PM
Export password-protected PDF in Photoshop: Open the image file. Click "File"> "Export"> "Export as PDF". Set the "Security" option and enter the same password twice. Click "Export" to generate a PDF file.
The difference between H5 and mini-programs and APPs
Apr 06, 2025 am 10:42 AM
H5. The main difference between mini programs and APP is: technical architecture: H5 is based on web technology, and mini programs and APP are independent applications. Experience and functions: H5 is light and easy to use, with limited functions; mini programs are lightweight and have good interactiveness; APPs are powerful and have smooth experience. Compatibility: H5 is cross-platform compatible, applets and APPs are restricted by the platform. Development cost: H5 has low development cost, medium mini programs, and highest APP. Applicable scenarios: H5 is suitable for information display, applets are suitable for lightweight applications, and APPs are suitable for complex functions.
Why do you need to call Vue.use(VueRouter) in the index.js file under the router folder?
Apr 05, 2025 pm 01:03 PM
The necessity of registering VueRouter in the index.js file under the router folder When developing Vue applications, you often encounter problems with routing configuration. Special...
Difference between centos and ubuntu
Apr 14, 2025 pm 09:09 PM
The key differences between CentOS and Ubuntu are: origin (CentOS originates from Red Hat, for enterprises; Ubuntu originates from Debian, for individuals), package management (CentOS uses yum, focusing on stability; Ubuntu uses apt, for high update frequency), support cycle (CentOS provides 10 years of support, Ubuntu provides 5 years of LTS support), community support (CentOS focuses on stability, Ubuntu provides a wide range of tutorials and documents), uses (CentOS is biased towards servers, Ubuntu is suitable for servers and desktops), other differences include installation simplicity (CentOS is thin)
How to use XPath to search from a specified DOM node in JavaScript?
Apr 04, 2025 pm 11:15 PM
Detailed explanation of XPath search method under DOM nodes In JavaScript, we often need to find specific nodes from the DOM tree based on XPath expressions. If you need to...
What is the difference between syntax for adding columns in different database systems
Apr 09, 2025 pm 02:15 PM
不同数据库系统添加列的语法为：MySQL：ALTER TABLE table_name ADD column_name data_type;PostgreSQL：ALTER TABLE table_name ADD COLUMN column_name data_type;Oracle：ALTER TABLE table_name ADD (column_name data_type);SQL Server：ALTER TABLE table_name ADD column_name data_
What are the different ways of promoting H5 and mini programs?
Apr 06, 2025 am 11:03 AM
There are differences in the promotion methods of H5 and mini programs: platform dependence: H5 depends on the browser, and mini programs rely on specific platforms (such as WeChat). User experience: The H5 experience is poor, and the mini program provides a smooth experience similar to native applications. Communication method: H5 is spread through links, and mini programs are shared or searched through the platform. H5 promotion methods: social sharing, email marketing, QR code, SEO, paid advertising. Mini program promotion methods: platform promotion, social sharing, offline promotion, ASO, cooperation with other platforms.
Where is the C language function library? How to add the C language function library?
Apr 03, 2025 pm 11:39 PM
The C language function library is a toolbox containing various functions, which are organized in different library files. Adding a library requires specifying it through the compiler's command line options, for example, the GCC compiler uses the -l option followed by the abbreviation of the library name. If the library file is not under the default search path, you need to use the -L option to specify the library file path. Library can be divided into static libraries and dynamic libraries. Static libraries are directly linked to the program at compile time, while dynamic libraries are loaded at runtime.
