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

This article mainly introduces the time complexity of bubbling sorting, quick sorting and heap sorting in programming technology, which is very detailed and has certain reference value. Interested friends must finish reading it!

Time complexity of bubble sorting: "O (n)" at best and "O (N2)" at worst. Time complexity of quick sorting: "O (nlogn)" at best and "O (N2)" at worst. The time complexity of heap sorting is "O (nlogn)".

The operating environment of this tutorial: windows7 system, Dell G3 computer.

Bubble sort (Bubble Sort)

Time complexity

Best-case scenario: the array itself is sequential, and the outer loop traverses once to complete O (n).

Worst-case scenario: the array itself is in reverse order, traversing the inner and outer layers of O (N2).

Space complexity

Open up a space exchange order O (1)

Stability.

Stable, because if the if judgment is not valid, the order will not be exchanged and the same elements will not be exchanged.

Bubble sorting is the simplest of all sorting algorithms. However, from a run-time point of view, bubble sorting is the worst, with a complexity of O (N2).

The bubble sort compares any two adjacent items, and if the first is larger than the second, swap them. The element item moves up to the correct order, just as the bubble rises to the surface, hence the name bubble sort.

When exchanging, we use an intermediate value to store the value of an exchange item. This method is also used in other sorting methods, so we declare a method to place this interchange code for reuse. Using ES6 (ECMAScript 2015) * * enhanced object attributes-the deconstruction assignment syntax for object arrays, * * this function can be written as follows:

[array [index1], Array [index2]] = [array [index2], Array [index1]]

Specific implementation:

Function bubbleSort (arr) {for (let I = 0; I)

< arr.length; i++) {//外循环（行{2}）会从数组的第一位迭代 至最后一位，它控制了在数组中经过多少轮排序 for (let j = 0; j < arr.length - i; j++) {//内循环将从第一位迭代至length - i位，因为后i位已经是排好序的，不用重新迭代 if (arr[j] >

Arr [j + 1]) {/ / if the previous bit is greater than the latter bit [arr [j], arr [j + 1]] = [arr [j + 1], arr [j]]; / / Exchange position} return arr;} Quick sort

Time complexity

Best-case scenario: each time the base value is exactly equal to the entire array, O (nlogn)

Worst-case scenario: each time the base value is the maximum / minimum value in the array, O (N2)

Space complexity

Quick sorting is recursive and needs the help of the stack to save the recursive call information of each layer, so the space complexity is consistent with the depth of the recursive tree.

Best-case scenario: each time the base value is exactly divided into the entire array, the depth of the recursive tree O (logn)

Worst-case scenario: each time the base value is the maximum / minimum value in the array, the depth of the recursive tree O (n)

Stability.

Quick sorting is unstable because the same keywords may be exchanged.

Quick sort is recursive

Special case: left > right, exit directly.

Steps:

(1) first, select the middle item from the array as the principal element base, usually taking the first value.

(2) create two pointers, one on the left to the first item in the array and the other to the last item in the array. Move the right pointer until you find an element smaller than the principal element, then move the left pointer until we find an element larger than the principal element, and then exchange them, repeating the process until the left pointer meets the right pointer. This process will make the values smaller than the principal element come before the principal element, and the values larger than the principal element come after the principal element. This step is called a partition operation.

(3) then exchange the element of the principal element and the position where the pointer stops (that is to say, put this element back, the one on the left is smaller than him, the one on the right is larger than him, and this position is his final position)

(4) then, the algorithm repeats the previous two steps (recursive method) for the divided decimal array (a subarray of values smaller than the principal element and a subarray of values larger than the principal element).

The recursive exit is left/right=i, that is:

Left > iMur1 / iTun1 > right

At this point, the subarray array is sorted.

Schematic diagram of returning to position:

Specific implementation:

