## Make complaints about ten classic sorting algorithms (mind map + dynamic demo + code + C/C++/Python + fatal Tucao).

I'm Guan Xiaoliang 2020-11-13 05:30:23
make complaints classic sorting algorithms

# Statement

1） This article collates the selfless contribution materials of Daniel and experts from the Internet , Please refer to the references for specific references .
2） This article is for academic exchange only , Non commercial . If some part of it accidentally infringes on our interests , Looking forward to the sea culvert , And contact blogger to delete .
3） Bloggers lack of talent and knowledge , If there is anything wrong in the text , Please point out , Common progress , thank you .
4） This is the first version , If there is an error , It needs to be amended, added and deleted . I hope you can give me some advice . We all share a little bit , Contribute to the promotion of scientific research in China .

## 0、 Write it at the front

Recently, I finally learned the sorting algorithm , Sort , Is to make a string of records , According to the size of one or some of the keywords , An operation arranged in ascending or descending order . Sorting algorithm , How to arrange records according to requirements .

Why sorting algorithm is paid more attention in many fields ？

Mainly an excellent algorithm can save a lot of resources , Especially in the processing of large amount of data .

Sorting algorithm can be divided into internal sorting and external sorting ：

• Internal sort is the sorting of data records in memory ,
• The external sort is because the sort is very large , Cannot hold all sort records at once , You need to access external storage during the sort process .

There are several classical sorting algorithms （ Mind mapping ）：

Click to view a larger image ！ The main nature must be ：

• Data objects

Data objects
Array or linked list , perhaps both.

• stability

stability
Assume in the sequence of records to be sorted , There are multiple records with the same keyword , If sorted , The relative order of these records remains the same , In the original sequence ,`r[i]=r[j]`, And `r[i]` stay `r[j]` Before , In the sorted sequence ,`r[i]` Still in `r[j]` Before , This sort algorithm is called Stable Of ; Otherwise it is called unstable Of .

• Time complexity

Time complexity
time complexity , Also known as time complexity , Is a function that qualitatively describes the running time of the algorithm .

• Spatial complexity

Spatial complexity
Space complexity is a measure of the amount of storage space temporarily occupied by an algorithm during operation .

Click to view a larger image ！  ## 1、 Bubble sort

describe ：

Repeatedly visit the element columns to sort , Compare two adjacent elements in turn , If the order is wrong , Just exchange them .

Dynamic diagram demonstration ： • When is the fastest ？
When the input data is already in positive order （？？？ It's still sorted ？ It's all in order , What else can I do for you ）.
• When is the slowest ？
When the input data is in reverse order （ It's a dead eye ？ Just output the data in reverse order , Are you free to use it ）. Code ：

