Basic concepts

Internal and external sorting

Internal sorting here refers to the sort method that only uses computer memory and does not use external memory . Relative , External sorting is a sort method that uses both computer memory and external memory at the same time . This article will only discuss internal sorting .

classification

Comparison and non comparison sorting

compare
In this case, we need to compare the size of two elements ( around ) Can be sorted . Is there a sort algorithm that doesn't need to be compared ? There is , But not much . There are three common ones ： Count sort , Bucket sorting , Cardinal sort . They use statistical methods to avoid comparison , You can see these algorithms in detail later .

transformation

Only transpose the position between two elements at a time .

insert

The traversed elements are put into 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 the 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 illustrates the above definition very vividly ：

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

(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 , Compares the size of the current element with the size of the next element , If it doesn't match the order , change of position . After the end of the last element , And go through it from scratch , Until the sorting is complete .

analyse ： Every time the traversal is completed , Forward the decimal by one digit , But the maximum number reaches the final bit ; The end is already the final sort .

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 } } }
optimization 1: Every time I go through it , See if you've finished sorting ahead of time ( use hasSorted). So it is , Early end .
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]); } } } }
optimization 2:
according to “ analyse ： Every time the traversal is completed , Forward the decimal by one digit , But the maximum number reaches the final bit ; The end is already the final sort .”, Every time the traversal is completed , Inside loop You can traverse one element less . But in fact, we can infer from this , the last one swap Of j and j+1,
j Elements after ( barring j) 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 the last bit of the indefinite sort
if(arr[j]>arr[j+1]){ upto = j; //upto=j Last bit of indefinite size , j+1 Sort completed （ the last one if）
swap(arr[j],arr[j+1]); } } n=upto; if(n==0) break; } }
optimization 3: There can be a two-way cycle , Forward loop moves the largest element to the end , The reverse loop moves the smallest element to the front , This optimized bubble sort , It's called cocktail sorting (Cocktail Sort)
void bubble4(vector<int>& arr){ int beg = 0; int end = arr.size()-1;
while(beg<end){ int nbeg = beg, nend = end; // Forward circulation 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

Decide to use greater than or equal to when comparing ( 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 sorting is the worst case ,O(n^2)

3.3 space

need O(1) To complete swap etc.

Quick sort (Quicksort)

1 algorithm

Used divide & conquer The thought of .

Select any number in the sequence , The sequence is then divided into two subsequences larger than the number and 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); } }
optimization 1 Switch to insert sort

Because quicksort calls itself recursively in small arrays , For small arrays , Insert sort performs better than quick sort , So you can switch to insert sort in a small array .

optimization 2 Take the middle of three numbers

The best case is to take the median of the array every time , It's expensive to calculate, but it's expensive . People found that 3 Elements with the middle size as the best segmentation element .

optimization 3 Three way segmentation

For arrays with a large number of duplicate elements , You can split an array into three parts , Respectively corresponding to less than , Equal to and greater than the split element .

After waiting review I'll stick it when I get there code bar ～ It's too much to write about ～

3 analysis

3.1 Stability

3.2 time

In the best case pivot It's all the midpoint -- O(n log n) ( The same is true on average , So some algorithms will randomly scramble the sequence at the beginning )

In the worst case, it's an ordered sequence -- O(n^2)

3.3 space

Although no other data structure was used , But it's not O(1) Oh ～ because recursion Need to be in stack frames It's rebuilt inside array. It's on me code need O(n)
extra space, The best , Can be achieved O(log n)

4 deformation

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

Insert sort (Insertion Sort)

1 algorithm

Maintain an ordered sequence , Simultaneously traverses the sequence to be sorted , Find the right place in an ordered sequence , Insert 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]); } } }
optimization 1 After finding the location of the current element to insert , Re insert
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 is less than swap, Keep the previous relative position when equal to , So it's stable .

3.2 time

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

The worst is reverse sorting , Each insert needs to compare the number of elements in the completed sequence -- O(n^2)

3.3 space

O(1) - As above code -> temp

Shell Sort (Shell Sort)

1 algorithm

Improved version of simple insertion sequence , Select to insert elements that are far away first .

Select a gap , The sequence is divided into many subsequences and sorted by insertion . Reduce spacing and repeat insert sort , Until the gap is reduced to 1 Complete sorting .

2 code
// Just put it before insert function Of gap=1 Change to variable gap Just fine 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 , It is possible that their order may change because they are divided into different groups .

3.2 time

Time complexity and increment of Hill sort ( Namely , step gap) The selection of . for example , When the increment is 1 Time , Hill sort degenerates into direct insertion sort , The time complexity is O(N²), and Hibbard The time complexity of incremental Hill sort is 0 O(N3/2).

3.3 space

O(1) - As above code -> temp

3.4 Compare with other algorithms

When gap Maximum hour , amount to bubble sort; When gap=1 Time , It's equivalent to insertion sort.

Select sort (Selection Sort)

1 algorithm

Maintain an ordered sequence , Simultaneously traverses the sequence to be sorted , Usually find the smallest element to insert into an ordered sequence . Repeat until the sequence to be sorted has no remaining elements .

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 that appears after can only be the same element before swap Later ability swap, This keeps the original relative position .

3.2 time

Both good and bad need it O(n^2), Because every time you select the minimum, you need to traverse all the remaining elements .

3.3 space

O(1)

Heap sort (Heapsort)

1 algorithm

Understanding push (Heap)

2 code

3 analysis

3.1 Stability

3.2 time

3.3 space

Merge sort (Mergesort)

1 algorithm

Used divde & conquer The way of thinking , Sometimes called merge sort .

The sequence is decomposed into subsequences until only subsequences are left 0 or 1 position . Then the subsequences are merged by size , Finally, the length of the original sequence was 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 merge sort is stable .

3.2 time

Each time, the subsequence is divided into half of the parent sequence , therefore O(n log n)

3.3 space

Additional space is needed to store subsequences -- O(n)

Count sort (Counting Sort)

1 algorithm

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

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

Not sort based on comparison , But the premise is that you know the range of the sort 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 by range

3.3 space

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

Bucket sorting (Bucket Sort)

1 algorithm

Sort based on count , Added function mapping (hashmap), It is easy to sort the elements into different buckets .

for instance , Sorting requires 1-100 The number of . If it is count sort , You need one 100 Of vector To deposit ; Bucket sorting can use a 10 Of vector To deposit , Each element enters ( element /10)index Of vector.

2 code

Because different data have different requirements for function mapping , There's 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

Cardinal sort is to sort by low order first , Then collect ; And then sort by high order , And then collect it ; And so on , Up to the top . Sometimes some attributes are prioritized , Sort low priority first , Then sort by high priority . The last order is high priority, high priority , High priority same low priority high priority first .

2 code

Post someone else's
// 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

Cardinal sort is based on separate sort , Collect separately , So it's stable . However, the performance of cardinal sort is slightly worse than that of bucket sort , Every bucket allocation of keywords is required O(n) Time complexity of , Moreover, it is necessary to obtain a new keyword sequence after allocation O(n) Time complexity of . If the data to be arranged can be divided into d Keywords , Then the time complexity of cardinality sort will be O(d*2n)
, of course d Far less than n, So it's basically linear .

3.3 space

The spatial complexity of cardinality sorting is O(n+k), among k Is the number of barrels . generally speaking n>>k, So the extra space is about n About one .

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/ In the interview %2010%20 Summary of large sorting algorithm .md