Shulou(Shulou.com)06/01 Report--

What are several commonly used sorting algorithms in JavaScript? For this problem, this article introduces the corresponding analysis and solutions in detail, hoping to help more small partners who want to solve this problem find simpler and easier ways.

Insertion Sort/*1) Introduction to the algorithm The algorithm description of Insertion Sort is a simple and intuitive sorting algorithm. It works by constructing ordered sequences, scanning backward through the ordered sequence for unsorted data, finding the corresponding position and inserting. Insertion sorting is usually implemented as in-place sorting (i.e., sorting that requires only O(1) extra space), so that in the back-to-front scanning process, it is necessary to repeatedly move the sorted elements back and forth to provide insertion space for the newest elements. 2) Algorithm description and implementation In general, insert sorting is implemented on arrays using in-place. The specific algorithm is described as follows: starting from the first element, the element can be considered to have been sorted; taking out the next element and scanning from back to front in the sorted element sequence; if the element (sorted) is greater than the new element, moving the element to the next position; repeating step 3 until the sorted element is found to be less than or equal to the new element; inserting the new element into the position; repeating steps 2 - 5. 3) Algorithm analysis Best case: Input arrays are sorted in ascending order. T(n) = O(n) Worst-case: Input array sorted in descending order. T(n) = O(n2) Average case: T(n) = O(n2)*/function insertionSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { for (var i = 1; i

< array.length; i++) { var key = array[i]; var j = i - 1; while (j >

= 0 && array[j] > key) { array[j + 1] = array[j]; j--; } array[j + 1] = key; } return array; } else { return 'array is not an Array! '; var a = [1,4,2,5,3];var result = insertionSort(a);debugger; Binary-insert-sort/*1) Introduction Binary-insert-sort is a sort algorithm that makes minor modifications to the direct insertion sort algorithm. The biggest difference between it and direct insertion sorting algorithm is that it uses a binary search method to find the insertion position, and there is a certain increase in speed. 2) Algorithm description and implementation In general, insert sorting is implemented on arrays using in-place. The specific algorithm is described as follows: starting from the first element, the element can be considered to have been sorted; take out the next element, and find the position of the first number larger than it in the sorted element sequence; insert the new element into the position; repeat the above two steps. 3) Algorithm analysis Best case: T(n) = O(nlogn) Worst case: T(n) = O(n2) Average case: T(n) = O(n2)*/function binaryInsertionSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { for (var i = 1; i

< array.length; i++) { var key = array[i], left = 0, right = i - 1; while (left = left; j--) { array[j + 1] = array[j]; } array[left] = key; } return array; } else { return 'array is not an Array!'; }}var a = [1,4,2,5,3];var result = binaryInsertionSort(a);debugger;选择排序/*1）算法简介选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。2）算法描述和实现n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：初始状态：无序区为R[1..n]，有序区为空；第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；n-1趟结束，数组有序化了。3）算法分析最佳情况：T(n) = O(n2)最差情况：T(n) = O(n2)平均情况：T(n) = O(n2)*/function selectionSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { var len = array.length, temp; for (var i = 0; i < len - 1; i++) { var min = array[i]; for (var j = i + 1; j < len; j++) { if (array[j] < min) { temp = min; min = array[j]; array[j] = temp; } } array[i] = min; } return array; } else { return 'array is not an Array!'; }}var a = [1,4,2,5,3];var result = selectionSort(a);debugger;选择排序/*1）算法简介选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。2）算法描述和实现n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：初始状态：无序区为R[1..n]，有序区为空；第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；n-1趟结束，数组有序化了。3）算法分析最佳情况：T(n) = O(n2)最差情况：T(n) = O(n2)平均情况：T(n) = O(n2)*/function selectionSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { var len = array.length, temp; for (var i = 0; i < len - 1; i++) { var min = array[i]; for (var j = i + 1; j < len; j++) { if (array[j] < min) { temp = min; min = array[j]; array[j] = temp; } } array[i] = min; } return array; } else { return 'array is not an Array!'; }}var a = [1,4,2,5,3];var result = selectionSort(a);debugger;冒泡排序/*1）算法简介冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。2）具体算法描述如下：比较相邻的元素。如果第一个比第二个大，就交换它们两个；对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；针对所有的元素重复以上的步骤，除了最后一个；重复步骤1~3，直到排序完成。3）算法分析最佳情况：T(n) = O(n)最差情况：T(n) = O(n2)平均情况：T(n) = O(n2)*/function bubbleSort(array) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') { var len = array.length, temp; for (var i = 0; i < len - 1; i++) { for (var j = len - 1; j >

