I. Conceptual cognition

Data structure: A collection of data elements having one or more specific relationships with each other;

1. A finite number of steps to solve a particular problem;

Relationship between data structure and algorithm: Data structure is the bottom layer and algorithm is the top layer. Data structures serve algorithms. Algorithms operate around data structures.

Data structure characteristics: Each data structure has its own characteristics. For example: Queue: First in, first out. Stack: First in last out. And so on;

The characteristics of the algorithm: the algorithm has five basic characteristics: input, output, finite, deterministic and feasibility.

2. Introduction to sorting algorithm

1. Definition of sort: sort a sequence of objects according to a keyword;

2. Evaluation criteria for the algorithm:

Stability: if a is ahead of B and a= B, a is still ahead of B after sorting;

Unstable: If a is already in front of B, and A = B, a may appear behind B after sorting;

Internal sort: All sort operations are done in memory;

External sort: Because the data is too large, the data is placed on disk, and the sort can only be carried out by disk and memory data transfer;

Time complexity: the amount of time an algorithm takes to execute;

Space complexity: The amount of memory required to run a program.

3. Summary of sorting algorithm picture

N: data size K: number of buckets In-place: occupies constant memory, does not occupy extra memory out-place: occupies extra memory

4. Sort and classify

Three, eight commonly used sorting algorithm details

1, direct insert sort

1, idea: each step will be a record to be sorted according to the size of its sorting code value, inserted into the previous file has been arranged in the appropriate position, until all inserted.

Application scenario: Use insertion sort for nearly ordered arrays.

2. Code implementation:

function insertSort(arr) { let length = arr.length; for(let i = 1; i < length; i++) { let temp = arr[i]; let j = i; for(; j > 0; j--) { if(temp >= arr[j-1]) { break; } arr[j] = arr[j-1]; } arr[j] = temp;} arr[j] = temp; } return arr; } / / example let arr =,5,10,7,10,32,90,9,11,1,0,10 [2] the console. The log (insertSort (arr));Copy the code

3. Gifs:

2. Hill sort

1. Idea: Take an integer d1 less than N as the first increment, divide all the records in the file into D1 groups, and put all the records whose distance is a multiple of dI into the same group. Direct insertion sequencing was performed in each group

Then, the grouping and sorting above is repeated with the second increment D2 <d1 until the increment Dr =1(Dr < DR-1 <0<d2<dl), that is, all records are placed in the same group for direct insertion sort. The method is essentially a grouping insertion method.

2. Code implementation:

