Several ways to write sorting using typescript
1. Bubble sort
Bubble sorting is a simple sorting algorithm. It repeatedly visits the sequence to be sorted, compares two elements at a time, and exchanges them if they are in the wrong order. The work of visiting the sequence is repeated until there is no need to exchange, that is, the sequence has been sorted. The name of this algorithm comes from the fact that smaller elements will slowly "float" to the top of the sequence through exchange.
1.1} algorithm description
- Compare adjacent elements. If the first is bigger than the second, exchange them two;
- Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end, so that the last element should be the largest number;
- Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end, so that the last element should be the largest number;
- Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end, so that the last element should be the largest number;
1.2} dynamic diagram demonstration
1.3} code implementation//Here we define the common array in advance //let sortArr :number [] = [0,2,4,6,8,10,9,7,5,3,1]; /* 1.Bubble sorting Time complexity (average): O(n) ²) Time complexity (worst): O(n) ²) Time complexity (best): O(n) Space complexity: O(1) Stability: stable */ function bubbleSort(arr :number[]) :any{ let len :number = arr.length; if(len < 2) { console.log(arr); return arr } for(let i :number = 0; i < len - 1; i++){ for(let j :number = 0; j < len -1; j++){ if(arr[j] > arr[j + 1]){ // Pairwise comparison of adjacent elements let temp :number = arr[j + 1]; // Element exchange arr[j + 1] = arr[j]; arr[j] = temp; } } } console.log("bubbleSort",arr); return arr; } bubbleSort(sortArr);2. Selection Sort
selection sort is a simple and intuitive sorting algorithm. Its working principle: first, find the smallest (large) element in the unordered sequence and store it at the beginning of the sorted sequence, then continue to find the smallest (large) element from the remaining unordered elements, and then put it at the end of the sorted sequence. And so on until all elements are sorted.
2.1} algorithm description
For the direct selection sorting of n records, the ordered results can be obtained through n-1 times of direct selection sorting. The specific algorithm is described as follows:
- Initial state: the disordered region is R[1... n], and the ordered region is empty;
- At the beginning of the ith sort (i=1,2,3... n-1), the current ordered area and disordered area are R[1... i-1] and R(i... n) respectively. This sequence selects the record R[k] with the smallest keyword from the current unordered area and exchanges it with the first record r in the unordered area, so that R[1... I] and R[i+1... n) become a new ordered area with an increase in the number of records and a new unordered area with a decrease in the number of records, respectively;
- At the end of n-1 trip, the array is ordered.
2.2} dynamic diagram demonstration
2.3} code implementation/* 2.Select sort Time complexity (average): O(n) ²) Time complexity (worst): O(n) ²) Time complexity (best): O(n) ²) Space complexity: O(1) Stability: unstable */ function selectionSort(arr :number[]) :any{ let len :number = arr.length; if(len < 2) { console.log(arr); return arr } let minIndex :number , temp :number; for(let i :number = 0; i < len - 1; i++){ minIndex = i; for(let j :number = i + 1; j < len; j++){ if(arr[j] < arr[minIndex]) minIndex = j } temp = arr [i]; arr[i] = arr[minIndex]; arr[minIndex] = temp } console.log('selectionSort:',arr); return arr; } selectionSort(sortArr);3. Insertion Sort
the algorithm description of insertion sort is a simple and intuitive sorting algorithm. Its working principle is to build an ordered sequence, scan the unordered data from back to front in the sorted sequence, find the corresponding position and insert it.
3.1} algorithm description
Generally speaking, insertion sorting is implemented on the array using in place. The specific algorithm is described as follows:
- Starting from the first element, the element can be considered to have been sorted;
- Take out the next element and scan from back to front in the sorted element sequence;
- If the element (sorted) is larger than the new element, move the element to the next position;
- Repeat step 3 until the sorted element is found to be less than or equal to the position of the new element;
- After inserting the new element into this position;
- Repeat steps 2 to 5.
3.2} dynamic diagram demonstration
3.3} code implementation/* 3.Insert sort Time complexity (average): O(n) ²) Time complexity (worst): O(n) ²) Time complexity (best): O(n) Space complexity: O(1) Stability: stable */ function insertionSort(arr :number[]) :any{ let len :number = arr.length; if(len < 2) { console.log(arr); return arr } let preIndex :number , current :number; for(let i :number = 1; i < len; i++){ preIndex = i - 1; current = arr[i]; while(preIndex >= 0 && arr[preIndex] > current){ arr[preIndex + 1] = arr[preIndex]; preIndex--; } arr[preIndex + 1] = current; } console.log('insertionSort:',arr); return arr; } insertionSort(sortArr);4. Shell Sort
in 1959, Shell invented the first sorting algorithm that breaks through O(n2), which is an improved version of simple insertion sorting. It differs from insert sort in that it preferentially compares elements that are far away. Hill sort is also called reduced incremental sort.
3.1} algorithm description
First, divide the whole record sequence to be sorted into several subsequences for direct insertion sorting. The specific algorithm description is as follows:
- Select an incremental sequence t1, t2,..., tk, where ti > TJ, tk=1;
- Sort the sequence k times according to the number of incremental sequences k;
- For each sorting, the sequence to be sorted is divided into several subsequences with length m according to the corresponding increment ti, and each sub table is directly inserted and sorted. Only when the increment factor is 1, the whole sequence is treated as a table, and the table length is the length of the whole sequence.
Fig. 3.3 dynamic demonstration
3.3} code implementation/* 4.Shell Sort Time complexity (average): O (1.3 square of n) Time complexity (worst): O(n) ²) Time complexity (best): O(n) Space complexity: O(1) Stability: unstable */ function shellSort(arr :number[]) :any{ let len :number = arr.length; if(len < 2) { console.log(arr); return arr } let gap :number = Math.floor(len / 2) for(gap; gap > 0; gap = Math.floor(gap / 2)){ for(let i :number = gap; i < len; i++){ let j :number = i; let current :number = arr[i]; while(j - gap >= 0 && current < arr[j - gap]){ arr[j] = arr[j - gap]; j = j - gap; } arr[j] = current; } } console.log('shellSort:',arr); return arr; } shellSort(sortArr);5. Merge Sort
The core of hill sorting is the setting of interval sequence. The interval sequence can be set in advance or defined dynamically. The algorithm for dynamically defining interval sequence was proposed by Robert Sedgewick, co-author of algorithm (4th Edition).
5.1} algorithm description
Merge sort is an effective sort algorithm based on merge operation. The algorithm is a very typical application of Divide and Conquer. The ordered subsequences are combined to obtain 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-way merging.
- The input sequence with length n is divided into two subsequences with length n/2;
- The two subsequences are sorted by merging;
- Merge two sorted subsequences into a final sorting sequence.
5.2} dynamic diagram demonstration
5.3 code implementation/* 5.Merge sort Time complexity (average): O(nlogn) Time complexity (worst): O(nlogn) Time complexity (best): O(nlogn) Space complexity: O(n) Stability: stable */ function mergeSort(arr :number[]) :any{ var len :number = arr.length; if (len < 2) { return arr; } var middle :number = Math.floor(len / 2), left :number[]= arr.slice(0, middle), right :number[]= arr.slice(middle); return merge(mergeSort(left), mergeSort(right)); } function merge(left:number[], right:number[]) :any{ var result :any= []; while (left.length>0 && right.length>0) { if (left[0] <= right[0]) result.push(left.shift()); else result.push(right.shift()); } while (left.length) result.push(left.shift()); while (right.length) result.push(right.shift()); console.log('mergeSort:',result); return result; } mergeSort(sortArr)6. Counting Sort
counting sorting is not a comparison based sorting algorithm. Its core is to convert the input data values into keys and store them in the additional array space. As a sort with linear time complexity, count sort requires that the input data must be integers with a certain range.
6.1} algorithm description
Find the largest and smallest elements in the array to be sorted;
- Count the number of occurrences of each element with value i in the array and store it in item i of array C;
- All counts are accumulated (starting from the first element in C, and each item is added to the previous item);
- Reverse fill the target array: put each element i in item C(i) of the new array, and subtract 1 from C(i) for each element.
6.2} dynamic diagram demonstration
6.3} code implementation/* 6.Count sort Time complexity (average): O(n + k) Complexity (K + time): worst Time complexity (best): O(n + k) Spatial complexity: O(n + k) Stability: stable */ function countingSort(nums :any) :any{ let arr :number[] = []; let max :number = Math.max(...nums); let min :number = Math.min(...nums); for(let i :number = 0, len :number= nums.length; i < len; i++) { let temp :number = nums[i]; arr[temp] = arr[temp] + 1 || 1; } let index :number = 0; for(let i :number = min; i<=max; i++) { while(arr[i] > 0) { nums[index++] = i; arr[i]--; } } console.log('countingSort:',arr); //Note that the sorting here is to sort the index of the array. If the index is empty, it will not be sorted return arr } countingSort(sortArr)