Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "how to use JavaScript to achieve seven sorting algorithms". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Bubbling sort

Bubble sorting is an entry-level algorithm, but there are also some interesting ways to play. In general, bubble sorting can be written in three ways:

Compare and swap backwards, bubbling the maximum / minimum to the last place

Optimized writing: use a variable to record whether the current round of comparisons have been exchanged. If no exchange occurs, it means that the order is in order, and the sorting will not continue.

Basic algorithm

Space complexity is O (1), time complexity is O (N2).

Const sort = (arr) = > {for (let I = 0, len = arr.length; I)

< len-1; i++){ for (let j = 0; j < len-1-i; j++) { if (arr[j] >

Arr [juni1]) {[arr [j], arr [j + 1]] = [arr [juni1], arr [j]];} return arr}

With each round of the outermost for loop, the maximum value of the remaining digits is moved to the last digit of the current round, and some adjacent digits are swapped into order. The total number of comparisons is (nmur1) + (nmur2) + (nMur3) + … + 1 (n − 1) + (n − 2) + (n − 3) + … + 1.

The second method is improved from the basic algorithm: const sort = (arr) = > {for (let I = 0, len = arr.length; I)

< len - 1; i++) { let isSwap = false for (let j = 0; j < len - 1 - i; j++) { if (arr[j] >

Arr [j + 1]) {[arr [j], arr [j + 1]] = [arr [j + 1], arr [j]]; isSwap = true}} if (! isSwap) {break;}} return arr;}

Space complexity is O (1), time complexity is O (N2)-preferably O (n)

As the outermost for loop passes through each round, the maximum value of the remaining number is still moved to the last bit of the current round. The advantage of this method over the first method is that if there is no exchange in a round of comparisons, the sorting is stopped immediately, because the remaining numbers must be in order.

Select sort

The idea of choosing sorting is: double loop through the array, after each round of comparison, find the subscript of the smallest element and swap it to the first place.

Basic algorithm const sort = (arr) = > {for (let I = 0, len = arr.length; I)

< len - 1; i++) { let minIndex = i for (let j = i+1; j < len; j++) { if (arr[i] >

Arr [j]) {minIndex = j}} [arr [I], arr [minIndex]] = [arr [minIndex], arr [I]];} return arr;}; binary selection sorting-optimization

The selection sorting algorithm can also be optimized, since the minimum value has been found in each round, why not find the maximum value by the way? This is the idea of binary selection sorting.

Using binary selection sorting, the minimum and maximum values are recorded during each round of selection, which doubles the range of arrays that need to be traversed.

Const sort = (arr) = > {for (let I = 0, len = arr.length; I)

< len / 2; i++) { let minIndex = i; let maxIndex = i; for (let j = i + 1; j < len-i; j++) { if (arr[minIndex] >

Arr [j]) {minIndex = j;} if (arr [maxIndex]

< arr[j]) { maxIndex = j; } } if (minIndex === maxIndex) break; [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]; if (maxIndex === i) { maxIndex = minIndex; } const lastIndex = len - i - 1; [arr[maxIndex], arr[lastIndex]] = [arr[lastIndex], arr[maxIndex]]; } return arr; };插入排序 插入排序的思想非常简单，生活中有一个很常见的场景：在打扑克牌时，我们一边抓牌一边给扑克牌排序，每次摸一张牌，就将它插入手上已有的牌中合适的位置，逐渐完成整个排序。 插入排序有两种写法： 交换法：在新数字插入过程中，不断与前面的数字交换，直到找到自己合适的位置。 移动法：在新数字插入过程中，与前面的数字不断比较，前面的数字不断向后挪出位置，当新数字找到自己的位置后，插入一次即可。 交换法插入排序const sort = (arr) =>

{for (let I = 1, len = arr.length; I)

< len; i++) { let j = i; while (j >

= 1 & & arr [j]

< arr[j - 1]) { [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]; j-- } } return arr;}; 当数字少于两个时，不存在排序问题，当然也不需要插入，所以我们直接从第二个数字开始往前插入。 移动法 我们发现，在交换法插入排序中，每次都要交换数字。但实际上，新插入的这个数字并不一定适合与它交换的数字所在的位置。也就是说，它刚换到新的位置上不久，下一次比较后，如果又需要交换，它马上又会被换到前一个数字的位置。 由此，我们可以想到一种优化方案：让新插入的数字先进行比较，前面比它大的数字不断向后移动，直到找到适合这个新数字的位置后再插入。 这种方案我们需要把新插入的数字暂存起来，代码如下： const sort = (arr) =>

