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
AI Hentai Generator
Generate AI Hentai for free.
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
1386
52
The difference between char and wchar_t in C language
Apr 03, 2025 pm 03:09 PM
In C language, the main difference between char and wchar_t is character encoding: char uses ASCII or extends ASCII, wchar_t uses Unicode; char takes up 1-2 bytes, wchar_t takes up 2-4 bytes; char is suitable for English text, wchar_t is suitable for multilingual text; char is widely supported, wchar_t depends on whether the compiler and operating system support Unicode; char is limited in character range, wchar_t has a larger character range, and special functions are used for arithmetic operations.
The difference between multithreading and asynchronous c#
Apr 03, 2025 pm 02:57 PM
The difference between multithreading and asynchronous is that multithreading executes multiple threads at the same time, while asynchronously performs operations without blocking the current thread. Multithreading is used for compute-intensive tasks, while asynchronously is used for user interaction. The advantage of multi-threading is to improve computing performance, while the advantage of asynchronous is to not block UI threads. Choosing multithreading or asynchronous depends on the nature of the task: Computation-intensive tasks use multithreading, tasks that interact with external resources and need to keep UI responsiveness use asynchronous.
What is the function of C language sum?
Apr 03, 2025 pm 02:21 PM
There is no built-in sum function in C language, so it needs to be written by yourself. Sum can be achieved by traversing the array and accumulating elements: Loop version: Sum is calculated using for loop and array length. Pointer version: Use pointers to point to array elements, and efficient summing is achieved through self-increment pointers. Dynamically allocate array version: Dynamically allocate arrays and manage memory yourself, ensuring that allocated memory is freed to prevent memory leaks.
What is the difference between char and unsigned char
Apr 03, 2025 pm 03:36 PM
char and unsigned char are two data types that store character data. The main difference is the way to deal with negative and positive numbers: value range: char signed (-128 to 127), and unsigned char unsigned (0 to 255). Negative number processing: char can store negative numbers, unsigned char cannot. Bit mode: char The highest bit represents the symbol, unsigned char Unsigned bit. Arithmetic operations: char and unsigned char are signed and unsigned types, and their arithmetic operations are different. Compatibility: char and unsigned char
What are the basic requirements for c language functions
Apr 03, 2025 pm 10:06 PM
C language functions are the basis for code modularization and program building. They consist of declarations (function headers) and definitions (function bodies). C language uses values to pass parameters by default, but external variables can also be modified using address pass. Functions can have or have no return value, and the return value type must be consistent with the declaration. Function naming should be clear and easy to understand, using camel or underscore nomenclature. Follow the single responsibility principle and keep the function simplicity to improve maintainability and readability.
Concept of c language function
Apr 03, 2025 pm 10:09 PM
C language functions are reusable code blocks. They receive input, perform operations, and return results, which modularly improves reusability and reduces complexity. The internal mechanism of the function includes parameter passing, function execution, and return values. The entire process involves optimization such as function inline. A good function is written following the principle of single responsibility, small number of parameters, naming specifications, and error handling. Pointers combined with functions can achieve more powerful functions, such as modifying external variable values. Function pointers pass functions as parameters or store addresses, and are used to implement dynamic calls to functions. Understanding function features and techniques is the key to writing efficient, maintainable, and easy to understand C programs.
c What are the differences between the three implementation methods of multithreading
Apr 03, 2025 pm 03:03 PM
Multithreading is an important technology in computer programming and is used to improve program execution efficiency. In the C language, there are many ways to implement multithreading, including thread libraries, POSIX threads, and Windows API.
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.
