Basic concepts

Internal and external sorting

Internal sorting here refers to the sorting method that only uses computer memory instead of external memory.. Relative, External sorting is a sort method that uses both computer memory and external memory.. This article only discusses internal sorting.

classification

Compare and non compare sort

compare
In this case, we need to compare the sizes of two elements.( around) Sort by. Is there a sort algorithm that doesn't need to be compared? It does exist. But not much.. There are three common types： Counting sort, Bucket sorting, Radix sorting. They use statistical methods to avoid comparison. You can see these algorithms in detail..

Transformation

Only the position between two elements is changed at a time.

insert

The traversed elements are placed in the previously maintained sorted sequence.

Choice

Select the largest or smallest of the remaining elements.

After knowing the above concepts, Can better understand the classification（ It is suggested to have a look at it first, Look back after all sorting algorithms）

Stability (Stability)

Definition： If the sorting algorithm does not change the relative position of two elements with the same value, Then the algorithm has high stability.

This picture vividly explains the above definition：

Why is this concept important? If it's a stable algorithm,, We can sort names first, Sorting names.

(from:
https://stackoverflow.com/questions/1517793/what-is-stability-in-sorting-algorithms-and-why-is-it-important

<https://stackoverflow.com/questions/1517793/what-is-stability-in-sorting-algorithms-and-why-is-it-important>

Bubble sort (Bubble Sort)

1 algorithm

Traverse from the first element, Compare the size of the current element with the next element, If not, sort, Change of position. After the last element, And I'll go through it from the beginning. Until sorting is complete.

Analyse： Once per traverse, One decimal place forward, But the maximum number reaches the final bit; Final sort already at the end.

2 Code

basic
void bubble(vector<int>& arr){ for(int i=0;i<arr.size()-1;i++){ //only need
n-1 swaps to move the smallest to the front for(int j=0;j<arr.size()-1;j++){
if(arr[j]>arr[j+1]) swap(arr[j],arr[j+1]); //arr[j]>arr[j+1] stable
//arr[j]>=arr[j+1] unstable } } }
optimization1: Every time I traverse, See if the sorting has been completed in advance( use hasSorted). If so, Early termination.
void bubble1(vector<int>& arr){ bool hasSorted = false; for(int
i=0;i<arr.size()-1&&!hasSorted;i++){ hasSorted=true; for(int
j=0;j<arr.size()-1;j++){ if(arr[j]>arr[j+1]){ hasSorted = false;
swap(arr[j],arr[j+1]); } } } }
optimization2:
according to“ Analyse： Once per traverse, One decimal place forward, But the maximum number reaches the final bit; Final sort already at the end.”, Once per traverse, Insideloop You can traverse one element less.. But we can infer from this. The last oneswap Ofj andj+1,
j Elements after( Barringj) It's all sorted..
void bubble2(vector<int>& arr){ int n = arr.size()-1; for(int
i=0;i<arr.size()-1;i++){ int upto = 0; for(int j=0;j<n;j++){ //j Less than last bit of indefinite sort
if(arr[j]>arr[j+1]){ upto = j; //upto=j Last bit of variable size, j+1 Sorting completed（ The last oneif）
swap(arr[j],arr[j+1]); } } n=upto; if(n==0) break; } }
optimization3: It can cycle in two directions, Forward loop moves the largest element to the end, Reverse loop moves the smallest element to the front, This optimized bubble sorting, Called cocktail order(Cocktail Sort)
void bubble4(vector<int>& arr){ int beg = 0; int end = arr.size()-1;
while(beg<end){ int nbeg = beg, nend = end; // Forward cycle for(int i=beg;i<end;i++){
if(arr[i]>arr[i+1]){ nend=i; swap(arr[i],arr[i+1]); } } if(nend==end) break;
end = nend; // Reverse circulation for(int i=end; i>beg;i--){ if(arr[i]<arr[i-1]){ nbeg=i;
swap(arr[i], arr[i-1]); } } if(nbeg==beg) break; beg = nbeg; } }

3 Analysis

3.1 Stability

It is greater than or equal to that used in comparison.( Less than or equal to) Or greater than( less than)

arr[i]>arr[i+1] --> Stable

arr[i]>=arr[i+1] --> Instable

3.2 time

Reverse sort is the worst case,O(n^2)

3.3 space

NeedO(1) To finishswap etc.

Quick sort (Quicksort)

1 algorithm

Make use of divide & conquer Thought.

Select any number in the sequence, Then, we divide the sequence into two subsequences, one is larger than the number and the other is smaller than the number.. Repeat the above steps to complete the sorting.

2 Code
int partition1(vector<int>& arr, int beg, int end){ int pivot = arr[beg]; int
l=beg+1, r=end; while(l<=r){ if(arr[l]<pivot) l++; else if(arr[r]>pivot) r--;
else if(arr[l]>=pivot && arr[r]<=pivot){ swap(arr[l++], arr[r--]); } }
swap(arr[r], arr[beg]); return r; } int partition2(vector<int>& arr, int beg,
int end){ int pivot = arr[beg]; int index = beg+1; for(int i=index;i<=end;i++){
if(arr[i]<pivot){ swap(arr[i], arr[index++]); } } swap(arr[beg],arr[index-1]);
return index-1; } void quick(vector<int>& arr, int beg, int end){ if(beg<end){
int pivot = partition1(arr,beg,end); // int pivot = partition2(arr,beg,end);
quick(arr, beg, pivot-1); quick(arr, pivot+1, end); } }
optimization1 Switch to insert sort

Because fast sorting can also call itself recursively in small arrays. For small arrays, Insert sort has better performance than quick sort, So you can switch to insert sort in a small array.

optimization2 Three numbers taking

In the best case, you can take the median of the array as the segmentation element every time. But it's expensive to calculate the median.. People found that 3 Elements with the middle size are the best for segmentation.

optimization3 Three way segmentation

For arrays with a large number of repeating elements, The array can be divided into three parts, Corresponding to less than, Equal to and greater than segmentation elements.

After waitingreview Post it whencode bar～ It's brain burning to write this～

3 Analysis

3.1 Stability

3.2 time

The best situation ispivot They are all midpoint. -- O(n log n) ( The same is true on average, So some fast sorting algorithms will randomly disrupt the sequence at the beginning.)

The worst case scenario is an ordered sequence. -- O(n^2)

3.3 space

Although there is no other data structure, But notO(1) Oh～ becauserecursion Need tostack frames Rebuild insidearray. Above mecode NeedO(n)
extra space, Best words, Can achieveO(log n)

4 deformation

LeetCode - Top K Frequent Elements
<https://blog.csdn.net/real_lisa/article/details/82650870>

Insertion sort (Insertion Sort)

1 algorithm

Maintain an ordered sequence, Simultaneously traversing the sequence to be sorted, Find the right place in an ordered sequence, Insertion element.

2 Code
void insertion(vector<int>& arr){ for(int i=1;i<arr.size();i++){ int temp=i;
for(int j=i-1;j>=0;j--){ if(arr[temp]<arr[j]) swap(arr[temp--],arr[j]); } } }
optimization1 When the current element is found, the location of the insertion is, Re insertion
void insertion1(vector<int>& arr){ for(int i=1;i<arr.size();i++){ int
temp=arr[i]; int j=i-1; for(;j>=0 && temp<arr[j];j--){ arr[j+1] = arr[j]; }
arr[j+1] = temp; } }
3 Analysis

3.1 Stability

arr[temp]<arr[j], Only when it's less thanswap, Keep the previous relative position when equal to, So it's stable..

3.2 time

The best case is forward order -- O(n)

The worst is reverse order, You need to compare the number of elements in the completed sequence each time you insert -- O(n^2)

3.3 space

O(1) - As abovecode -> temp

Shell Sort (Shell Sort)

1 algorithm

An improved version of simple interpolation, Choose to insert distant elements first.

Select a gap, Divide the sequence into many subsequences and sort them by insertion. Reduce spacing and repeat insertion sorting, Until the gap drops to1 Completion sort.

2 Code
// Just put theinsert function Ofgap=1 Change to variablegap Just go void shellInsert(vector<int>& arr, int
beg, int gap){ for(int i=beg+gap;i<arr.size();i+=gap){ int temp=arr[i]; int
j=i-gap; for(;j>=0 && temp<arr[j];j-=gap){ arr[j+gap] = arr[j]; } arr[j+gap] =
temp; } } void shell(vector<int>& arr){ int gap = arr.size()/2; while(gap>0){
int beg=gap-1; while(beg>=0){ shellInsert(arr, beg, gap); beg--; } gap = gap/2;
} }
3 Analysis

