Stable sorting :

Bubble sorting , Insert sort , Merge sort

Unstable sorting :

Select sort , Shell Sort , Heap sort , Quick sort

1, Bubble sorting

Bubble sort is to move small elements forward or to move large elements back. , A comparison is a comparison of two adjacent elements , Exchange also occurs between these two elements .( Similar to bubble floating process )

The dynamic diagram is as follows :

step :

1, Compare adjacent elements , If the first is bigger than the second , Then exchange

2, Repeat step for each pair of adjacent elements 1 operation , Filter out maximum elements

3, Repeat step for all elements 1,2( Except the last element , It's already the biggest )

Sample code :
void bubbleSort(std::vector<int> &vecArry) { for (int i = 0;i <
vecArry.size();i++) { for (int j = 0;j < vecArry.size() - i -1;j++) { if
(vecArry[j] > vecArry[j+1]) { int nTemp = vecArry[j]; vecArry[j] =
vecArry[j+1]; vecArry[j+1] = nTemp; } } } } // Optimize code void
bubbleSort(std::vector<int> &vecArry) { bool bSwitch = false; for (int i = 0;i
< vecArry.size();i++) { for (int j = 0;j < vecArry.size() - i -1;j++) { if
(vecArry[j] > vecArry[j+1]) { bSwitch = true; int nTemp = vecArry[j];
vecArry[j] = vecArry[j+1]; vecArry[j+1] = nTemp; } } if (!bSwitch) { return; }
} }
2, Select sort

  The smallest value was never found in the sort sequence ( maximum ), Place at the end of a sorted sequence

The dynamic diagram is as follows :

  step :

1, Minimum sort queue found ( maximum ) element , Stored at the beginning of the sequence

2, Minimum found in unordered sequence ( maximum ) element , Place at the end of a sorted sequence

3, repeat 1,2 step

Sample code :
void selectSort(std::vector<int> &vecArry) { for(int i = 0; i <
vecArry.size(); ++i) { int nIndex = i; for (int j = i+1; j <
vecArry.size();++j) { if (vecArry[j] < vecArry[nIndex]) { nIndex = j; } } int
nTemp = vecArry[i]; vecArry[i] = vecArry[nIndex]; vecArry[nIndex] = nTemp; } }
3, Insert sort

Use the first element of an unordered sequence , Start the comparison from the end of the sorted sequence to the start position , That is, the inserted element is compared with the largest sorted element , Always find the element position smaller than it and insert it .

The dynamic diagram is as follows :

step :

 1, Set the first element to sorted

2, Take out the next element , Compare forward at the end of a sorted sequence

3, If this element ( Sorted ) Greater than new element ( Element to be inserted ), Move the element to the next position

4, Repeat step 3, Found sorted element less than or equal to new element

5, Insert new element into sorted sequence

6, repeat 2~5

Sample code :
void insertSort(std::vector<int> &vecArry) { for (auto i = 1; i <
vecArry.size(); ++i) { int m = vecArry[i]; for (int n = i-1; n >=0; --n) { if
(m < vecArry[n]) { int nTemp = vecArry[n + 1]; vecArry[n+1] = vecArry[n];
vecArry[n] = nTemp; } } } }
4, Quick sort

Base on one element , Move elements smaller than the cardinality to the front of the cardinality , Elements greater than cardinality are moved after cardinality , Repeat the above steps for the left and right intervals , Know that there is only one number in the interval

The dynamic diagram is as follows :

step :

1, Select a number as the base

2, Move elements smaller than the cardinality to the front of the cardinality

3, Move elements larger than cardinality behind cardinality  

4, Repeat the left and right intervals of the cardinality 1~3 step , Until the interval has only one number

Sample code :
void quickSort(std::vector<int> &vecArry,int nLeft,int nRight) { if (nLeft >=
nRight) { return; } int nLow = nLeft; int nHight = nRight; int nBase =
vecArry[nLeft]; while (nLow < nHight) { while( nLow < nHight && nBase<
vecArry[nHight]) { nHight--; } if (nLow < nHight) { vecArry[nLow++] =
vecArry[nHight]; } while (nLow < nHight && nBase > vecArry[nLow]) { nLow++; }
if (nLow < nHight) { vecArry[nHight--] = vecArry[nLow]; } } vecArry[nLow++] =
nBase; quickSort(vecArry,nLeft,nLow-1); quickSort(vecArry,nHight+1,nRight); }
5, Shell Sort

Hill sort can be understood as an optimized version of insert sort . Hill sorting is to divide any interval into N Ordered elements , At first it could be N=n/2, Then let N=N/2, Give Way N Keep shrinking , When N=1, Time , At this time, the sequence interval is 1 Orderly .

The dynamic diagram is as follows :

step :

1, Initial interval N= Array length /2

2, Pair interval is N Insert sort by grouping , Until orderly

3, narrow N value ,N=N/2;

4, repeat 2,3 step , Until interval N=1

Sample code :
void shellSortCore(std::vector<int> &vecArry) { int gap = vecArry.size()/2;
while(gap) { for (int i = gap; i < vecArry.size(); i++)// How many groups { int m =
vecArry[i]; for (int n = i - gap; n >=0; --n) { if (m < vecArry[n]) { int nTemp
= vecArry[n + gap]; vecArry[n+gap] = vecArry[n]; vecArry[n] = nTemp; } } }
gap/=2; } }
6, Heap sort

