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,
about String How to create objects JavaScript Hundred refining into Immortals 1.15 Legendary Is MCU embedded , It's a cliche Resume the 13th session python Blue Bridge Cup html+css+js Make a simple website home page java Connect to the database to realize basic addition, deletion, modification and query VHDL——JK trigger Java of JDBC programming 3 4j It's not legal python expression _3+4j It's not legal Python expression .【linux】shell: ordinary shell Script exercise