3.1 Stability

For the same two numbers, The order of the groups may change because they are in different groups.

3.2 time

Time complexity and increment of hill sorting( Namely, stepgap) Selection of. for example, When increment is1 Time, Hill sort degenerates into direct insert sort, The time complexity isO(N²), andHibbard The time complexity of incremental Hill sorting isO(N3/2).

3.3 space

O(1) - As abovecode -> temp

3.4 Compare other algorithms

Whengap Maximum time, Amount tobubble sort; Whengap=1 Time, Equivalent toinsertion sort.

Selection sort (Selection Sort)

1 algorithm

Maintain an ordered sequence, Simultaneously traversing the sequence to be sorted, Usually find the smallest element to insert into the ordered sequence. Repeat until there are no remaining elements in the sequence to be sorted.

2 Code
void select(vector<int>& arr){ int s = arr.size(); for(int i=0;i<s;i++){ int m
= arr[i]; int index = i; for(int j=i+1;j<s;j++){ if(arr[j]<m){ m = arr[j];
index = j; } } swap(arr[i], arr[index]); } }
3 Analysis

3.1 Stability

arr[j]<m - The same element after can only be the same element beforeswap Later talentswap, This keeps the original relative position.

3.2 time

Good or badO(n^2), Because every time you select the minimum value, you need to traverse all the remaining elements..