Heap can be divided into large root heap and small root heap , Heap sorting is a sort designed according to the data structure of the heap .

Large top reactor :arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  

Small top pile :arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]  

The dynamic diagram is as follows :

step :

1, Build the sequence to be sorted into a large root heap , This heap is the initial unordered heap

2, Swap the top element with the last element , Now get a new N-1 Unordered heap and ordered sequence

3, repeat 2 Until the unordered heap is 1, At this time, the ordered sequence is N-1

Sample code :
int nLen = 0; void swap(std::vector<int> &vecArry,int nSrc, int nDes) { int
nTemp = vecArry[nSrc]; vecArry[nSrc] = vecArry[nDes]; vecArry[nDes] = nTemp; }
void funcBuild(std::vector<int> &vecArry, int n) { int left = 2 * n + 1; int
right = 2 * n + 2; int largest = n; if (left < nLen && vecArry[left] <
vecArry[largest]) { largest = left; } if (right < nLen && vecArry[right] <
vecArry[largest]) { largest = right; } if (largest != n) { swap(vecArry, n,
largest); funcBuild(vecArry, largest); } } void heapify_sort(std::vector<int>
&vecArry) { nLen = vecArry.size(); for (int i = nLen/2-1; i >= 0; i--) {
funcBuild(vecArry,i); } for (int j = nLen-1;j >= 0; j--) { swap(vecArry,0,j);
nLen--; funcBuild(vecArry,0); } }
7, Count sort

The occurrence times of the sequence elements to be sorted are stored in the new array space as the key value

The dynamic diagram is as follows :

step :

1, Find the sequence to be sorted A Maximum element Max

2, Open up a new Max+1 Array of B, The initial value is 0

3, Will sequence A Element values in as an array B Indexes x,A The number of occurrences of elements in the array B Index is x Value of

4, Open up a length and A Arrays of the same sequence size C

5, Loop out array B Value stored in C in , Take out one B value --

Sample code :
void countSort(std::vector<int> &vecArry) { int nMax = 0; for (auto &item :
vecArry) { if (nMax < item) { nMax = item; } } std::vector<int>
vecCount(nMax+1,0); for (int i = 0; i < vecArry.size();i++) {
vecCount[vecArry[i]]++; } std::vector<int> vecResult(vecArry.size(),0); int
nIndex = 0; for (int j = 0; j< vecCount.size();j++) { while(vecCount.at(j) > 0)
{ vecResult[nIndex++] = j; vecCount[j]--; } } }
8, Merge sort

Merging and sorting adopts the idea of division and rule , Divide the sequence to be sorted into N Subsequence , After subsequence sorting , Merge two subsequences to sort

The dynamic diagram is as follows :

step :

1, Set the length to N Sequence division of N/2 Subsequence

2, Merge and sort subsequences

3, Merging ordered subsequences into one subsequence

