preface
In this section, we will mainly learn the common sorting and search algorithms : as : Bubble sort , Select sort , Insert sort , Merge sort , Quick sort and heap sort, etc : Sequential search and binary search algorithm .
//1, Before you start the sorting algorithm , Create an array first ( list ) To represent the data structure to be sorted and searched .
function ArrayList() { var array = []; //1.1 Define an array to hold data this.insert = function
(item) { //1.2 Define an insert method to add elements to the data structure array.push(item); }; this.toString = function
() { // use js Native join method , To splice all elements in an array return array.join('-'); }; // Bubble sorting without improvement : /***
* Bubble sort compares any two adjacent items , If the first is bigger than the second , Exchange them . * The time complexity is O(n^2) */ this.bubbleSort =
function () { var length = array.length; for (var i = 0; i < length; i++) {
// Number of control cycles for (var j = 0; j < length - 1; j++) { // Constantly compare and exchange data from adjacent locations if (array[j] >
array[j + 1]) { swap(array, j, j + 1); } } } }; // Improved bubble sorting /** *
If you subtract the number of runs in the outer loop from the inner loop , All unnecessary comparisons in the inner loop can be avoided * */ this.modifiedBubbleSort = function
() { var length = array.length; for (var i = 0; i < length; i++) { for (var j =
0; j < length - 1 - i; j++) { if (array[j] > array[i]) { swap(j, j + 1); } } }
}; /** * Select sort : Selection sort algorithm is a sort algorithm of original address comparison . The general idea of sorting is to find the minimum value in the data structure and put it in the first place , *
Then find the second smallest value and place it in the second place , and so on . * Its time complexity is also 0 O(n^2) * * */ // Select sorting algorithm source code :
this.selectionSort = function () { var length = array.length; var indexMin; for
(var i = 0; i < length - 1; i++) {// Outer loop iteration array , And control the iteration times ( Number of array n Values ==== Next minimum ) indexMin
= i; // Suppose the minimum value of this iteration for (var j = i; j < length; j++) {
// From the current i Value to end of array , Compare position j Smaller than the current minimum value , If it is if (array[indexMin] > array[j]) { indexMin
= j;// Then change the minimum value to the new minimum value } }// When the internal circulation ends , The number of n Small value if (i !== indexMin)
{// If the minimum value is different from the original minimum value , Exchange the value [array[i], array[indexMin]] = [array[indexMin],
array[i]]; } } }; /** * Insert sort : Insert sort sorts one integer item at a time , The final sorted array is constructed . * * */
this.insertionSort = function () { var length = array.length; var j, temp; for
(var i = 1; i < length; i++) {// Iterate the array to give the i Item found the correct location j = i; temp =
array[i];// use i To initialize an auxiliary variable and store its value in the -- Temporary variable while (j > 0 && array[j - 1] > temp)
{// Find the right place to insert array[j] = array[j - 1];// If the previous value in the array is larger than the value to be compared , Moves the previous value to the current position ,J-- j--; }
array[j] = temp; // Until the preceding value part is not greater than temp Time , hold temp Put in the current location . Then iterate on the next item to continue sorting } }; /** *
Merge sort : Merge sort is the first algorithm that can be used in practice * The performance of the previous algorithms is not good , Merging is good , Its complexity is * Time complexity :O(nlog^n) *
Merge sort is a divide and conquer algorithm . The idea is to split the original array into smaller arrays * Until each small array has only one position , The small arrays are then merged into larger arrays , Until the end, there is only one sorted large array *
*/ this.mergeSort = function(){ array = mergeSortRec(array); }; /** *
Quick sort : The most commonly used algorithm , Its complexity is O(nlog^n) * (1) first , Select the middle item from the array as the principal element . *
(2) Create two pointers , The one on the left points to the first item in the array , The one on the right points to the last item in the array . *
Move the left pointer until we find an element larger than the principal element , next , Move the right pointer until an element smaller than the principal element is found . * And exchange them , Repeat the process , Until the left pointer exceeds the right pointer . *
This process places values smaller than the principal element before the principal element , And values larger than the principal element are placed after the principal element
*(3) next , Algorithm for the partition of the small array ( A subarray of values smaller than the principal , And a subarray of values larger than the principal ) * Repeat the previous two steps , Until the array is fully sorted . **/
this.quickSort = function(){ quick(array, 0, array.length - 1); }; // search algorithm /** *
Sequential search : Sequential or linear search is the most basic search algorithm . Its mechanism is : * Compare the elements in each data structure with the elements we are looking for . Sequential search is the most inefficient * A search algorithm . * */
this.sequentialSearch = function(item){ for(var i=0;i<array.length;i++){
if(item === array[i]){ return i;//true perhaps array[i] } } return -1; } /** *
Binary search : The algorithm requires that the data structure to be searched has been sorted * step : * (1) Select the middle value of the array * (2) If the selected value is the value to be searched , Then the algorithm is finished *
(3) If the value to be searched is smaller than the selected value , Return to step 1 And look in the subarray to the left of the selected value * (4) If the value to be searched is larger than the selected value , Return to step 1 And look in the subarray to the right of the selected value */
this.binarySeach = function(item){ this.quickSort(); // Sort array before lookup var low =
0; var high = array.length -1; var mid,element; while(low<= high){ mid =
Math.floor((low + high) /2); element = array[mid]; if(element <item) { low =
mid +1; } else if(element >item){ high = mid -1; }else{ return mid; // The index is returned }
} return -1; }; } // Quick sort partition process : var partition = function(array,left,right){ var
pivot = array[Math.floor((right + left)/2)];// Select the middle item as the primary element var i= left;
// Initialize to the first element of the array var j = right; // Initialize to the last element of the array while(i<= j){ while(array[i] <
pivot){ // Move the pointer until an element is found that is larger than the principal element i++; } while(array[j] > pivot){
// about right The pointer does the same thing , Move to find smaller than the principal element j--; } if(i<= j){
// When the left pointer points to an element larger than the principal element and the right pointer points to a smaller element than the principal element , At this time, the left pointer index is not larger than the right pointer index , Exchange them swap(array,i,j); i++; j--;
} } return i; }; // Declare methods to call recursive functions , Pass array to be sorted , And index 0 And its last position as a parameter . var quick =
function(array,left,right){ var index; // Define the variable , Helps us separate subarrays into smaller arrays and larger arrays
if(array.length >1){ index = partition(array,left,right); if(left < index -1){
quick(array,left,index-1); } if(index < right){ quick(array,index,right); } }
}; // The following is the merge order // Auxiliary functions actually executed var mergeSortRec = function(array){ var length =
array.length; if(length ===1){ // End condition return array; } var mid =
Math.floor(length/2);// Gets the middle bit of the array var left = array.slice(0,mid); // Array divides it into two small arrays
var right = array.slice(mid,length); return
merge(mergeSortRec(left),mergeSortRec(right)); }; // definition merge function , Responsible for merging and sorting small arrays to produce large arrays
// Until you go back to the original array and sort it out . var merge = function(left,right){ var result = []; var iL =
0; var iR = 0; while(iL < left.length && ir < right.length) { // {8} if
(left[iL] < right[iR]) { result.push(left[iL++]); // {9} } else {
result.push(right[iR++]); } } while(iL <left.length){ result.push(left[iL++]);
} while(iR <right.length){ result.push(right[iR++]); } return result; }; // Exchange method
var swap= function(array,index1,index2){ /* var aux = array[index1];
array[index1]= array[index2]; array[index2]=aux;*/ // It can be used es6 In order to exchange
[array[index1],array[index2]]=[array[index2],array[index1]]; };
test :
// Test bubble sort algorithm // Define a function to automatically create an unsorted array , The length of the array is specified by the parameter of the function function
createNonSortedArray(size){ var array = new ArrayList(); for(var i =
size;i>0;i--){ array.insert(i); } return array; } // Test bubbling results var array =
createNonSortedArray(5); console.log(" Before bubble sort :",array.toString());
array.bubbleSort(); console.log(" After bubble sort :",array.toString()); // Test selection sorting algorithm var
selectionArry = createNonSortedArray(5);
console.log(" Select before sorting :",selectionArry.toString()); selectionArry.selectionSort();
console.log(" After selecting sort :",selectionArry.toString()); // Test insertion sort algorithm var insertArry =
createNonSortedArray(5); console.log(" Insert before sort :",insertArry.toString());
insertArry.selectionSort(); console.log(" Insert after sort :",insertArry.toString());
console.log(" Data after binary search ",insertArry.binarySeach(3));
results of enforcement

Technology
©2019-2020 Toolsou All rights reserved,
Python Garbage collection and memory leak hive Summary of processing methods for a large number of small files The difference between memory overflow and memory leak , Causes and Solutions Create data mysql Library process You don't know ——HarmonyOS stay Vue Use in Web WorkerSparkSQL Achieve partition overlay write msf Generate Trojan horse attack android mobile phone Linux Page replacement algorithm C Language implementation Django Personal blog building tutorial --- Time classified archiving