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 ,
 Insert picture description here
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 !
 Insert picture description here
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 !
 Insert picture description here
 Insert picture description here

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 :
 Insert picture description here

  • 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 ).
     Insert picture description here

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;
}
}

 Insert picture description here

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 :
 Insert picture description here
( It's actually playing cards , Catching cards , Look at cards , Horse brand )
 Insert picture description here

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]);
}
}
}

 Insert picture description here

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 :
 Insert picture description here
( slow , Really slow , It's not fake )
 Insert picture description here
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;
}
}

 Insert picture description here

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 :
 Insert picture description here
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 )
 Insert picture description here

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;
}
}
}

 Insert picture description here

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 :
 Insert picture description here
It's about breaking it up , Separation , ha-ha
 Insert picture description here

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[0] <= right[0]:
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 " );
}

 Insert picture description here

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 :
 Insert picture description here
Fast sorting is the most powerful feeling at present .
 Insert picture description here

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]*/
return A[Right-1]; /* Return to benchmark Pivot*/
}
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);
}

 Insert picture description here

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 :
 Insert picture description here
Heap sorting is actually the same as the previous heap , But I don't know .
 Insert picture description here

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 dad = start;
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 
swap(&arr[dad], &arr[son]);
dad = son;
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[0], &arr[i]);
max_heapify(arr, 0, i - 1);
}
}
//C++
void max_heapify(int arr[], int start, int end) {

// Establish parent and child indicators 
int dad = start;
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 
swap(arr[dad], arr[son]);
dad = son;
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[0], 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[0], &A[i] ); /* See the code 7.1 */
PercDown( A, 0, i );
}
}

 Insert picture description here

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 :
 Insert picture description here
If it's not an example that must be compared , I don't know how fast to count , For example, seniority statistics .
 Insert picture description here

Code :

#python
def countingSort(arr, maxValue):
bucketLen = maxValue+1
bucket = [0]*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[0]);
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);
}

 Insert picture description here

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 :

 Insert picture description here
It seems that counting and sorting are really easy to use , Or there won't be plus!
 Insert picture description here
Code :

struct ListNode{

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

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

pre = curr;
curr = curr->mNext;
}
newNode->mNext = curr;
pre->mNext = newNode;
return dummyNode.mNext;
}
ListNode* Merge(ListNode *head1,ListNode *head2){

ListNode dummyNode;
ListNode *dummy = &dummyNode;
while(NULL!=head1 && NULL!=head2){

if(head1->mData <= head2->mData){

dummy->mNext = head1;
head1 = head1->mNext;
}else{

dummy->mNext = head2;
head2 = head2->mNext;
}
dummy = dummy->mNext;
}
if(NULL!=head1) dummy->mNext = head1;
if(NULL!=head2) dummy->mNext = head2;
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;
ListNode *head = buckets.at(index);
buckets.at(index) = insert(head,arr[i]);
}
ListNode *head = buckets.at(0);
for(int i=1;i<BUCKET_NUM;++i){

head = Merge(head,buckets.at(i));
}
for(int i=0;i<n;++i){

arr[i] = head->mData;
head = head->mNext;
}
}

10、 Radix sorting

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 :
 Insert picture description here