Function quicksort (arr, left, right) {if (left > right) {return;} var I = left, j = right, base = arr [left]; / / Datum always takes the element at the beginning of the sequence / / var [base, I, j] = [arr [left], left, right] / / when the left pointer element is base while (I! = j) {/ / iExj, when the two pointers meet, the sorting is completed at one time, jumping out of the loop / / because the operations in each big loop will change the values of I and j, so before each loop / operation, it is necessary to judge whether it satisfies the I = base) {/ / find the right pointer element a that is less than base, and jump out of the loop, otherwise move a JFI to the left. } while (I

< j && arr[i] = 0; i--) { headAdjust(arr, i, arr.length); //对每一个节点都调整堆，使其满足大顶堆规则 }} 步骤二：调整指定结点形成大根堆 建立childMax指针指向child最大值节点，初始值为2 * cur + 1，指向左节点 当左节点存在时（左节点索引小于数组length），进入循环，递归调整所有节点位置，直到没有左节点为止（cur指向一个叶结点为止），跳出循环，遍历结束 每次循环，先判断右节点存在时，右节点是否大于左节点，是则改变childMax的指向 然后判断cur根节点是否大于childMax， 大于的话，说明满足大顶堆规律，不需要再调整，跳出循环，结束遍历 小于的话，说明不满足大顶堆规律，交换根节点和子结点， 因为交换了节点位置，子结点可能会不满足大顶堆顺序，所以还要判断子结点然后，改变cur和childMax指向子结点，继续循环判断。 //从输入节点处调整堆function headAdjust(arr, cur, len) { let intialCur = arr[cur]; //存放最初始的 let childMax = 2 * cur + 1; //指向子树中较大的位置，初始值为左子树的索引 //子树存在（索引没超过数组长度）而且子树值大于根时，此时不符合大顶堆结构，进入循环，调整堆的结构 while (childMax < len) { //判断左右子树大小,如果右子树更大，而且右子树存在，childMax指针指向右子树 if (arr[childMax] < arr[childMax + 1] && childMax + 1 < len) childMax++; //子树值小于根节点，不需要调整，退出循环 if (arr[childMax] < arr[cur]) break; //子树值大于根节点，需要调整，先交换根节点和子节点 swap(arr, childMax, cur); cur = childMax; //根节点指针指向子节点，检查子节点是否满足大顶堆规则 childMax = 2 * cur + 1; //子节点指针指向新的子节点 }} 步骤三：利用堆进行排序 从后往前遍历大顶堆（数组），交换堆顶元素a[0]和当前元素a[i]的位置，将最大值依次放入数组末尾。 每交换一次，就要重新调整一下堆，从根节点开始，调整根节点～i-1个节点（数组长度为i），重新生成大顶堆

/ / heap sort function heapSort (arr) {if (arr.length = 0; iMel -) {swap (arr, I, 0); / / swap the position of the last position and the first position (heap top maximum) headAdjust (arr, 0, I); / / adjust the root node ~ iMel 1 node to regenerate the large top heap} return arr;}

Complete code:

/ / swap array elements function swap (a, I, j) {[a [I], a [j]] = [a [j], a [I]];} / / adjust heap function headAdjust (arr, cur, len) {let intialCur = arr [cur] from the input node; / / store the original let childMax = 2 * cur + 1 / / pointing to a larger position in the subtree, if the index / / subtree with the initial value of the left subtree exists (the index does not exceed the length of the array) and the subtree value is greater than the root, it does not conform to the large top heap structure, enter the loop and adjust the heap structure while (childMax).

< len) { //判断左右子树大小,如果右子树更大，而且右子树存在，childMax指针指向右子树 if (arr[childMax] < arr[childMax + 1] && childMax + 1 < len) childMax++; //子树值小于根节点，不需要调整，退出循环 if (arr[childMax] < arr[cur]) break; //子树值大于根节点，需要调整，先交换根节点和子节点 swap(arr, childMax, cur); cur = childMax; //根节点指针指向子节点，检查子节点是否满足大顶堆规则 childMax = 2 * cur + 1; //子节点指针指向新的子节点 }}// 建立大顶堆function buildHeap(arr) { //从最后一个非叶子节点开始，向前遍历， for (let i = Math.floor(arr.length / 2 - 1); i >

= 0; iMel -) {headAdjust (arr, I, arr.length); / / A pair of each node adjusts the heap to meet the large top heap rule}} / / Heap sorting function heapSort (arr) {if (arr.length = 0; iMel -) {swap (arr, I, 0); / / swap the position of the last position and the first position (heap top maximum) headAdjust (arr, 0, I) / / adjust the root node ~ iMel 1 node to regenerate the big top heap} return arr;} the above is all the contents of the article "what is the time complexity of bubbling sorting, quick sorting and heap sorting in programming technology". Thank you for reading! Hope to share the content to help you, more related knowledge, welcome to follow the industry information channel!

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.