``````#python
def bubbleSort(arr):
for i in range(1, len(arr)):
for j in range(0, len(arr)-i):
if arr[j] > arr[j+1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
``````
``````//C
void swap(int *a,int *b){

int temp = *a;
*a = *b;
*b = temp;
}
void bubble_sort(int arr[], int len){

int i, j, temp;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1]) {

swap(&arr[j], &arr[j + 1]);
}
}
``````
``````//C++
template<typename T>
void bubble_sort(T arr[], int len) {

int i, j;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
``````

Write a `Swap` Exchange and `flag` Jump out early , Plus the first level reverse cycle , Yes. .

Reference resources MOOC Data structure of Zhejiang University

``````// C
void Swap(ElementType *a, ElementType *b){

ElementType t = *a; *a = *b; *b = t;
}
void BubbleSort(ElementType A[], int N){

int P, i;
int flag;
for (P = N - 1; P >= 0; P--){

flag = 0;
for (i = 0; i < P; i++){

if (A[i] > A[i + 1]){

Swap(&A[i], &A[i + 1]);
flag = 1;
}
}
if (flag = 0) break;
}
}
`````` ## 2、 Selection sort

describe ：

Select the smallest data element from the data elements to be sorted for the first time （ Or maximum ） An element of , Store at the beginning of the sequence , And then find the smallest of the remaining unsorted elements （ Big ） Elements , Then put it at the end of the sorted sequence . And so on , Until the number of all data elements to be sorted is zero .

Dynamic diagram demonstration ： （ It's actually playing cards , Catching cards , Look at cards , Horse brand ） Code ：

``````#python
def selectionSort(arr):
for i in range(len(arr) - 1):
# Record the decimal index
minIndex = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[minIndex]:
minIndex = j
# i When not the minimum , take i Exchange with the least number
if i != minIndex:
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr
``````
``````//C
void swap(int *a,int *b){

int temp = *a;
*a = *b;
*b = temp;
}
void selection_sort(int arr[], int len){

int i,j;
for (i = 0 ; i < len - 1 ; i++){

int min = i;
// Traversing unsorted elements
for (j = i + 1; j < len; j++){

if (arr[j] < arr[min]) // Current minimum found
min = j; // Record minimum
swap(&arr[min], &arr[i]); // In exchange
}
}
}
``````
``````//C++
template<typename T>
void selection_sort(std::vector<T>& arr) {

for (int i = 0; i < arr.size() - 1; i++) {

int min = i;
for (int j = i + 1; j < arr.size(); j++){

if (arr[j] < arr[min])
min = j;
std::swap(arr[i], arr[min]);
}
}
}
``````

Reference resources MOOC Data structure of Zhejiang University

``````// C
void Swap(ElementType *a, ElementType *b){

ElementType t = *a; *a = *b; *b = t;
}
void SimpleSelectionSort(ElementType A[], int N){

int i, j, min;
for (i = 0; i < N-1; i++){

min = i;
for (j = i + 1; j < N; j++){

if (A[i] < A[min])
min = j;
Swap(&A[i], &A[min]);
}
}
}
`````` ## 3、 Insertion sort

describe ：

By building an ordered sequence , For unsorted data , Scan backward and forward in sorted series , Locate and insert .

Dynamic diagram demonstration ： （ slow , Really slow , It's not fake ） Code ：

``````#python
def insertionSort(arr):
for i in range(len(arr)):
preIndex = i-1
current = arr[i]
while preIndex >= 0 and arr[preIndex] > current:
arr[preIndex+1] = arr[preIndex]
preIndex-=1
arr[preIndex+1] = current
return arr
``````
``````//C
void insertion_sort(int arr[], int len){

int i,j,key;
for (i=1;i<len;i++){

key = arr[i];
j=i-1;
while((j>=0) && (arr[j]>key)) {

arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
``````
``````//C++
void insertion_sort(int arr[],int len){

for(int i=1;i<len;i++){

int key=arr[i];
int j=i-1;
while((j>=0) && (key<arr[j])){

arr[j+1]=arr[j];
j--;
}
arr[j+1]=key;
}
}
``````

Reference resources MOOC Data structure of Zhejiang University

``````void InsertionSort( ElementType A[], int N ){

int P, i;
ElementType Tmp;
for ( P=1; P<N; P++ ) {

Tmp = A[P];
for ( i=P; i>0 && A[i-1]>Tmp; i-- )
A[i] = A[i-1];
A[i] = Tmp;
}
}
`````` ## 4、 Shell Sort

describe ：

Group records by a certain increment of subscript , Sort each group using the direct insertion sort algorithm ; As the increments decrease , Each group contains more and more keywords , When the increment is reduced to 1 when , The whole document is just a group , The algorithm terminates .

Dynamic diagram demonstration ： Hill sort is improved based on insertion sort ,（ It's a lot faster after the reform , It used to be an old ox , Now it's a scooter ） Code ：

``````#python
def shellSort(arr):
import math
gap=1
while(gap < len(arr)/3):
gap = gap*3+1
while gap > 0:
for i in range(gap,len(arr)):
temp = arr[i]
j = i-gap
while j >=0 and arr[j] > temp:
arr[j+gap]=arr[j]
j-=gap
arr[j+gap] = temp
gap = math.floor(gap/3)
return arr
``````
``````//C
void shell_sort(int arr[], int len) {

int gap, i, j;
int temp;
for (gap = len >> 1; gap > 0; gap >>= 1){

for (i = gap; i < len; i++) {

temp = arr[i];
for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
arr[j + gap] = arr[j];
arr[j + gap] = temp;
}
}
}
``````
``````//C++
template<typename T>
void shell_sort(T array[], int length) {

int h = 1;
while (h < length / 3) {

h = 3 * h + 1;
}
while (h >= 1) {

for (int i = h; i < length; i++) {

for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {

std::swap(array[j], array[j - h]);
}
}
h = h / 3;
}
}
``````

Reference resources MOOC Data structure of Zhejiang University

``````void ShellSort( ElementType A[], int N ){

int Si, D, P, i;
ElementType Tmp;
/* Only a few increments are listed here */
int Sedgewick[] = {
929, 505, 209, 109, 41, 19, 5, 1, 0};
for ( Si=0; Sedgewick[Si]>=N; Si++ )
;
for ( D=Sedgewick[Si]; D>0; D=Sedgewick[++Si] ){

for ( P=D; P<N; P++ ){

Tmp = A[P];
for ( i=P; i>=D && A[i-D]>Tmp; i-=D )
A[i] = A[i-D];
A[i] = Tmp;
}
}
}
`````` ## 5、 Merge sort

describe ：

A typical application of divide and rule , Merges ordered subsequences , You get a perfectly ordered sequence ; So let's make each subsequence in order , Then make the subsequence segments in order .

Dynamic diagram demonstration ： It's about breaking it up , Separation , ha-ha Code ：

``````#python
def mergeSort(arr):
import math
if(len(arr)<2):
return arr
middle = math.floor(len(arr)/2)
left, right = arr[0:middle], arr[middle:]
return merge(mergeSort(left), mergeSort(right))
def merge(left,right):
result = []
while left and right:
if left <= right:
result.append(left.pop(0))
else:
result.append(right.pop(0));
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0));
return result
``````
``````//C
void merge_sort_recursive(int arr[], int reg[], int start, int end) {

if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {

int reg[len];
merge_sort_recursive(arr, reg, 0, len - 1);
}
``````
``````//C++
void Merge(vector<int> &Array, int front, int mid, int end) {

// preconditions:
// Array[front...mid] is sorted
// Array[mid+1 ... end] is sorted
// Copy Array[front ... mid] to LeftSubArray
// Copy Array[mid+1 ... end] to RightSubArray
vector<int> LeftSubArray(Array.begin() + front, Array.begin() + mid + 1);
vector<int> RightSubArray(Array.begin() + mid + 1, Array.begin() + end + 1);
int idxLeft = 0, idxRight = 0;
LeftSubArray.insert(LeftSubArray.end(), numeric_limits<int>::max());
RightSubArray.insert(RightSubArray.end(), numeric_limits<int>::max());
// Pick min of LeftSubArray[idxLeft] and RightSubArray[idxRight],
// and put into Array[i]
for (int i = front; i <= end; i++) {

if (LeftSubArray[idxLeft] < RightSubArray[idxRight]) {

Array[i] = LeftSubArray[idxLeft];
idxLeft++;
} else {

Array[i] = RightSubArray[idxRight];
idxRight++;
}
}
}
void MergeSort(vector<int> &Array, int front, int end) {

if (front >= end)
return;
int mid = (front + end) / 2;
MergeSort(Array, front, mid);
MergeSort(Array, mid + 1, end);
Merge(Array, front, mid, end);
}
``````

Reference resources MOOC Data structure of Zhejiang University

``````//C
/* L = Left start position , R = Right start position , RightEnd = Right end position */
void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd ){

/* Will be orderly A[L]~A[R-1] and A[R]~A[RightEnd] To merge into an ordered sequence */
int LeftEnd, NumElements, Tmp;
int i;
LeftEnd = R - 1; /* Left end position */
Tmp = L; /* Starting position of ordered sequence */
NumElements = RightEnd - L + 1;
while( L <= LeftEnd && R <= RightEnd ) {

if ( A[L] <= A[R] )
TmpA[Tmp++] = A[L++]; /* Copy left element to TmpA */
else
TmpA[Tmp++] = A[R++]; /* Copy right element to TmpA */
}
while( L <= LeftEnd )
TmpA[Tmp++] = A[L++]; /* Copy the rest on the left */
while( R <= RightEnd )
TmpA[Tmp++] = A[R++]; /* Copy directly the rest on the right */
for( i = 0; i < NumElements; i++, RightEnd -- )
A[RightEnd] = TmpA[RightEnd]; /* Will be orderly TmpA[] Copy back A[] */
}
void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd ){

/* Core recursive sort function */
int Center;
if ( L < RightEnd ) {

Center = (L+RightEnd) / 2;
Msort( A, TmpA, L, Center ); /* Recursively solve left */
Msort( A, TmpA, Center+1, RightEnd ); /* Recursively solve right */
Merge( A, TmpA, L, Center+1, RightEnd ); /* Merge two ordered sequences */
}
}
void MergeSort( ElementType A[], int N ){

/* Merge sort */
ElementType *TmpA;
TmpA = (ElementType *)malloc(N*sizeof(ElementType));
if ( TmpA != NULL ) {

Msort( A, TmpA, 0, N-1 );
free( TmpA );
}
else printf( " The space is insufficient " );
}
`````` ## 6、 Quick sort

describe ：

Separate the records to be arranged into two independent parts by one sorting , The keywords of one part of the records are smaller than those of the other part , Then the two parts of records can be sorted separately , To get the whole sequence in order .

Dynamic diagram demonstration ： Fast sorting is the most powerful feeling at present . Code ：

``````#python
def quickSort(arr, left=None, right=None):
left = 0 if not isinstance(left,(int, float)) else left
right = len(arr)-1 if not isinstance(right,(int, float)) else right
if left < right:
partitionIndex = partition(arr, left, right)
quickSort(arr, left, partitionIndex-1)
quickSort(arr, partitionIndex+1, right)
return arr
def partition(arr, left, right):
pivot = left
index = pivot+1
i = index
while i <= right:
if arr[i] < arr[pivot]:
swap(arr, i, index)
index+=1
i+=1
swap(arr,pivot,index-1)
return index-1
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
``````
``````//C
void swap(int *x, int *y) {

int t = *x;
*x = *y;
*y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {

if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {

while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right--;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else
left++;
if (left)
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len) {

quick_sort_recursive(arr, 0, len - 1);
}
``````
``````//C++
template <typename T>
void quick_sort_recursive(T arr[], int start, int end) {

if (start >= end)
return;
T mid = arr[end];
int left = start, right = end - 1;
// Search the whole range for elements smaller or larger than the hub element value , Then swap the left element with the right element
while (left < right) {

// Try to find an element larger than hub element on the left
while (arr[left] < mid && left < right)
left++;
// Try to find an element smaller than hub element on the right
while (arr[right] >= mid && left < right)
right--;
std::swap(arr[left], arr[right]); // Exchange elements
}
if (arr[left] >= arr[end])
std::swap(arr[left], arr[end]);
else
left++;
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
template <typename T>
void quick_sort(T arr[], int len) {

quick_sort_recursive(arr, 0, len - 1);
}
``````

Reference resources MOOC Data structure of Zhejiang University

``````//c
// Judge array size , If it's too small , Insert sort directly
void swap(int *a,int *b){

int temp = *a;
*a = *b;
*b = temp;
}
void InsertionSort( ElementType A[], int N ){

int P, i;
ElementType Tmp;
for ( P=1; P<N; P++ ) {

Tmp = A[P];
for ( i=P; i>0 && A[i-1]>Tmp; i-- )
A[i] = A[i-1];
A[i] = Tmp;
}
}
ElementType Median3(ElementType A[], int Left, int Right){

int Center=(Left+Right)/2;
if(A[Left]>A[center])
Swap(&A[Left], &A[center]);
if(A[Left]>A[Right])
Swap(&A[Left], &A[Right]);
if(A[center]>A[Right])
Swap(&A[Center], &A[Right]);
/* here A[Left]c=A[center]c=A[Right]*/
Swap(&A[center], &A[Right-1]); /* Benchmark Pivot Hide to the right */
/* Just think about it A[Left+1]…A[Right-2]*/
}
void Qsort(Elementrype A[], int Left, int Right){

/* Core recursive function */
int pivot, Cutoff, Low, High;
if(Cutoff<=Right-Left){
/* If there are enough sequence elements , Enter fast platoon */
Pivot=Median3(A, Left, Right); /* Select benchmark */
Low=Left;High=Right-1;
while(1){
/* Move the smaller of the sequence to the left of the datum , Move the big one to the right */
while(A[++Low]<Pivot);
while(A[--High]>pivot);
if(Low<High) Swap(&A[Low], &A[High]);
else break;
}
Swap(&A[Low], &A[Right-1]); /* Change the datum to the correct position */
Qsort(A, Left, Low-1); /* Recursively solve left */
Qsort(A, Low+1, Right); /* Recursively solve right */
}
else Insertionsort(A+Left, Right-Left+1); /* Too few elements , Simple sorting */
}
void Quicksort（ElementType A[],int N){

/* Unified interface */
Qsort(A, 0, N-1);
}
`````` ## 7、 Heap sort

describe ：

Heap sorting is a sort algorithm designed by using heap as data structure . Stacking is the structure of a nearly complete binary tree , And at the same time satisfy the nature of accumulation ： That is, the key or index of the child is always less than （ Or greater than ） Its parent node .

Dynamic diagram demonstration ： Heap sorting is actually the same as the previous heap , But I don't know . Code ：

``````#python
def buildMaxHeap(arr):
import math
for i in range(math.floor(len(arr)/2),-1,-1):
heapify(arr,i)
def heapify(arr, i):
left = 2*i+1
right = 2*i+2
largest = i
if left < arrLen and arr[left] > arr[largest]:
largest = left
if right < arrLen and arr[right] > arr[largest]:
largest = right
if largest != i:
swap(arr, i, largest)
heapify(arr, largest)
def swap(arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def heapSort(arr):
global arrLen
arrLen = len(arr)
buildMaxHeap(arr)
for i in range(len(arr)-1,0,-1):
swap(arr,0,i)
arrLen -=1
heapify(arr, 0)
return arr
``````
``````//C
void swap(int *a, int *b) {

int temp = *b;
*b = *a;
*a = temp;
}
void max_heapify(int arr[], int start, int end) {

// Establish parent and child indicators
int son = dad * 2 + 1;
while (son <= end) {
// Only when the sub node indicators are within the range can they be compared
if (son + 1 <= end && arr[son] < arr[son + 1]) // Compare the size of two child nodes first , Select the largest
son++;
if (arr[dad] > arr[son]) // If the parent node is larger than the child node, the adjustment is completed , Jump function directly
return;
else {
// Otherwise, exchange parent-child content and continue the comparison between child nodes and child nodes
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {

int i;
// initialization ,i Adjust from last parent
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
// First exchange the first element with the one before the arranged element , Readjust again , Until the sorting is finished
for (i = len - 1; i > 0; i--) {

swap(&arr, &arr[i]);
max_heapify(arr, 0, i - 1);
}
}
``````
``````//C++
void max_heapify(int arr[], int start, int end) {

// Establish parent and child indicators
int son = dad * 2 + 1;
while (son <= end) {
// Only when the sub node indicators are within the range can they be compared
if (son + 1 <= end && arr[son] < arr[son + 1]) // Compare the size of two child nodes first , Select the largest
son++;
if (arr[dad] > arr[son]) // If the parent node is larger than the child node, the adjustment is completed , Jump function directly
return;
else {
// Otherwise, exchange parent-child content and continue the comparison between child nodes and child nodes
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {

// initialization ,i Adjust from last parent
for (int i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
// First, exchange the first element with the previous one of the arranged elements , Readjust again ( Elements before elements just adjusted ), Until the sorting is finished
for (int i = len - 1; i > 0; i--) {

swap(arr, arr[i]);
max_heapify(arr, 0, i - 1);
}
}
``````

Reference resources MOOC Data structure of Zhejiang University

``````void Swap( ElementType *a, ElementType *b )
{

ElementType t = *a; *a = *b; *b = t;
}
void PercDown( ElementType A[], int p, int N )
{
/* Adapted code 4.24 Of PercDown( MaxHeap H, int p ) */
/* take N In the array of elements A[p] Adjust the child heap of the root to the maximum heap */
int Parent, Child;
ElementType X;
X = A[p]; /* Take out the root of the node */
for( Parent=p; (Parent*2+1)<N; Parent=Child ) {

Child = Parent * 2 + 1;
if( (Child!=N-1) && (A[Child]<A[Child+1]) )
Child++; /* Child Point to the larger one of the left and right child nodes */
if( X >= A[Child] ) break; /* Found the right place */
else /* Filtration X */
A[Parent] = A[Child];
}
A[Parent] = X;
}
void HeapSort( ElementType A[], int N )
{
/* Heap sort */
int i;
for ( i=N/2-1; i>=0; i-- )/* Build the largest heap */
PercDown( A, i, N );
for ( i=N-1; i>0; i-- ) {

/* Delete the maximum heap top */
Swap( &A, &A[i] ); /* See the code 7.1 */
PercDown( A, 0, i );
}
}
`````` ## 8、 Count sorting

describe ：

Counting sort is not a sort algorithm based on comparison , Its core is to convert the input data value into a key and store it in the extra open array space .

Dynamic diagram demonstration ： If it's not an example that must be compared , I don't know how fast to count , For example, seniority statistics . Code ：

``````#python
def countingSort(arr, maxValue):
bucketLen = maxValue+1
bucket = *bucketLen
sortedIndex =0
arrLen = len(arr)
for i in range(arrLen):
if not bucket[arr[i]]:
bucket[arr[i]]=0
bucket[arr[i]]+=1
for j in range(bucketLen):
while bucket[j]>0:
arr[sortedIndex] = j
sortedIndex+=1
bucket[j]-=1
return arr
``````
``````//C
void print_arr(int *arr, int n) {

int i;
printf("%d", arr);
for (i = 1; i < n; i++)
printf(" %d", arr[i]);
printf("\n");
}
void counting_sort(int *ini_arr, int *sorted_arr, int n) {

int *count_arr = (int *) malloc(sizeof(int) * 100);
int i, j, k;
for (k = 0; k < 100; k++)
count_arr[k] = 0;
for (i = 0; i < n; i++)
count_arr[ini_arr[i]]++;
for (k = 1; k < 100; k++)
count_arr[k] += count_arr[k - 1];
for (j = n; j > 0; j--)
sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
free(count_arr);
}
`````` ## 9、 Bucket sort

describe ：

Bucket sorting is an upgrade of counting sorting . It makes use of the mapping of functions , The key to high efficiency lies in the determination of this mapping function .

Dynamic diagram demonstration ： It seems that counting and sorting are really easy to use , Or there won't be plus！ Code ：

``````struct ListNode{

explicit ListNode(int i=0):mData(i),mNext(NULL){
}
ListNode* mNext;
int mData;
};

ListNode dummyNode;
ListNode *newNode = new ListNode(val);
ListNode *pre,*curr;
pre = &dummyNode;
while(NULL!=curr && curr->mData<=val){

pre = curr;
curr = curr->mNext;
}
newNode->mNext = curr;
pre->mNext = newNode;
return dummyNode.mNext;
}

ListNode dummyNode;
ListNode *dummy = &dummyNode;

}else{

}
dummy = dummy->mNext;
}
return dummyNode.mNext;
}
void BucketSort(int n,int arr[]){

vector<ListNode*> buckets(BUCKET_NUM,(ListNode*)(0));
for(int i=0;i<n;++i){

int index = arr[i]/BUCKET_NUM;
}
for(int i=1;i<BUCKET_NUM;++i){

}
for(int i=0;i<n;++i){

}
}
``````

describe ：

Radix sort is sorted in order of low order first , Then collect ; And then sort by the highest order , And then collect ; By analogy , Up to the highest bit . Sometimes some properties are prioritized , Let's start with low priority , And then sort by high priority . The last order is the one with the highest priority , High priority equals low priority equals high priority .

Dynamic diagram demonstration ： Cardinality sort is like poker sort ！ Is it a number or a color number ？

Code ：

``````//C
void print(int *a, int n) {

int i;
for (i = 0; i < n; i++) {

printf("%d\t", a[i]);
}
}
void radixsort(int *a, int n) {

int i, b[MAX], m = a, exp = 1;
for (i = 1; i < n; i++) {

if (a[i] > m) {

m = a[i];
}
}
while (m / exp > 0) {

int bucket[BASE] = {
0 };
for (i = 0; i < n; i++) {

bucket[(a[i] / exp) % BASE]++;
}
for (i = 1; i < BASE; i++) {

bucket[i] += bucket[i - 1];
}
for (i = n - 1; i >= 0; i--) {

b[--bucket[(a[i] / exp) % BASE]] = a[i];
}
for (i = 0; i < n; i++) {

a[i] = b[i];
}
exp *= BASE;
#ifdef SHOWPASS
printf("\nPASS : ");
print(a, n);
#endif
}
}
``````
``````//C++
// Auxiliary function , Find the maximum number of digits of data
int maxbit(int data[], int n) {

int maxData = data; ///< The maximum number
/// Find the maximum number first , Find the number of digits again , In this way, each number in turn is used to judge the number of digits , Slightly optimized .
for (int i = 1; i < n; ++i) {

if (maxData < data[i])
maxData = data[i];
}
int d = 1;
int p = 10;
while (maxData >= p) {

//p *= 10; // Maybe overflow
maxData /= 10;
++d;
}
return d;
}
void radixsort(int data[], int n) {

int d = maxbit(data, n);
int *tmp = new int[n];
int *count = new int; // Counter
int i, j, k;
// Conduct d Secondary ranking
for(i = 1; i <= d; i++) {

for(j = 0; j < 10; j++)
count[j] = 0; // Clear counter before each allocation
for(j = 0; j < n; j++){

k = (data[j] / radix) % 10; // Count the number of records in each barrel
count[k]++;
}
for(j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; // take tmp The positions in are assigned to each bucket in turn
for(j = n - 1; j >= 0; j--) {
// Collect records in all buckets in turn to tmp in
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for(j = 0; j < n; j++) // Copy the contents of the temporary array to data in
data[j] = tmp[j];
}
delete []tmp;
delete []count;
}
``````

Reference resources MOOC Data structure of Zhejiang University

``````//c
/* Radix sorting - Secondary priority */
/* Suppose the element has at most MaxDigit Key words , Base numbers are all the same Radix */
#define MaxDigit 4
/* Bucket element node */
typedef struct Node *PtrToNode;
struct Node {

int key;
PtrToNode next;
};

};
int GetDigit ( int X, int D )
{
/* Default secondary D=1, nominative case D<=MaxDigit */
int d, i;
for (i=1; i<=D; i++) {

}
return d;
}
void LSDRadixSort( ElementType A[], int N )
{
/* Radix sorting - Secondary priority */
int D, Di, i;
Bucket B;
PtrToNode tmp, p, List = NULL;
for (i=0; i<Radix; i++) /* Initialize each bucket as an empty list */
for (i=0; i<N; i++) {
/* Store the original sequence in the initial linked list in reverse order List */
tmp = (PtrToNode)malloc(sizeof(struct Node));
tmp->key = A[i];
tmp->next = List;
List = tmp;
}
/* Start sorting below */
for (D=1; D<=MaxDigit; D++) {
/* Processing every bit of data circularly */
/* Here is the process of allocation */
p = List;
while (p) {

Di = GetDigit(p->key, D); /* Gets the current digit number of the current element */
/* from List Middle extirpation */
tmp = p; p = p->next;
/* Insert B[Di] Tail of No */
tmp->next = NULL;
else {

B[Di].tail->next = tmp;
B[Di].tail = tmp;
}
}
/* Here is the process of collection */
List = NULL;
/* The elements of each bucket are collected in sequence List */
/* If the bucket is not empty */
/* Full barrel insertion List Header */
B[Di].tail->next = List;
B[Di].head = B[Di].tail = NULL; /* Empty bucket */
}
}
}
/* take List Pour into A[] And free up space */
for (i=0; i<N; i++) {

tmp = List;
List = List->next;
A[i] = tmp->key;
free(tmp);
}
}
/* Radix sorting - Thematic priority */
/* Suppose the element has at most MaxDigit Key words , Base numbers are all the same Radix */
#define MaxDigit 4
/* Bucket element node */
typedef struct Node *PtrToNode;
struct Node{

int key;
PtrToNode next;
};

};
int GetDigit ( int X, int D )
{
/* Default secondary D=1, nominative case D<=MaxDigit */
int d, i;
for (i=1; i<=D; i++) {

}
return d;
}
void MSD( ElementType A[], int L, int R, int D )
{
/* Core recursive function : Yes A[L]...A[R] Of the D Number of digits to sort */
int Di, i, j;
Bucket B;
PtrToNode tmp, p, List = NULL;
if (D==0) return; /* Recursive termination condition */
for (i=0; i<Radix; i++) /* Initialize each bucket as an empty list */
for (i=L; i<=R; i++) {
/* Store the original sequence in the initial linked list in reverse order List */
tmp = (PtrToNode)malloc(sizeof(struct Node));
tmp->key = A[i];
tmp->next = List;
List = tmp;
}
/* Here is the process of allocation */
p = List;
while (p) {

Di = GetDigit(p->key, D); /* Gets the current digit number of the current element */
/* from List Middle extirpation */
tmp = p; p = p->next;
/* Insert B[Di] Bucket number */
if (B[Di].head == NULL) B[Di].tail = tmp;
}
/* Here is the process of collection */
i = j = L; /* i, j Record the current to be processed A[] Left and right subscripts of */
/* For each barrel */
/* Pour the whole non empty barrel into A[], Recursive sorting */
while (p) {

tmp = p;
p = p->next;
A[j++] = tmp->key;
free(tmp);
}
/* Sort the bucket data recursively , Digit subtraction 1 */
MSD(A, i, j-1, D-1);
i = j; /* Corresponding to the next barrel A[] Left side */
}
}
}
void MSDRadixSort( ElementType A[], int N )
{
/* Unified interface */
MSD(A, 0, N-1, MaxDigit);
}
`````` I still like the code style of Zhejiang University ！

## Reference resources

• Baidu Encyclopedia
• https://www.runoob.com/
• https://github.com/hustcc/JS-Sorting-Algorithm