{for (let I = 1, len = arr.length; I)

< len; i++) { let j = i-1; let cur = arr[i]; while (j >

= 0 & & cur

< arr[j]) { arr[j+1] = arr[j] j--; } arr[j+1] = cur } return arr;};希尔排序 1959 年 77 月，美国辛辛那提大学的数学系博士 Donald Shell 在 《ACM 通讯》上发表了希尔排序算法，成为首批将时间复杂度降到O(n2)以下的算法之一。虽然原始的希尔排序最坏时间复杂度仍然是O(n2)，但经过优化的希尔排序可以达到O(n1.3)甚至 O(n7/6)。 希尔排序本质上是对插入排序的一种优化，它利用了插入排序的简单，又克服了插入排序每次只交换相邻两个元素的缺点。它的基本思想是： 将待排序数组按照一定的间隔分为多个子数组，每组分别进行插入排序。这里按照间隔分组指的不是取连续的一段数组，而是每跳跃一定间隔取一个值组成一组 逐渐缩小间隔进行下一轮排序 最后一轮时，取间隔为 11，也就相当于直接使用插入排序。但这时经过前面的「宏观调控」，数组已经基本有序了，所以此时的插入排序只需进行少量交换便可完成 举个例子，对数组[8, 3, 34, 6, 4, 1, 44, 45, 43, 2, 23]进行希尔排序的过程如下： 第一遍（5 间隔排序）：按照间隔 5 分割子数组，共分成五组，分别是[8, 1, 23],[3, 44],[34, 45],[6, 43],[4, 2]。对它们进行插入排序，排序后它们分别变成：[1, 8, 23],[3, 44],[34, 45],[6, 43],[2, 4]，此时整个数组变成 [1, 3, 34, 6, 2, 8, 44, 45, 43, 4, 23] 第二遍（2 间隔排序）：按照间隔 2 分割子数组，共分成两组，分别是[1, 34, 2, 44, 43, 23],[3, 6, 8, 45, 4]。对他们进行插入排序，排序后它们分别变成：[1, 2, 23, 34, 43, 44],[3, 4, 6, 8, 45]，此时整个数组变成[1, 3, 2, 4, 23, 6, 34, 8, 43, 45, 44]。这里有一个非常重要的性质：当我们完成 2 间隔排序后，这个数组仍然是保持 5 间隔有序的。也就是说，更小间隔的排序没有把上一步的结果变坏。 第三遍（11 间隔排序，等于直接插入排序）：按照间隔 1 分割子数组，分成一组，也就是整个数组。对其进行插入排序，经过前两遍排序，数组已经基本有序了，所以这一步只需经过少量交换即可完成排序。排序后数组变成[1, 2, 3, 4, 6, 8, 23, 34, 43, 44, 45]，整个排序完成。 const sort = arr =>

{const len = arr.length; if (len

< 2) { return arr; } let gap = Math.floor(len / 2); while (gap >

0) {for (let I = gap; I

< len; i++) { let j = i; let cur = arr[i]; while (j >

= 0 & & cur

< arr[j - gap]) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = cur; } gap = Math.floor(gap / 2); } return arr;}堆排序 堆排序过程如下： 用数列构建出一个大顶堆，取出堆顶的数字(放到待排序数组的最后)； 调整剩余的数字，构建出新的大顶堆，再次取出堆顶的数字； 循环往复，完成整个排序。 function sort(arr) { for (let i = Math.floor(arr.length / 2) - 1; i >

= 0; Imura -) {adjustHeap (arr, I, arr.length)} for (let j = arr.length-1; j > 0; jmure -) {[arr [0], arr [j]] = [arr [j], arr [0]] adjustHeap (arr, 0, j)}} function adjustHeap (arr, I, length) {let tmp = arr [I] for (let k = I * 2 + 1;

< length; k = k * 2 + 1) { if (k + 1 < length && arr[k] < arr[k + 1]) { k++; } if (arr[k] >

Tmp) {arr [I] = arr [k]; I = k;} else {break;} arr [I] = tmp;}} Quick sort

The fast sorting algorithm was proposed by C. A. R. Hoare in 1960. Its time complexity is also O (nlogn), but among several sorting algorithms whose time complexity is O (nlogn), it is more efficient in most cases, so fast sorting is widely used. In addition, the divide-and-conquer idea used in quick sorting is very practical, which makes quick sorting favored by interviewers, so it is particularly important to master the idea of quick sorting.

The basic idea of quick sorting algorithm is:

Take a number from the array and call it the pivot.

Iterate through the array, putting the number larger than the cardinality on its right and the number smaller than the cardinality on its left. After traversing, the array is divided into left and right regions

Treat the left and right regions as two arrays and repeat the first two steps until the sorting is complete

In fact, each traversal of the quick sort puts the cardinality to the final position. The first round traversal arranges 1 cardinality, the second round traversal arranges 2 cardinals (one cardinality for each region, but if a region is empty, this round can only arrange one cardinality), the third round traversal arranges 4 cardinals (similarly, in the worst case, only one cardinality), and so on. The total number of iterations is logn~n, and the time complexity of each round is O (n), so it is easy to analyze that the time complexity of fast sorting is O (nlogn) ~ O (N2), and the average time complexity is O (nlogn).

Const partition = (arr, start, end) = > {let pivot = arr [start]; / / take the first number as the cardinality let left = start + 1; / / partition let right = end; / / right boundary / / left from the second number, exit the loop while (left) when right encounters

< right) { // 找到第一个大于基数的位置 while (left < right && arr[left] pivot) right--; // 将基数和中间数交换 if (right != start) [arr[left], pivot] = [pivot, arr[left]]; // 返回中间值的下标 return right;}const quickSort = (arr, start, end) =>

{if (start > = end) return; const middle = partition (arr, start, end) quickSort (arr, start, middle-1); quickSort (arr, middle + 1, end);} const sort = arr = > {quickSort (arr, 0, arr.length-1);} merge sort

Merge sorting is an effective sorting algorithm based on merge operation. This algorithm is a very typical application of divide-and-conquer (Divide and Conquer). The ordered subsequences are merged to get a completely ordered sequence, that is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are merged into one ordered table, it is called 2-path merging.

Algorithm description

The input sequence of length n is divided into two subsequences of length n

Merge and sort the two subsequences respectively.

Merge two sorted subsequences into a final sorted sequence.

Const merge = (left, right) = > {let result = []; while (left.length > 0 & & right.length > 0) {if (left [0] {let len = arr.length; if (len < 2) {return arr;} const middle = Math.floor (len / 2), left = arr.slice (0, middle), right = arr.slice (middle) Return merge (sort (left), sort (right));}; "how to implement seven sorting algorithms with JavaScript" ends here. Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.