Cardinality sort is like poker sort !
 Insert picture description here
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[0], 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[0]; ///< 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;
}
// Radix sorting 
void radixsort(int data[], int n) {

int d = maxbit(data, n);
int *tmp = new int[n];
int *count = new int[10]; // Counter 
int i, j, k;
int radix = 1;
// 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];
radix = radix * 10;
}
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
#define Radix 10
/* Bucket element node */
typedef struct Node *PtrToNode;
struct Node {

int key;
PtrToNode next;
};
/* Bucket head node */
struct HeadNode {

PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];
int GetDigit ( int X, int D )
{
 /* Default secondary D=1, nominative case D<=MaxDigit */
int d, i;
for (i=1; i<=D; i++) {

d = X % Radix;
X /= Radix;
}
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 */
B[i].head = B[i].tail = NULL;
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;
if (B[Di].head == NULL)
B[Di].head = B[Di].tail = tmp;
else {

B[Di].tail->next = tmp;
B[Di].tail = tmp;
}
}
/* Here is the process of collection */
List = NULL;
for (Di=Radix-1; Di>=0; Di--) {
 /* The elements of each bucket are collected in sequence List */
if (B[Di].head) {
 /* If the bucket is not empty */
/* Full barrel insertion List Header */
B[Di].tail->next = List;
List = B[Di].head;
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
#define Radix 10
/* Bucket element node */
typedef struct Node *PtrToNode;
struct Node{

int key;
PtrToNode next;
};
/* Bucket head node */
struct HeadNode {

PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];
int GetDigit ( int X, int D )
{
 /* Default secondary D=1, nominative case D<=MaxDigit */
int d, i;
for (i=1; i<=D; i++) {

d = X%Radix;
X /= Radix;
}
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 */
B[i].head = B[i].tail = NULL;
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;
tmp->next = B[Di].head;
B[Di].head = 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 (Di=0; Di<Radix; Di++) {
 /* For each barrel */
if (B[Di].head) {
 /* Pour the whole non empty barrel into A[], Recursive sorting */
p = B[Di].head;
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);
}

 Insert picture description here
I still like the code style of Zhejiang University !

Reference resources

  • Baidu Encyclopedia
  • https://www.runoob.com/
  • https://github.com/hustcc/JS-Sorting-Algorithm
版权声明
本文为[I'm Guan Xiaoliang]所创,转载请带上原文链接,感谢

  1. 利用Python爬虫获取招聘网站职位信息
  2. Using Python crawler to obtain job information of recruitment website
  3. Several highly rated Python libraries arrow, jsonpath, psutil and tenacity are recommended
  4. Python装饰器
  5. Python实现LDAP认证
  6. Python decorator
  7. Implementing LDAP authentication with Python
  8. Vscode configures Python development environment!
  9. In Python, how dare you say you can't log module? ️
  10. 我收藏的有关Python的电子书和资料
  11. python 中 lambda的一些tips
  12. python中字典的一些tips
  13. python 用生成器生成斐波那契数列
  14. python脚本转pyc踩了个坑。。。
  15. My collection of e-books and materials about Python
  16. Some tips of lambda in Python
  17. Some tips of dictionary in Python
  18. Using Python generator to generate Fibonacci sequence
  19. The conversion of Python script to PyC stepped on a pit...
  20. Python游戏开发,pygame模块,Python实现扫雷小游戏
  21. Python game development, pyGame module, python implementation of minesweeping games
  22. Python实用工具,email模块,Python实现邮件远程控制自己电脑
  23. Python utility, email module, python realizes mail remote control of its own computer
  24. 毫无头绪的自学Python,你可能连门槛都摸不到!【最佳学习路线】
  25. Python读取二进制文件代码方法解析
  26. Python字典的实现原理
  27. Without a clue, you may not even touch the threshold【 Best learning route]
  28. Parsing method of Python reading binary file code
  29. Implementation principle of Python dictionary
  30. You must know the function of pandas to parse JSON data - JSON_ normalize()
  31. Python实用案例,私人定制,Python自动化生成爱豆专属2021日历
  32. Python practical case, private customization, python automatic generation of Adu exclusive 2021 calendar
  33. 《Python实例》震惊了,用Python这么简单实现了聊天系统的脏话,广告检测
  34. "Python instance" was shocked and realized the dirty words and advertisement detection of the chat system in Python
  35. Convolutional neural network processing sequence for Python deep learning
  36. Python data structure and algorithm (1) -- enum type enum
  37. 超全大厂算法岗百问百答(推荐系统/机器学习/深度学习/C++/Spark/python)
  38. 【Python进阶】你真的明白NumPy中的ndarray吗?
  39. All questions and answers for algorithm posts of super large factories (recommended system / machine learning / deep learning / C + + / spark / Python)
  40. [advanced Python] do you really understand ndarray in numpy?
  41. 【Python进阶】Python进阶专栏栏主自述:不忘初心,砥砺前行
  42. [advanced Python] Python advanced column main readme: never forget the original intention and forge ahead
  43. python垃圾回收和缓存管理
  44. java调用Python程序
  45. java调用Python程序
  46. Python常用函数有哪些?Python基础入门课程
  47. Python garbage collection and cache management
  48. Java calling Python program
  49. Java calling Python program
  50. What functions are commonly used in Python? Introduction to Python Basics
  51. Python basic knowledge
  52. Anaconda5.2 安装 Python 库(MySQLdb)的方法
  53. Python实现对脑电数据情绪分析
  54. Anaconda 5.2 method of installing Python Library (mysqldb)
  55. Python implements emotion analysis of EEG data
  56. Master some advanced usage of Python in 30 seconds, which makes others envy it
  57. python爬取百度图片并对图片做一系列处理
  58. Python crawls Baidu pictures and does a series of processing on them
  59. python链接mysql数据库
  60. Python link MySQL database