Sample code :
void merge(std::vector<int> &vecArry,int nLeft, int nMid, int nRight) { int
nLen = nRight-nLeft+1; int nTempLeft = nLeft, nTempRight = nMid+1; int nIndex =
0; std::vector<int> vecTemp(nLen,0); while (nTempLeft <= nMid && nTempRight <=
nRight) { vecTemp[nIndex++] = vecArry[nTempLeft] <= vecArry[nTempRight] ?
vecArry[nTempLeft++] : vecArry[nTempRight++]; } while(nTempLeft <= nMid) {
vecTemp[nIndex++] = vecArry[nTempLeft++]; } while (nTempRight <= nRight) {
vecTemp[nIndex++] = vecArry[nTempRight++]; } for (int i = 0; i < nLen; i++) {
vecArry[nLeft+i] = vecTemp[i]; } } void mergeSort(std::vector<int> &vecArry,
int nLeft, int nRight) { if (nLeft == nRight) { return; } int nMid = (nLeft +
nRight)/2; mergeSort(vecArry,nLeft,nMid); mergeSort(vecArry,nMid+1,nRight);
merge(vecArry,nLeft,nMid,nRight); }
9, Bucket sorting

Bucket sorting is to put arrays into a limited number of buckets . Each bucket is sorted again . Bucket sorting is an inductive result of pigeon nest sorting

The dynamic diagram is as follows :

step :

1, Set a certain number of empty buckets

2, Traverse the sequence to be sorted , Put each element into the corresponding bucket

3, Sort each bucket that is not empty

4, Remove elements from an empty bucket

Sample code :
void bucketSort2(std::vector<int> &vecArry) { int nMax = vecArry[0]; for (auto
&value : vecArry) { if (value > nMax) { nMax = value; } } std::vector<int>
vecTemp(nMax+1,0); for (auto &value : vecArry) { vecTemp[value]++; } int nIndex
= 0; for (int i = 0; i < vecTemp.size(); ++i) { while (vecTemp[i] > 0) {
vecArry[nIndex++] = i; vecTemp[i]--; } } } void bucketSort(std::vector<int>
&vecArry) { int nMax = vecArry.at(0); int nMin = vecArry.at(0); for (auto &data
: vecArry) { if (data > nMax) { nMax = data; } if (data < nMin) { nMin = data;
} } int nValue = nMax - nMin;// Difference std::vector<std::vector<int>> vecTemp; int
nLen = vecArry.size();// Sequence length vecTemp.resize(nLen); for (auto &value : vecArry)
{ //nLen-1 Interval // Set the difference to nValue Divide equally nLen-1 On two intervals //value-min Is the difference between the current element and the minimum value
//nIndex Just for (value - nMin)/nValue/(nLen-1) int nIndex = (value -
nMin)/nValue/(nLen-1); vecTemp[nIndex].push_back(value); } for (auto &data :
vecTemp) { insertSort(data); } int nIndex= 0; for (auto &data : vecTemp) {
for(auto &value : data) { vecArry[nIndex++] = value; } } }
10, Cardinality sort

Cardinality sorting is sorting by low order first , Then collect , Then sort by high order , Re collection , and so on , Up to the top .

The dynamic diagram is as follows :

step :

1, Get the maximum number in the sequence to be sorted , And get the number of bits

2, The lower order of each element in the sequence to be sorted is the same and placed in one radix array

3, From multiple radix Array fetch element , Form a new sequence to be sorted

4, Repeat this 2,3( step 2 From low to high )

Sample code :
void radixSort(std::vector<int> &vecArry) // Cardinality sort { int nLen = vecArry.size();
int nMax = vecArry.at(0); for (auto &value : vecArry) { if (nMax < value) {
nMax = value; } } int nCount = 0; while(nMax) { nMax/=10; nCount++; } int radix
= 1; std::vector<std::vector<int>> vecTemp(10); for (int i = 0; i < nCount;
i++) { vecTemp.clear(); vecTemp.resize(10); for(auto &value : vecArry) { int
nIndex = (value/radix)%10; vecTemp.at(nIndex).push_back(value); } int nIndex =
0; for (auto &value : vecTemp) { for (auto &data : value) { vecArry[nIndex++] =
data; } } radix *= 10; } }

Technology
©2019-2020 Toolsou All rights reserved,
Android Using wechat in H5 Payment result refresh during payment shock !!C++ Can make a sound ! Basic operation of single linked list C Language explanation Java Implement an epidemic number management system 2021 year 11 World programming language ranking linux upper mysql Invalid command _linux lower mysql The command is useless Java project : Campus dormitory management system (java+jsp+javaweb+mysql+ajax) Wechat applet development project directory linux ubuntu Which version ,Ubuntu Which version is the best ?python Code painting cherry blossoms - How to use Python Draw a beautiful cherry blossom