function shellSort(arr) { var len = arr.length, temp, gap = 1; Console. time(' Hill sort time :'); While (gap < len/5) {// Dynamically define interval sequence gap =gap*5+1; } for (gap; gap > 0; gap = Math.floor(gap/5)) { for (var i = gap; i < len; i++) { temp = arr[i]; for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) { arr[j+gap] = arr[j]; } arr[j+gap] = temp; }} console.timeEnd(' Hill sort time :'); return arr; } var arr =,44,38,5,47,15,36,26,27,2,46,4,19,50,48 [3]; console.log(shellSort(arr)); / / [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]Copy the code

3. Select sort directly

1, idea: first, select the record with the smallest sort code from all the records and exchange it with the first record, then select the record with the smallest sort code from the rest of the records and exchange it with the second record… And so on until all the records are sorted.

2. Code implementation:

function selectionSort(arr) { var len = arr.length; var minIndex, temp; Console. time(' Select sort time '); for (var i = 0; i < len - 1; i++) { minIndex = i; for (var j = i + 1; j < len; J ++) {if (arr[j] < arr[minIndex]) {// find minIndex = j; }} temp = arr[I]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } console.timeEnd(' select sort time '); return arr; } var arr =,44,38,5,47,15,36,26,27,2,46,4,19,50,48 [3]; console.log(selectionSort(arr)); / / [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]Copy the code

4. Heap sort

1. Idea: Heap sort is a tree selection sort, which is an effective improvement on direct selection sort. It achieves the purpose of sorting by building the initial heap and continuously rebuilding the heap, and output the sort keywords in order one by one.

2. Code implementation:

/* heapSort @param array */ function heapSort(array) {console.time(' heapSort '); If (Object. The prototype. ToString. Call (array). Slice (8, 1) = = = 'array') {/ / build var heapSize = array length, temp. for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) { heapify(array, i, heapSize); } // heap sort for (var j = heapsie-1; j >= 1; j--) { temp = array[0]; array[0] = array[j]; array[j] = temp; heapify(array, 0, --heapSize); } console.timeEnd(' heap sort time '); return array; } else { return 'array is not an Array! '; }} /* @param arr @param x subscript @param len heap size */ function heapify(arr, x, len) { if (Object.prototype.toString.call(arr).slice(8, -1) === 'Array' && typeof x === 'number') { var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp; if (l < len && arr[l] > arr[largest]) { largest = l; } if (r < len && arr[r] > arr[largest]) { largest = r; } if (largest ! = x) { temp = arr[x]; arr[x] = arr[largest]; arr[largest] = temp; heapify(arr, largest, len); } } else { return 'arr is not an Array or x is not a number! '; Var arr =}} [91,60,96,13,35,65,46,65,10,30,20,31,77,81,22]; console.log(heapSort(arr)); //[10, 13, 20, 22, 30, 31, 35, 46, 60, 65, 65, 77, 81, 91, 96]Copy the code

5. Bubble sort

1. Idea: Compare adjacent elements, and if the former element is larger than the latter, swap the positions of the two elements; Do the same for each pair of adjacent elements, starting from the first pair of elements to the last pair of elements at the end, and the element at the last position is the maximum.

2. Code implementation:

function bubbleSort (arr) { var max = arr.length - 1; for (var j = 0; j < max; Var done = true; var done = true; for (var i = 0; i < max - j; i++) { if (arr[i] > arr[i + 1]) { [arr[i], arr[i+1]] = [arr[i+1], arr[i]]; done = false; } } if (done) { break; } } return arr; }Copy the code

Quicksort

1. Idea: a divide-and-conquer strategy is adopted to decompose the original problem into several smaller sub-problems with similar structures to the original problem. Solve these subproblems recursively, and then combine the solutions of these subproblems into solutions of the original problem.

It’s one of the fastest sorting algorithms for big data.

2. Code implementation:

Function quickSort(array, left, right) {console.time('1 '); Quicksort time '); if (Object.prototype.toString.call(array).slice(8, -1) === 'Array' && typeof left === 'number' && typeof right === 'number') { if (left < right) { var x = array[right], i = left - 1, temp; for (var j = left; j <= right; j++) { if (array[j] <= x) { i++; temp = array[i]; array[i] = array[j]; array[j] = temp; } } quickSort(array, left, i - 1); quickSort(array, i + 1, right); } console.timeEnd('1. Quicksort time '); return array; } else { return 'array is not an Array or left or right is not a number! '; Var quickSort2 = function(arr) {console.time('2 '); Quicksort time '); if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = []; for (var i = 0; i < arr.length; i++){ if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); }} console.timeEnd('2. Quicksort time '); return quickSort2(left).concat([pivot], quickSort2(right)); }; Var arr =,44,38,5,47,15,36,26,27,2,46,4,19,50,48 [3]; console.log(quickSort(arr,0,arr.length-1)); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] console.log(quickSort2(arr)); / / [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]Copy the code

3. Gifs:

Selection of benchmark method:

  • Head/tail is extremely unbalanced for ordered sequence segmentation

  • Random selection is better than sequence head, but it is expensive

  • Three-digit median split it will consider the element values of the three positions left, right, (left + right) / 2 in the sequence, and select their median as the baseline

Merge sort

1. Idea: Combine two or more ordered subtables into a new ordered table. At the beginning, the sequence containing N nodes is regarded as composed of n ordered sub-tables of length 1, and then they are merged in pairs to obtain some ordered sub-tables of length 2, and then they are combined in pairs until the ordered list of length N is obtained, and the sorting is finished.

2. Code implementation:

Var mergeSort(arr) {function mergeSort(arr) {var mergeSort(arr); if(len < 2) { return arr; } var middle = Math.floor(len / 2), left = arr.slice(0, middle), right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right)); } function merge(left, right) { var result = []; Console. time(' merge sort time '); while (left.length && right.length) { 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. timeEnd(' merge sort time '); return result; } var arr =,44,38,5,47,15,36,26,27,2,46,4,19,50,48 [3]; console.log(mergeSort(arr));Copy the code

3. Examples:

8. Radix sort

1. The key codes of the order are distributed and collected from the low order to the high order. After d distribution and collection, an ordered sequence can be obtained.

2. Code implementation:

/** * Base sort applies to: * (1) The data range is small, * @author xiazdong * @param arr * @param maxDigit */ /LSD Radix Sort function radixSort(arr, maxDigit) { var mod = 10; var dev = 1; var counter = []; Console. time(' radix sort time '); for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { for(var j = 0; j < arr.length; j++) { var bucket = parseInt((arr[j] % mod) / dev); if(counter[bucket]== null) { counter[bucket] = []; } counter[bucket].push(arr[j]); } var pos = 0; for(var j = 0; j < counter.length; j++) { var value = null; if(counter[j]! =null) { while ((value = counter[j].shift()) ! = null) { arr[pos++] = value; }}}} console.timeEnd(' radix sort time '); return arr; } var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]; console.log(radixSort(arr,2)); / / [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]Copy the code

4. Application scenarios

1. If n is small (such as n≤50), direct insertion or direct selection sort can be used. When the record size is small, direct insertion sort is better. Otherwise, because the number of records directly selected to move is less than that of directly inserted, direct selection sort should be selected.

2, if the initial state of the file is basically orderly (positive order), it should choose direct insertion, bubble or random quick sort is appropriate;

3. If n is large, the sorting method with time complexity of O(NLGN) should be adopted: quicksort, heap sort or merge sort.

Quicksort is considered to be the best method of internal sorting based on comparison. When the keywords to be sorted are randomly distributed, the average time of quicksort is the shortest. Heap sort requires less auxiliary space than quicksort and does not have the worst possible case of quicksort. Both kinds of ordering are unstable.

If stable sorting is required, merge sort can be used. However, the pair-merge sorting algorithm introduced earlier from a single record is not recommended and can usually be used in conjunction with direct insert sort. A long ordered subsequence is obtained by direct insertion sort and then merges. Because direct insertion sort is stable, the improved merge sort is still stable.

Refer to the link