JavaScript implements various sorting algorithms

Foreword：This article mainly uses Javascript to implement various sorting algorithms in data structures，For example&# xff1a;Insertion sort
, Hill sort, merge sort, etc.

Bubble sort

function bubbleSort(arr) {console.time(“Bubble Sort” )var num = 0 ;for (var i = arr.length; i > num; num++) {for (var j = i – 1; j > num; j–) { if(arr[j-1]>arr[j]){var temp = arr[j-1];arr [j-1] = arr[j];arr[j] = temp;}}}console.timeEnd(” Bubble sort”)return arr}var arr = [12, 290, 219, 278 , 4432,21, 43, 89, 78];console.log( bubbleSort(arr));

Time complexity： Worst O(n ²); Optimal O(n)

Insertion sort

The basic principle of insertion sort is as follows: Build an ordered sequence from front to back. For an unsorted sequence, scan the insertion position from back to front in the sorted sequence. ;For the p-th element ， it is necessary to scan p-1 times， On average, the insertion sort algorithm complexity is O(n²)

function insertSort(arr) {console.time(“insert sort”)var len = arr.length;if (len <= 1) {return span> arr;}// 1~n-1 sortingarr.map(function (item,index){if(index>0){for (var j & #61; index; j > 0 && arr[j – 1] > item; j–) {arr[j] = arr[j – 1];}arr [j] = item;}});console.timeEnd(“insertion sort”)return arr
}
var arr = [12, 290, 219, 278, 4432, 21, 43, 89, 78];
console.log(insertSort(arr));

Hill sort

Shell sorting is also called descending increment sorting，The effect is better than insertion sort，For different increments，The sorting performance is also different

Let’s take a look at the step size selection

The algorithm implementation process is as follows：Here we choose the step size to be 4：（Each column is equivalent to an insertion sort）

12 190 219 278
4432 21 43 89
78
// After the first sorting, we get：
12 21 43 89
78 190 219 278
4432// Connect to get The result is [12，21，43，89，78，190，219，278，4432]， and then sort with 2 as the step size. For:
12 21
43 89
78 190
219 278
4432// Then it is a simple insertion sort

The average time complexity is： =”” />

Quick sort implementation 2： （Using the middle as the base value）

1 function qSort(arr) {
2 if (arr.length <= 1 ) {
3 return arr;
4 }
5 var num = Math.floor(arr.length / 2);
6
7 var numValue = arr.splice(num, 1)[0];
8 var left = [],
9 right = [];
10 for (var i = 0; i ) {
11 if (arr[i] < numValue) {
12 left.push(arr[i]);
13 } else {
14 right.push(arr[i]);
15 }
16 }
17 return qSort(left)
18 .concat([numValue], qSort(right))
19 }
20
21 console.log(qSort([32, 45, 37 , 16, 2, 87]))

The average time complexity of quick sort is O(NLogN)

Merge sort

Merge sort uses the idea of ​​​​divide and conquer to divide the array – separate it in half – sort the left and right sides respectively – and then merge the sorted results. According to this idea – recursion is the most convenient.

1 int a[N], c[N];
2 void mergeSort(l, r) {
3 int mid, i, j , tmp;
4 if (r – 1 > l) {
5 mid = (l + r) >> 1;
6 // respectively Sort by the left and right two days
7 mergeSort(l, mid);
8 mergeSort( mid, r);
9 // Merge sorted arrays
10 tmp = l;
11 for (i = l, j = mid; i <mid && j < r;) {
12 if (a[i] > a[j]) c[tmp& #43;+] = a[j++];
13 else c[tmp++] = a[i++];
14 }
15 // Connect the rest
16 if (j < r) {
17 for (; j <r; j++ ) c[tmp++] = a[j];
18 } else {
19 for (; i <mid; i++) c[tmp++ ] = a[i];
20 }
21 // Overwrite the c array into a
22 for (i = l; i <r ; i++) {
23 a[i] = c[i];
24 }
25 }
26 }

Conclusion

Update the implementation of several sorting algorithms

Redirect: https://www.cnblogs.com/kasmine/p/6416472.html