JavaScript implements insertion sort of classic sorting algorithm

Although the code implementation of insertion sort is not as simple and crude as bubble sort and selection sort, its principle should be the easiest to understand, because anyone who has played poker should be able to understand it in seconds. Like sorting a hand of poker, we start with our left hand empty and the cards on the table face down. We then take one card at a time from the table and insert it into the correct position in the left hand. To find the correct position of a card, we compare it with every card already in the hand from right to left. The cards held in the left hand are always sorted and originally were the top cards in the pile on the table. .

1) Algorithm principle

The algorithm description of insertion sort (Insertion-Sort) is a simple and intuitive sorting algorithm. It works by building an ordered sequence. For unsorted data, it scans from back to front in the sorted sequence to find the corresponding position and insert it. In the implementation of insertion sort, in-place sorting is usually used (that is, sorting that only uses O(1) extra space). Therefore, during the scanning process from back to front, it is necessary to repeatedly and gradually shift the sorted elements backward. , providing insertion space for the latest element.

2) Algorithm description and implementation

Generally speaking, insertion sort is implemented on the array using in-place. The specific algorithm is described as follows:

<1> Starting from the first element, the element can be considered to have been sorted;

<2> Take out the next element, after the sorted element Scan from back to front in the sequence;

<3> If the element (sorted) is larger than the new element, move the element to the next position;

<4> Repeat the steps 3. Until you find a position where the sorted element is less than or equal to the new element;

<5> After inserting the new element into that position;

<6> Repeat steps 2~5 .

3) JavaScript code implementation

function insertSort(arr) { for (var i = 1; i < arr.length; i++) { var temp = arr[i]; var j = i - 1; while (j >= 0 && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } return arr; } var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52]; console.log(insertSort(arr));

Improved insertion sort: Use binary search when finding the insertion position.

Steps:
In the sequence, the two points were found to find the first number larger than it;
& lt; 3 & gt; insert the new element after the location;

function binaryInsertionSort(arr) { for (var i = 1; i < arr.length; i++) { var key = arr[i],left = 0,right = i - 1; while (left <= right) { var middle = parseInt((left + right) / 2); if (key < arr[middle]) { right = middle - 1; } else { left = middle + 1; } } for (var j = i - 1; j >= left; j--) { arr[j + 1] = arr[j]; } arr[left] = key; } return arr; } var arr = [1, 45, 37, 5, 48, 15, 37, 26, 29, 2, 46, 4, 17, 50, 52]; console.log(binaryInsertionSort(arr));

Worst case: the input array is sorted in descending order. T(n) = O(n2)
Average situation: T(n) = O(n2)

The above is the entire content of this article. I hope it will be helpful to everyone’s study. I also hope that everyone will learn more. Support PHP Chinese website.

For more articles related to insertion sort using JavaScript to implement the classic sorting algorithm, please pay attention to the PHP Chinese website!