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

Editor to share with you how JavaScript to achieve the four commonly used sorting, I hope you will learn something after reading this article, let's discuss it together!

I. insert sort

Insertion sort includes direct insert sort, half insert sort and Hill sort. Here, only the commonly used direct insertion sort is implemented.

Directly insert sort

Treat the left sequence as an ordered sequence, and insert a number into the ordered sequence one at a time.

When inserting, the comparison starts from the far right of the ordered sequence, and if the number of comparisons is large, move back one bit.

Function insertSort (array) {/ / the first for has been arranged by default (let I = 1; I

< array.length; i++) { let target = i; for (let j = i - 1; j >

= 0; jmurf -) {if (array [target]

< array[j]) { [array[target], array[j]] = [array[j], array[target]] target = j; } else { break; } } } return array; } 复杂度 时间复杂度：O(n2) 空间复杂度:O(1) 稳定性 稳定 二、交换排序（1）冒泡排序 循环数组，比较当前元素和上一个元素，如果当前元素比上一个元素小，向下冒泡。 这样一次循环之后最前一个数就是本数组最小的数。 下一次循环继续上面的操作，不循环已经排序好的数。 优化：当一次循环没有发生冒泡，说明已经排序完成，停止循环。 function bubbleSort(array) { //第一个循环是所需次数 for (let j = 0; j < array.length; j++) { let complete = true; for (let i = array.length-1; i>

J; iMel -) {/ / compare adjacent numbers if (array [I])

< array[i -1]) { [array[i], array[i - 1]] = [array[i - 1], array[i]]; complete = false; } } // 没有冒泡结束循环 if (complete) { break; } } return array; } 复杂度 时间复杂度：O(n2) 空间复杂度:O(1) 稳定性 稳定 （2）快速排序 快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有序序列。 实现步骤： 选择一个基准元素target（一般选择第一个数） 将比target小的元素移动到数组左边，比target大的元素移动到数组右边 分别对target左侧和右侧的元素进行快速排序 从上面的步骤中我们可以看出，快速排序也利用了分治的思想（将问题分解成一些小问题递归求解） 下面是对序列6、1、2、7、9、3、4、5、10、8排序的过程： //JS自带的sort()就是快排function quickSort(array, start, end) { if (end - start < 1) { return; } const target = array[start]; let l = start; let r = end; while (l < r) { while (l < r && array[r] >

= target) {r muri;} array [l] = array [r]; while (l)

< r && array[l] < target) { l++; } array[r] = array[l]; } array[l] = target; quickSort(array, start, l - 1); quickSort(array, l + 1, end); return array; } 复杂度 时间复杂度：平均O(nlogn)，最坏O(n2)，实际上大多数情况下小于O(nlogn) 空间复杂度:O(logn)（递归调用消耗） 稳定性 不稳定 三、选择排序（1）简单选择排序 每次循环选取一个最小的数字放到前面的有序序列中。 function selectionSort(array) { for (let i = 0; i < array.length - 1; i++) { let minIndex = i; for (let j = i + 1; j < array.length; j++) { if (array[j] < array[minIndex]) { minIndex = j; } } [array[minIndex], array[i]] = [array[i], array[minIndex]]; } } 复杂度 时间复杂度：O(n2) 空间复杂度:O(1) 稳定性 不稳定 （2）堆排序 创建一个大顶堆，大顶堆的堆顶一定是最大的元素。 交换第一个元素和最后一个元素，让剩余的元素继续调整为大顶堆。 从后往前以此和第一个元素交换并重新构建，排序完成。 function heapSort(array) { creatHeap(array); console.log(array); // 交换第一个和最后一个元素，然后重新调整大顶堆 for (let i = array.length - 1; i >

0; array -) {[array [I], array [0]] = [array [0], array [I]]; adjust (array, 0, I);} return array;} / / build a large top heap, starting with the first non-leaf node, sinking operation function creatHeap (array) {const len = array.length; const start = parseInt (len / 2)-1 For (let I = start; I > = 0; Imuri -) {adjust (array, I, len);}} / / sink the target element. If the child node is larger than him, sink function adjust (array, target, len) {for (let I = 2 * target + 1; I)

< len; i = 2 * i + 1) { // 找到孩子节点中最大的 if (i + 1 < len && array[i + 1] >

Array [I]) {I = I + 1;} / / sinking if (array [I] > array [target]) {[array [I], Array [target]] = [array [target], Array [I]] target = I;} else {break;}}

Complexity

Time complexity: O (nlogn)

Space complexity: O (1)

Stability.

Unstable

IV. Merging and sorting

A sorting method realized by using the idea of merger.

This algorithm is a very typical application of divide-and-conquer (Divide and Conquer). The divide-and-conquer method divides the problem into small problems and then solves them recursively, while the stage of governance "patches" the answers obtained in different stages, that is, divide and conquer.

Merge the ordered subsequences to get a completely ordered sequence.

That is, to order each subsequence first, and then to order the segments of the subsequence.

If two ordered tables are merged into one ordered table, it is called two-way merging.

Split:

Split the array from the midpoint and divide it into left and right arrays

Recursively split the left and right arrays until the array length is less than 2

Merge:

If you need to merge, then the left and right arrays are in order.

Create a temporary storage array temp, compare the first element of the two arrays, and add the smaller element to the temporary array

If one of the left and right arrays is empty, then the other array must be larger than all the elements in the temp and directly add all its elements to the temp

Function mergeSort (array) {if (array.length)

< 2) { return array; } const mid = Math.floor(array.length / 2); const front = array.slice(0, mid); const end = array.slice(mid); return merge(mergeSort(front), mergeSort(end)); } function merge(front, end) { const temp = []; while (front.length && end.length) { if (front[0] < end[0]) { temp.push(front.shift()); } else { temp.push(end.shift()); } } while (front.length) { temp.push(front.shift()); } while (end.length) { temp.push(end.shift()); } return temp; } 做题时，上面多了删除过程，特别大的例子，时间也可能会超，用下面的方法 function merge(left, right){ let leftLen = left.length, rightLen = right.length; let i = 0, j = 0; let temp = new Array(leftLen + rightLen); for(let cur = 0; cur < leftLen + rightLen; cur++){ // 检查i, j有没有超界 if(i >

= leftLen) temp [cur] = right [jacks +]; else if (j > = rightLen) temp [cur] = left [iTunes +]; else if (left [I]

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.