New technologies are constantly changing, and mastering some foundations is a solid foundation for learning and constantly updating technologies in the future. I have nothing to do recently. In order to review the data structure I learned before, I implemented the sorting algorithm in the data structure in JS, and embedded DEMO at the end of this article.
Simple sorting
Bubble sort
Bubble sorting is the simplest sorting algorithm, with a square of the time complexity n, and the code is as follows:
function bubbleSort(array) { for (var i = 0; i < array.length; i++) { for (var j = array.length; j > 0; j--) { if (array[j] < array[j - 1]) { var temp = array[j - 1]; array[j - 1] = array[j]; array[j] = temp; } } /* Output result*/ document.write("This is the + (i + 1) + "second loop・, the result is:"); for (var k = 0; k < array.length; k++) { document.write(array[k] + ","); } document.write("<br />"); /* The output result ends*/ } }Direct insert sort
Direct insertion sorting is also a simple sorting algorithm, and the time complexity is also squared by n, but the performance is slightly better than bubble sorting. The code is as follows:
function insertSort(array) { var temp; for (var i = 1; i < array.length; i++) { var temp = array[i]; for (var j = i; j > 0 && temp < array[j - 1]; j--) { array[j] = array[j - 1]; } array[j] = temp /* Output result*/ document.write("Th? + i + "The result of the ordering of passes is:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } document.write("<br />") /* The output result ends*/ } }Select Sort
Selection sorting is also a simple sorting algorithm, with a time complexity of n squared, and the performance is also slightly better than bubble sorting. The code is as follows:
function selectSort(array) { var min, temp; ; for (var i = 0; i < array.length; i++) { min = i; for (var j = i + 1; j < array.length; j++) { if (array[min] > array[j]) min = j; } if (min != i) { temp = array[i]; array[i] = array[min]; array[min] = temp; } /* Output result*/ document.write("+ i + "The result of the ordering of passes is:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } document.write("<br />") /* The output result ends*/ } }Complex sorting
Hill sort
Hill sorting is an upgrade of insertion sorting. In 1959, Hill broke through the time complexity of n square by changing the pairwise comparison in simple sorting to setting step-leap jump comparison. Hill sorting goes from the best nlogn to the worst n square according to different time complexity of step sizes. The code is as follows:
function shallSort(array) { var increment = array.length; var i var temp; //Store var count = 0; do { increment = Math.floor(increment / 3) + 1; for (i = increment; i < array.length; i++) { if (array[i] < array[i - increment]) { temp = array[i]; for (var j = i - increment; j > 0 && temp < array[j]; j -= increment) { array[j + increment] = array[j]; } array[j + increment] = temp; /* Output result*/ count++; document.write("<br />+ count + "The result of the ordering of passes is:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } /* The output result ends*/ } } } while (increment > 1) }Heap sorting
Heap sorting is an upgrade to select sorting. By continuously building a large top heap or a small top heap, selecting the largest or smallest value and putting it into the front end of the queue for sorting. The time complexity of heap sorting in any case is nlogn, the code is as follows:
function heapSort(array) { var temp; var i; for (i = Math.floor(array.length / 2); i >= 0; i--) { heapAdjust(array, i, array.length - 1); //Build array array into a large top heap} for (i = array.length - 1; i >= 0; i--) { /*Swap the root node out*/ temp = array[i]; array[i] = array[0]; array[0] = temp; /*The remaining array continues to be built into a large top heap*/ heapAdjust(array, 0, i - 1); /* Output result*/ document.write("<br />+ (array.length - i).toString() + "The result of the ordering of passes is:") for (var n = 0; n < array.length; n++) { document.write(array[n] + ","); } /* The output result end*/ } } //The subtree to be adjusted//start is the start subscript for the array//max is the end subscript of the array function heapAdjust(array, start, max) { var temp, j; temp = array[start];//temp is the value of the root node for (j = 2 * start; j < max; j *= 2) { if (j < max && array[j] < array[j + 1]) { //Get the subscript of older children++j; } if (temp >= array[j]) break; array[start] = array[j]; start = j; } array[start] = temp; }Merge sort
Merge sorting is the only stable sorting in complex sorting. It sorts by splitting and then merges the array to be sorted. The square of the complexity of the merge sorting time is n. The code is as follows:
//source source array//dest target array//s start subscript//t target subscript function mSort(source, dest, s, t) { var m; //Pick the intermediate value var dest2 = new Array(); if (s == t) { dest[s] = source[s]; } else { m = Math.floor((s + t) / 2); mSort(source, dest2, m+1 , t); merge(dest2, dest, s, m, t); /* Output result*/ document.write("<br />+ ++count + "The result of pass sorting is:") for (var n = 0; n < dest.length; n++) { document.write(array[n] + ","); } /* The output result ends*/ } } //Fusing two arrays in order from small to large//source original array//dest sorted array//s first subscript//m second array subscript//total length function merge(source, dest, s, m, n) { for (var j = m+1, k = s; j <= n && s <= m; k++) { if (source[s] < source[j]) { dest[k] = source[s++]; } else { dest[k] = source[j++]; } } //Add the remaining ordered arrays to the end of the dest if (s <= m) { for (var l = 0; l <= m - s; l++) { dest[k + l] = source[s+l]; } } if (j <= n) { for (var l = 0; l <= n - j; l++) { dest[k + l] = source[j+l]; } } } }Quick sort
Quick sort is the fastest known sort, with a time complexity of nlogn, and the code is as follows:
var count = 0; function quickSort(array, low, high) { var temp; if (low < high) { var keypoint = QuickSortHelp(array, low, high); count++; document.write("<br />Terminal? + count + "The result of the ordering of the ordering is?:") for (var l = 0; l < array.length; l++) { document.write(array[l] + ","); } quickSort(array, low, keypoint - 1); quickSort(array, keypoint + 1, high); } } function QuickSortHelp(array, low, high) { while (low < high) { while (low < high && array[low] <= array[high]) { high--; } temp = array[low]; array[low] = array[high]; array[high] = temp; while (low < high && array[low] <= array[high]) { low++ } temp = array[low]; array[low] = array[high]; array[high] = temp; } return low; }The above summary of various sorting methods (JS implementation) in the data structure is all the content I share with you. I hope you can give you a reference and I hope you can support Wulin.com more.