= i; j--) { if (array[j]

< array[j - 1]) { temp = array[j]; array[j] = array[j - 1]; array[j - 1] = temp; } } } return array; } else { return 'array is not an Array!'; }}var a = [1,4,2,5,3];var result = bubbleSort(a);debugger;快速排序/*1）算法简介快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。2）算法描述和实现快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：从数列中挑出一个元素，称为 "基准"（pivot）；重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。3）算法分析最佳情况：T(n) = O(nlogn)最差情况：T(n) = O(n2)平均情况：T(n) = O(nlogn)*/function quickSort(array, left, right) { if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number') { if (left < right) { var x = array[right], i = left - 1, temp; for (var j = left; j arr[largest]) { console.log(" left child >

largest, plan to swap! "); largest = l; } if (r

< len && arr[r] >

arr[largest]) { console.log(" right child > largest, plan to swap! "); largest = r; } if (largest != x) { temp = arr[x]; arr[x] = arr[largest]; arr[largest] = temp; heapify(arr, largest, len); } } else { return 'arr is not an Array or x is not a number! '; }}var a = [1,0,3];// var a = [1,4,2,3]var result = heapSort(a);debugger; merge sort/*1) Introduction Merge sort is an effective sort algorithm based on merge operations. This algorithm is a very typical application of Divide and Conquer. Merge sort is a stable sort method. The ordered sub-sequences are merged to obtain a completely ordered sequence, that is, each sub-sequence is ordered first, and then the sub-sequence segments are ordered. If two ordered tables are merged into one ordered table, it is called a 2-way merge. 2) Algorithm description and implementation The specific algorithm description is as follows: Divide the input sequence with length n into two sub-sequences with length n/2; merge the two sub-sequences; merge the two sorted sub-sequences into a final sorting sequence. 3) Algorithm analysis Best case: T(n) = O(n) Worst case: T(n) = O(nlogn) Average case: T(n) = O(nlogn)*/function mergeSort(array, p, r) { if (p

< r) { var q = Math.floor((p + r) / 2); mergeSort(array, p, q); mergeSort(array, q + 1, r); merge(array, p, q, r); }}function merge(array, p, q, r) { var n1 = q - p + 1, n2 = r - q, left = [], right = [], m = n = 0; for (var i = 0; i < n1; i++) { left[i] = array[p + i]; } for (var j = 0; j < n2; j++) { right[j] = array[q + 1 + j]; } left[n1] = right[n2] = Number.MAX_VALUE; for (var k = p; k array[j]) { buckets[index][k + 1] = buckets[index][k]; k--; } buckets[index][k + 1] = array[j]; } else { //空桶，初始化 buckets[index] = []; buckets[index].push(array[j]); } } while (n < num) { result = result.concat(buckets[n]); n++; } return result;}var a = [0,4,1,3,2,6];var result = bucketSort(a, a.length-1);debugger;计数排序/*1）算法简介计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。2）算法描述和实现具体算法描述如下：找出待排序的数组中最大和最小的元素；统计数组中每个值为i的元素出现的次数，存入数组C的第i项；对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。3）算法分析当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。*/function countingSort(array) { var len = array.length, B = [], C = [], min = max = array[0]; for (var i = 0; i < len; i++) { min = min = array[i] ? max : array[i]; C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1; } for (var j = min; j < max; j++) { C[j + 1] = (C[j + 1] || 0) + (C[j] || 0); } for (var k = len - 1; k >

=0; k--) { B[C[array[k]] - 1] = array[k]; C[array[k]]--; } return B;}var a = [0,4,1,3,2,6];var result = countingSort(a);debugger; About several common sorting algorithms in JavaScript are the answers to which questions are shared here, I hope the above content can be of some help to everyone, if you still have a lot of doubts, you can pay attention to the industry information channel to learn more related knowledge.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.