3.3 space

O(1)

Heap sort (Heapsort)

1 algorithm

Understand push(Heap)

2 Code

3 Analysis

3.1 Stability

3.2 time

3.3 space

Merge sort (Mergesort)

1 algorithm

Make use of divde & conquer Thinking mode of, Sometimes called merge sort.

Continue to decompose the sequence into subsequences until only0 or1 position. Then the subsequences are continuously merged by size. Finally, the length of the original sequence is restored..

2 Code
vector<int> merge(vector<int> a, vector<int> b){ vector<int> res; int ba = 0;
int bb = 0; while(ba<a.size() && bb<b.size()){ if(a[ba]<=b[bb]){
res.push_back(a[ba++]); } else{ res.push_back(b[bb++]); } } if(ba==a.size()){
while(bb<b.size()) res.push_back(b[bb++]); }else if(bb==b.size()){
while(ba<a.size()) res.push_back(a[ba++]); } return res; } vector<int>
mergeSort(vector<int> arr){ int s = arr.size(); if(s<2) return arr; int mid =
s/2; vector<int> front(arr.begin(), arr.begin()+mid); vector<int>
back(arr.begin()+mid, arr.end()); return merge(mergeSort(front),
mergeSort(back)); }
3 Analysis

3.1 Stability

a[ba]<=b[bb] -- When the elements are equal, the front and back positions of the elements are not changed. So the merging order is stable..

3.2 time

Divide the subsequence into half of the parent sequence every time, thereforeO(n log n)

3.3 space

Need additional space to store subsequences -- O(n)

Counting sort (Counting Sort)

1 algorithm

As the name implies, count the number of occurrences of each number in the sequence to be sorted. The process of filling in data structure is actually the process of sorting.. Finally, we can cover the original sequence according to the statistical results..

2 Code
void count(vector<int>& arr, int range){ vector<int> temp(range+1, 0); for(int
i=0;i<arr.size();i++){ temp[arr[i]]++; } int c=0; for(int
i=0;i<arr.size();i++){ while(temp[c]==0) c++; arr[i] = c; temp[c]--; } }
3 Analysis

Sort not based on comparison, But the precondition is to know the range of sorting elements.

3.1 Stability

stable -
https://stackoverflow.com/questions/2572195/how-is-counting-sort-a-stable-sort
<https://stackoverflow.com/questions/2572195/how-is-counting-sort-a-stable-sort>

3.2 time

O(n+k), k byrange

3.3 space

O(n+k), Used to store count results

Bucket sorting (Bucket Sort)

1 algorithm

Sort by count, Added function mapping(hashmap), Put elements in different buckets for sorting.

For instance, Need sorting1-100 Figures. If count sort, You need one100 Ofvector To deposit; One can be used for bucket sorting10 Ofvector To deposit, Each element enters( element/10)index Ofvector.

2 Code

Because different data requires different function mapping, No code here.

3 Analysis

3.1 Stability

3.2 time

Best - O(n+k)

Worst - O(n^2)

3.3 space

O(n*k)

1 algorithm

The cardinality is sorted first according to the low order, Then collect; Then sort by high order, Then collect; By analogy, Up to the highest level. Sometimes some properties are prioritized, Sort by low priority first, Sort by high priority. The last order is high priority first, High priority same low priority high priority first.

2 Code

It's personal
// LSD Radix Sort var counter = []; function radixSort(arr, maxDigit) { var
mod = 10; var dev = 1; 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; } } } } return arr; }
3 Analysis

3.1 Stability

3.2 time

Cardinality sorting is based on sorting separately, Collect separately, So it's stable.. But the performance of Radix sorting is slightly worse than that of bucket sorting. Every bucket allocation of keywords requiresO(n) Time complexity of, And it is necessary to get a new keyword sequence after allocation.O(n) Time complexity of. If the data to be arranged can be divided intod Key words, The time complexity of Radix sorting will beO(d*2n)
, Of coursed Far less thann, So it's basically linear..

3.3 space

The spatial complexity of Radix sorting isO(n+k), amongk Is the number of barrels. generally speakingn>>k, So the extra space needs to be aboutn Around.

Reference:

https://www.cnblogs.com/onepixel/articles/7674659.html
<https://www.cnblogs.com/onepixel/articles/7674659.html>

https://blog.csdn.net/hguisu/article/details/7776068
<https://blog.csdn.net/hguisu/article/details/7776068>

https://github.com/francistao/LearningNotes/blob/master/Part3/Algorithm/Sort/ Interview%2010%20 Summary of large sorting algorithm.md