The third tier
Bubble sort
The idea of bubble sort is to compare adjacent elements in pairs. When an element is larger than the adjacent element on the right, they are swapped. When an element is less than or equal to the adjacent element on the right, the position does not change
The implementation code
Function bubbleSort(list:Array<number>) {for (let I = 0; i < list.length - 1; For (let j = 0; let j = 0; let j = 0; j < list.length - i -1; j++) { if( list[j] > list[j+1]) { let temp = list[j]; list[j] = list[j+1]; list[j+1] = temp } } } return list }Copy the codeOptimization 1: Whether tags are ordered
Function bubbleSortTwo(list:Array<number>) {for (let I = 0; i < list.length - 1; For (let j = 0; let j = 0; let j = 0; j < list.length - i -1; j++) { if( list[j] > list[j+1]) { let temp = list[j]; list[j] = list[j+1]; List [j+1] = temp = false}} if(isSorted) {break}} return list}Copy the codeOptimization 3: ordered area optimization
Function bubbleSortThree(list:Array<number>) {let sortBorder = list.length-1; // Let lastExcChangeIndex = 0; For (let I = 0; let I = 0; i < list.length - 1; i++) { let isSorted = true; For (let j = 0; let j = 0; j < sortBorder; j++) { if( list[j] > list[j+1]) { let temp = list[j]; list[j] = list[j+1]; list[j+1] = temp; // If an exchange occurs, then isSorted = false; LastExcChangeIndex = j}} sortBorder = lastExcChangeIndex if(isSorted) {break}} return list}Copy the codeCocktail optimization
Each round of bubble sort compares elements from left to right, making a one-way comparison, whereas cocktail sort compares and swaps elements in both directions
Function bubbleSortFour(list:Array<number>) {let outLength = math.floor (list.length/2) for (let i = 0; i < outLength; i++) { let sorted = true; For (let j = I; j < list.length - 1 - i; j++) { if(list[j] > list[j + 1]){ let temp = list[j]; list[j] = list[j + 1]; list[j + 1] = temp sorted = false } } if(sorted){ break } sorted = true; For (let j = list.length-1-i; j > i ; j--) { if(list[j] < list[j - 1]){ let temp = list[j]; list[j] = list[j - 1]; list[j - 1] = temp; sorted = false; } } if(sorted) { break } } return list }Copy the codeCocktail + ordered area optimization
Function bubbleSortFive(list:Array<number>) {let leftSortBorder = 0; let leftLastSortIndex= 0; let rightSortBorder = list.length - 1; let rightLastSortIndex = 0; Let outLength = math.floor (list.length/2) for (let I = 0; i < outLength; i++) { let sorted = true; For (let j = leftSortBorder; j < rightSortBorder; j++) { if(list[j] > list[j + 1]){ let temp = list[j]; list[j] = list[j + 1]; list[j + 1] = temp sorted = false; RightLastSortIndex = j; } // Assign the right boundary rightSortBorder = rightLastSortIndex if(sorted){break} sorted = true; For (let j = rightSortBorder; j > leftSortBorder ; j--) { if(list[j] < list[j - 1]){ let temp = list[j]; list[j] = list[j - 1]; list[j - 1] = temp; sorted = false; LeftLastSortIndex = j-1; If (sorted) {break}} return list}Copy the codeBest explanation: my personal blog, need TZ, here is the nugget version
Selection sort
The idea of selection sort: each round to select the smallest, directly switched to the left of the array
The implementation code
function sort(arr:Array<number>) {
for (let index = 0; index < arr.length - 1; index++) {
let minIndx = index;
for (let j = index + 1; j < arr.length; j++) {
if(arr[j] < arr[minIndx]) {
minIndx = j
}
};
let temp = arr[minIndx];
arr[minIndx] = arr[index];
arr[index] = temp
}
return arr
}
Copy the codeSelection sort solves the code efficiency problem caused by the frequent element exchange operation of bubble sort, but also becomes unstable sort
Best explanation: my personal blog, need TZ, here is the nugget version
Insertion sort
The idea of insertion sort is to maintain an ordered area and insert the elements one by one into the appropriate place in the ordered area until all the elements are ordered
The implementation code
function insertSort(arr:Array<number>) { for (let index = 1; index < arr.length; index++) { let temp = arr[index]; let j = index - 1; // Compare elements from the right and shift for (; j >= 0 && arr[j] > temp; J --) {arr[j + 1] = arr[j]} insertValue arr[j + 1] = temp} return arr};Copy the codeBest explanation: my personal blog, need TZ, here is the nugget version
summary
The average time complexity of the sorting algorithms in the third tier is O(n2).
Differences and differences
1. Performance
The number of comparisons and exchanges of elements in bubble and insert sorts depends on how ordered the original array is
But overall, insertion sort performs slightly better than bubble sort
Because in bubble sort, each of the two elements are exchanged independently of each other
Insertion sort is continuous
Obviously insertion sort eliminates a lot of unnecessary swapping
In addition, selection sort is different from the previous two. It has a fixed number of commutations of elements, regardless of the order of the original array
Therefore, when the original array is nearly ordered, the performance of insertion sort is the best, and when most elements of the original array are unordered, the performance of selection sort is the best
2. Whether it is stable
Bubble sort and insertion sort are stable, and selection sort is unstable
The second tier
Heap sort
Heapsort idea: Heapsort is a sorting algorithm based on binary heap, which has the ability of self-adjustment. It can be summarized as: to build the unordered array into binary heap, if the order needs to be ascending, the maximum binary heap will be built; if the order needs to be descending, the minimum binary heap will be built
The implementation code
/** * @param {Array<number>} arr Specifies the heap to be adjusted * @param {number} parentIndex Specifies the parent node to be dropped * @param {number} Length Specifies the valid heap size * @description */ function downAdjust(arr: Array<number>, parentIndex: Number, length:number) {// temp Stores the value of the parent node and uses it as the final assignment. Let temp = arr[parentIndex]; // Let childrenIndex = parentIndex * 2 + 1; While (childrenIndex < length) {// if right node is present, If (childrenIndex + 1 < length && ARR [childrenIndex + 1] > ARR [childrenIndex]) {childrenIndex = childrenIndex + 1; If (temp >= arr[childrenIndex]) {break} arr[parentIndex] = arr[childrenIndex]; parentIndex = childrenIndex childrenIndex = childrenIndex * 2 + 1 } arr[parentIndex] = temp; } /** * @param {Array<number>} * @description */ function heapSort(arr:Array<number>) {// 1. For (let index = arr.length-2; index >= 0; Index --) {downAdjust(arr, index, arr.length - 1)} console.log(' maximum heap: %j', arr) // 2. For (let index = arr.length-1; index >= 0; Index --) {// swap the last element with the top of the heap let temp = arr[0]; arr[0] = arr[index]; arr[index] = temp; / / sink to adjust the maximum heap downAdjust (arr. Zero, index) / / the index value of effective length of pile Very clever here}} the function main () {let arr = [1, 3, 2, 6, 5, 7, 8, 9, 10, 0]; heapSort(arr); console.log(arr) }Copy the codeBest explanation: my personal blog, need TZ, here is the nugget version
Merge sort
Merge sort idea: split the array into two groups, ordered merge, and recursion, classic divide and conquer idea
The implementation code
Function merge(arr:Array<number>, start:number, end:number, middle:number) { Let tempArray = new Array(end-start + 1); let p1 = start; let p2 = middle + 1; let p = 0; while(p1 <= middle && p2 <= end) { if(arr[p1] <= arr[p2] ) { tempArray[p++] = arr[p1++] } else { tempArray[p++] = While (p1 <= middle) {tempArray[p++] = arr[p1++]} while(p2 <= end) { TempArray [p++] = arr[p2++]} for (let index = 0; index < tempArray.length; index++) { arr[start + index] = tempArray[index] } } function sort(arr:Array<number>, start:number, End :number) {if(start < end) {/* start = 5; end = 10; The middle = 7; Note that we're rounding down: 5,6,7,8,9,10, so middle=7; 5,6,7 as a group; If 8, 9, 10 is a group of 6,7,8,9,10, middle=8; 6,7,8 as a group; 9 and 10 are a set of formulas: Math. Floor ((end-start)/2) + start Math.floor(A / Math.pow(2, B)) = > Math. Floor (A/(2 * * B)) = > (A > > B) so: Math. The floor ((end - start) / 2) + start = = = ((end - start) > > 1) + start * / / / Let middle = ((end-start)>>1) + start; let middle = ((end-start)>>1) + start; sort(arr, start, middle); sort(arr, middle + 1, end); Function main() {const arr = [5, 8, 6, 3, 9, 2, 1, 7]; const arr = [5, 8, 6, 3, 9, 2, 1, 7]; console.log(sort(arr, 0, arr.length - 1)) }Copy the codeBest explanation: my personal blog, need TZ, here is the nugget version
Quick sort
The idea of quicksort: Quicksort is also a classic representation of the idea of divide and conquer, namely: select a reference element, larger than it on one side, smaller than it on the other side, and recurse
Implementation code:
Bilateral method:
/** * @param {Array<number>} arr Array to be exchanged * @param {number} startIndex startIndex * @param {number} endIndex endIndex * @returns */ function partition(arR: Array<number>, startIndex: number, endIndex: number) Const pivot = arr[startIndex]; const pivot = arr[startIndex]; // Left pointer let left = startIndex; // Let right = endIndex; while(left ! = right) {// While (left < right && arr[right] > pivot) {right--} // While (left < right && arr[right] > pivot) {left -- Arr [left] <= pivot) {left++} if(left < right) {let p = arr[left]; arr[left] = arr[right]; arr[right] = p; } // Arr [startIndex] = arr[left]; arr[left] = pivot; /* How to ensure that the swapped left element is either less than or greater than the base element? If either left or right stops, If left <= right, then right must be an element less than = pivot */ return left} function quickSort(arr: Array<number>, startIndex: number, endIndex: Number) {if(startIndex >= endIndex) {return} let pivotIndex = partition(arR, startIndex, endIndex); QuickSort (ARR, startIndex, pivotIndex - 1); quickSort(arr, pivotIndex + 1, endIndex); } function main() { let arr = [4, 2, 6, 2, 2, 2, 2, 8]; quickSort(arr, 0, arr.length - 1 ); console.log(arr) }Copy the codeUnilateral method:
/** * @param {Array<number>} arr Array to be exchanged * @param {number} startIndex start position * @param {number} endIndex End position * @description Function partition(arR: Array<number>, startIndex: number, endIndex: number); Let pivot = arr[startIndex]; let pivot = arr[startIndex]; // Let mark = startIndex; for (let index = startIndex; index <= endIndex; index++) { if(arr[index] < pivot) { mark++; let p =arr[mark]; arr[mark] = arr[index]; arr[index] = p } } arr[startIndex] = arr[mark]; arr[mark] = pivot; return mark } function quickSort(arr: Array<number>, startIndex: number, endIndex: number){ if(startIndex >= endIndex) { return } const pivotIndex = partition(arr, startIndex, endIndex); quickSort(arr, startIndex, pivotIndex - 1); quickSort(arr, pivotIndex + 1, endIndex) } function main() { let arr = [4, 4, 6, 5, 3, 2, 8, 1]; quickSort(arr, 0, arr.length - 1); console.log(arr) }Copy the codeNon-recursive implementation:
/** * @param {Array<number>} arr Array to be sorted * @param {number} startIndex Start position * @param {number} endIndex End position * @returns Function partition(arR: Array<number>, startIndex: number, endIndex: number) Number) {// let pivot = arr[startIndex] // Let mark = startIndex for (let index = startIndex; index <= endIndex; index++) { if(arr[index] < pivot) { mark++; let p = arr[mark]; arr[mark] = arr[index]; arr[index] = p } }; arr[startIndex] = arr[mark]; arr[mark] = pivot; return mark } interface StackItem { startIndex: number; endIndex: number; } function quickSort(arr: Array<number>, startIndex: number, endIndex: Number) {// use a stack instead of a recursive call stack let quickSortStack:Array<StackItem> = []; Let obj:StackItem = {startIndex, endIndex}; quickSortStack.push(obj); While (quickSortStack.length) {let item = quickSortStack.pop() as StackItem; let { startIndex, endIndex } = item let pivotIndex = partition(arr, startIndex, endIndex); If (startIndex < pivotIndex - 1) {quickSortStack.push({startIndex, endIndex: pivotIndex - 1 }) } if(endIndex > pivotIndex + 1) { quickSortStack.push({ startIndex : pivotIndex + 1, endIndex: endIndex }) } } } function main() { let arr = [4, 4, 6, 5, 3, 2, 8, 1]; quickSort(arr, 0, arr.length - 1); console.log(arr) }Copy the codeBest explanation: my personal blog, need TZ, here is the nugget version
Hill sorting
Hill sort is an updated version of insertion sort, which does some “preprocessing” of the original array to make most of the elements of the original array ordered
The implementation code
function sort(arr: Array<number>) {
let d = arr.length;
while(d > 1) {
d = Math.floor(d / 2);
for (let x = 0; x < d; x++) {
for (let index = x + d; index < arr.length; index+=d) {
let temp = arr[index];
let j = index - d;
for (; j >= 0 && arr[j] > temp; j-= d) {
arr[index] = arr[j];
}
arr[j+ d] = temp;
}
}
}
return arr
}
Copy the codeBest explanation: my personal blog, need TZ, here is the nugget version
summary
The second tier is an order of magnitude better than the third tier
The average time complexity of hill sort is the fastest to reach O(n1.3), and the average time complexity of quicksort, merge sort and heapsort is in O(nlogn).
Differences between the latter three:
1. Quicksort has an average time of O(nlogn), but in the extreme case it is O(n2), while heapsort and merge sort are stable at O(nlogn).
2. In terms of average complexity, heapsort performance is slightly lower than quicksort and merge sort, mainly because the parent and child nodes of binary heap are not contiguous in memory
When access to memory data, order to store data, reading and writing is often the highest efficiency, according to the principle of the space limitations of CPU, each time the CPU access memory, the memory in the adjacent data is also stored in cache, read the data, the adjacent next time need not read from the memory, but directly read from the CPU cache
3. Merge sort is stable, heap sort and quicksort are unstable
4. Quicksort and heapsort do not require additional storage space, while merge sort requires the creation of merge array
The first tier
Count sorting
The idea of counting sort is to determine the position of elements based on their subscripts, without comparing or swapping elements
The implementation code
Simple version of
function countSort(arr: Array<number>):Array<number> { // 1. Let Max = arr[0]; for (let index = 1; index < arr.length; index++) { if(arr[index] > max) { max = arr[index] } } // 2. Let countArray = (new Array(Max + 1)).fill(0); For (let index = 0; // 3. index < arr.length; Index ++) {countArray[arr[index]]++} let sortedArray = new Array(); for (let index = 0; index <= countArray.length; index++) { for (let j = 0; j < countArray[index]; j++) { sortedArray.push(index) } } return sortedArray }Copy the codeOptimized version
function countSort(arr: Array<number>) { // 1. Let Max = arr[0]; let min = arr[0]; for (let index = 1; index < arr.length; index++) { if(arr[index] > max) { max = arr[index] } if(arr[index] < min) { min = arr[index] } } // 2. Let length = max-min + 1; let countArray = (new Array(length)).fill(0) // 3. For (let index = 0; index < arr.length; index++) { countArray[arr[index] - min]++ } // 4. Let sortedArray = [] for (let index = 0; index < countArray.length; index++) { for (let j = 0; j < countArray[index]; j++) { sortedArray.push(index + min) } } return sortedArray }Copy the codeStable version
function countSort(arr: Array<number>) { // 1. Let Max = arr[0]; let min = arr[0]; for (let index = 1; index < arr.length; index++) { if(arr[index] > max) { max = arr[index] } if(arr[index] < min) { min = arr[index] } } // 2. Let length = max-min + 1; let countArray = (new Array(length)).fill(0) // 3. For (let index = 0; index < arr.length; index++) { countArray[arr[index] - min]++ } // 4. For (let index = 1; let index = 1; index < countArray.length; index++) { countArray[index] += countArray[index - 1] } // 5. SortedArray = new Array(arr.length); sortedArray = new Array(arr.length); for (let index = arr.length - 1; index >= 0; SortedArray [countArray[arr[index] -min] -1] = arr[index] countArray[arr[index] -min] -1] = arr[index] countArray[arr] index - min]-- } return sortedArray }Copy the codeBest explanation: my personal blog, need TZ, here is the nugget version
Bucket sort
Bucket sort is an updated version of counting sort, making up for the limitations of counting sort (counting sort is not applicable to non-integer sort).
The implementation code
function bucketSort(arr:Array<number>) { // 1. D let Max = arr[0]; let min = arr[0]; for (let index = 0; index < arr.length; index++) { if(arr[index] > max) { max = arr[index] } if(arr[index] < min) { min = arr[index] } } const d = max - min; // 2. Const bucketNum = arr.length; / * small pit: Let bucketList = new Array(bucketNum).fill([]) */ let bucketList = new Array(bucketNum) for (let index = 0; index < bucketList.length; index++) { bucketList[index] = [] } // 3. Let area = d/(bucketnum-1); let area = d/(bucketnum-1); for (let index = 0; index < arr.length; index++) { let num = Math.floor((arr[index] - min)/area); BucketList [num].push(arr[index])} /* bucketList[num].push(arr[index])} (element -min)/area = the number of buckets in the array, which in theory should be round up, but the array index is from 0, so it is math.floor 2. Because (Max. -min)/area must be the last bucket and an integer, that is: d = max - min area = d/num result = (max - min)/area = (max - min)/d * num = (max - min)/(max - min) * num result === */ // 4. */ // 4. */ // 4. For (let index = 0; index < bucketList.length; index++) { bucketList[index] = bucketList[index].sort((a:number, B :number) => (a-b))} return bucketList.flat()}Copy the codeBest explanation: my personal blog, need TZ, here is the nugget version
Radix sort
Radix sort is also to solve the limitations of counting sort, such as sorting English words, the idea is: to split the work into multiple rounds, each round of a single character using counting sort
The implementation code
// Value range of ASCII code let ASCII = 128; function getCharIndex(str:string,index:number):number { if(str.length <= index) { return 0 } return str.charCodeAt(index) } function radixSort(arr:Array<string>, maxLength:number) { let sortedArray = new Array(arr.length); for (let k = maxLength - 1; k >= 0; K --) {// let countArray = new Array(ASCII).fill(0); for (let index = 0; index < arr.length; index++) { let i = getCharIndex(arr[index], k) countArray[i]++ } // 2. For (let index = 1; let index = 1; index < countArray.length; index++) { countArray[index] += countArray[index-1] } // 3. For (let index = arr.length-1; let index = arr. index >= 0; index--) { let i = getCharIndex(arr[index], k); let sortedIndex = countArray[i] - 1; sortedArray[sortedIndex] = arr[index]; countArray[i]-- } arr=[...sortedArray] } return arr } function main() { const arr = ['qd', 'abc', 'qwe', 'hhh', 'a', 'cws', 'ope']; console.log(radixSort(arr, 3)) }Copy the codesummary
The first echelon of sorting algorithms are linear complexity sorting algorithms
The counting sort algorithm has a time complexity of O(n + m) where m is the range of the original array
The bucket sort algorithm has a time complexity of O(n) where n is the number of buckets
The time complexity of radix sorting algorithm is O(k(n + m)), where K is the maximum number of bits of an element, and m is the value range of each bit
In addition, these three sorting algorithms are stable sorting
Great summary
Summary from: comic algorithm little grey algorithm journey + programmer little grey princess article