Home > Article > Web Front-end > Simple implementation of several sorting algorithms in JavaScript_Basic knowledge
Implementation of sorting algorithm
My JS skills are poor, so I use a method similar to JAVA and C to write the JavaScript sorting algorithm.
And I won’t talk about the algorithm principle here, just the code implementation, there may be bugs, everyone is welcome to comment on the blog for guidance.
Insertion sort
The algorithm description of Insertion-Sort is a simple and intuitive sorting algorithm. It works by constructing an ordered sequence. For unsorted data, it scans from back to front in the sorted sequence, finds the corresponding position and inserts it. In the implementation of insertion sort, in-place sorting is usually used (that is, sorting that only uses O(1) extra space). Therefore, during the scanning process from back to front, it is necessary to repeatedly and gradually shift the sorted elements backward. , providing insertion space for the latest element.
The implementation code is as follows:
function insertSort(arr) { if (!arr) return; var len = arr.length; if (len == 0 || len == 1) return; for (var i = 1, len = arr.length; i < len; i ++) { var stand = arr[i]; for (var j = i - 1; j >= 0; j --) { if (arr[j] > stand) { arr[j + 1] = arr[j]; } else { arr[j + 1] = stand; break; } } } return arr; }
Time complexity is: O(n^2)
Of course, there is room for optimization of this algorithm, such as changing the positional algorithm of search and replacement to binary search.
Bubble sort
Classic sorting algorithm, I feel heartbroken when it comes to bubble sort. When I was an undergraduate, I wrote a required thesis on the improvement of the bubble sort algorithm. As a result, I couldn't fully implement the bubble sort algorithm after I finished writing the thesis. It was so embarrassing.
if (!arr) return; var len = arr.length; if (len == 0 || len == 1) return; for (var i = 0; i < len; i ++) { for (var j = 0; j < len - i - 1; j ++) { if (arr[j] > arr[j + 1]) { var tmp = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = tmp; } } } return arr; }
The time complexity is: O(n^2)
Quick Sort
A very classic sorting algorithm. The sorting process is mainly divided into three steps:
The implementation code is as follows:
function quickSort(arr, bt, ed) { if (bt < ed) { var pivot = findPartition(arr, bt, ed); quickSort(arr, bt, pivot - 1); quickSort(arr, pivot + 1, ed); } } function findPartition(arr, bt, ed) { var stand = arr[bt]; while (bt < ed) { while (bt < ed && arr[ed] >= stand) { ed --; } if (bt < ed) { arr[bt ++] = arr[ed]; } while (bt < ed && arr[bt] <= stand) { bt ++; } if (bt < ed) { arr[ed --] = arr[bt]; } } arr[bt] = stand; return bt; }
The time complexity is: O(nlogn).
Merge sort
It is also a very classic sorting algorithm. I took the opportunity of learning js to review the classic sorting algorithm. For ideas on merge sort, you can refer to my blog: Merge Sort. I only write js implementation here.
function mergeSort(arr, bt, ed) { if (bt < ed) { var mid = bt + parseInt((ed - bt) / 2); mergeSort(arr, bt, mid); mergeSort(arr, mid + 1, ed); mergeArray(arr, bt, mid, ed); } } function mergeArray(arr, bt, mid, ed) { var mArr = []; var i = bt, j = mid + 1; while (i <= mid && j <= ed) { if (arr[i] <= arr[j]) { mArr.push(arr[i++]); } else { mArr.push(arr[j ++]); } } if (i <= mid) { mArr = mArr.concat(arr.slice(i, mid + 1)); } if (j <= ed) { mArr = mArr.concat(arr.slice(j, ed + 1)); } for (var h = 0; h < mArr.length; h ++) { arr[bt + h] = mArr[h]; } }
There was another little episode when writing the merge sort: js could not automatically round up, so I later used the parseInt method, which was very cute.