Sorting algorithms are divided into internal sorting and external sorting. We often say that the sorting algorithm is internal sorting
Internal sorting: data records are sorted in memory
External sorting: the sorting data is too large to hold all sorting records at one time. External memory needs to be accessed in the sorting process
Stable sorting algorithm: the same element position has not been changed
The sorting algorithm we will understand is as follows:
Swap sort: bubble sort (stable or unstable), quick sort (unstable)
Selective sorting: simple selective sorting (unstable), heap sorting
Insert sort: direct insert sort, Hill sort
Merge sort
Now let's take a look at the bubble sorting algorithm in our exchange sorting
Bubble sorting
Thought:
- Compare adjacent elements. If the former is larger than the latter, exchange their two positions.
- Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. After this step, the last element will be the maximum number.
- Repeat the above steps for all elements except the last one.
- Continue to repeat the above steps for fewer and fewer elements at a time until no pair of numbers need to be compared.
The code is as follows:
1 #include<stdio.h> 2 int a[5]; 3 void swap(int a[],int i,int j) 4 { 5 int t=a[i]; 6 a[i]=a[j]; 7 a[j]=t; 8 } 9 void Bubblesort(int a[],int n) 10 { 11 int i,j; 12 for(i=0;i<n;i++) 13 { 14 for(j=i;j<n;j++) 15 { 16 if(a[i]>a[j]) 17 { 18 swap(a,i,j); 19 } 20 } 21 } 22 } 23 int main() 24 { 25 int i; 26 for(i=0;i<5;i++) 27 { 28 scanf("%d",&a[i]); 29 } 30 Bubblesort(a,5); 31 for(i=0;i<5;i++) 32 { 33 printf("%d\n",a[i]); 34 } 35 return 0; 36 }
Bubble sorting is the easiest sorting algorithm to understand and master, but it is inefficient for multi-element data sorting, but bubble sorting can also be improved. Let's take a look at the improved algorithm of bubble sorting - Cocktail sorting
The difference between this algorithm and bubble sorting algorithm is that it is from top to bottom and from bottom to top, while bubble sorting is only from top to bottom
Let's look at the cocktail sorting algorithm
1 #include<stdio.h> 2 int a[5]; 3 void swap(int a[],int i,int j) 4 { 5 int t=a[i]; 6 a[i]=a[j]; 7 a[j]=t; 8 } 9 void Bubblesort(int a[],int n) 10 { 11 int i; 12 int l=0,r=n-1; 13 while(l<r) 14 { 15 for(i=l;i<r;i++) 16 { 17 if(a[i]>a[i+1])//max,down Place the maximum at the bottom 18 { 19 swap(a,i,i+1); 20 } 21 } 22 r--;//Because it's at the bottom, it's r-- 23 for(i=r;i>l;i--) 24 { 25 if(a[i-1]>a[i])//min up Place minimum on top 26 { 27 swap(a,i-1,i); 28 } 29 } 30 l++;//Put it at the bottom, so l++ 31 } 32 } 33 int main() 34 { 35 int i; 36 for(i=0;i<5;i++) 37 { 38 scanf("%d",&a[i]); 39 } 40 Bubblesort(a,5); 41 for(i=0;i<5;i++) 42 { 43 printf("%d\n",a[i]); 44 } 45 return 0; 46 }
Let's take a look at quick sort in swap sort
Quick sort:
Thought:
Quick sort mainly uses the idea of recursion
Quick sorting uses the sorting method to divide a sequence into two subsequences
1. Select an element from the sequence as the reference element
2. Put all elements smaller than the benchmark in front of the benchmark element and those larger than the benchmark element behind the benchmark element. The same can be on either side. This operation is called partition operation
3. Operate 1 and 2 recursively for each partition. The condition for the end of recursion is that the sequence size is 0 or 1.
The code is as follows:
1 #include<stdio.h> 2 #define p 10 3 int a[p]; 4 void swap(int a[],int i,int j) 5 { 6 int t=a[i]; 7 a[i]=a[j]; 8 a[j]=t; 9 } 10 int Divide(int a[],int l,int r)//Partition sequence 11 { 12 int benchmark=a[r];//Determining datum elements 13 int tail=l-1;//initialization 14 int i; 15 for(i=l;i<r;i++)//Traverses all elements except the base element 16 { 17 if(a[i]<=benchmark)//Place less than the base element to the left 18 { 19 swap(a,++tail,i); 20 } 21 } 22 swap(a,tail+1,r);//Place the base element behind all elements smaller than the base element 23 return tail+1;//Return index 24 } 25 void Quicksort(int a[],int l,int r) 26 { 27 if(l>=r)//There is a sequence with size 0 or 1 28 return; 29 int index=Divide(a,l,r);//The division sequence is initialized for the first time and the reference element is determined 30 Quicksort(a,l,index-1); 31 Quicksort(a,index+1,r); 32 } 33 int main() 34 { 35 int i; 36 for(i=0;i<p;i++) 37 { 38 scanf("%d",&a[i]); 39 } 40 Quicksort(a,0,p-1); 41 for(i=0;i<p;i++) 42 { 43 printf("%d\n",a[i]); 44 } 45 return 0; 46 }
Let's take a look at selection sorting. First, let's take a look at the simple selection sorting in selection sorting
Simple selection sorting:
Thought:
Simple selection sorting is to traverse the elements. If you find the largest or smallest element, take it out and put it in the head of your array. The array found later will be placed in the first and second bits of the array, and so on. Then, the traversal range will be reduced by 1 and the cycle will continue until the traversal range is 1
However, we should pay attention to the difference between simple selection sort and bubble sort: bubble sort is the exchange of two adjacent elements, while selection sort is not
Without much to say, let's look at the code directly below:
1 #include<stdio.h> 2 #define p 10 3 int a[p]; 4 void swap(int a[],int i,int j) 5 { 6 int t=a[i]; 7 a[i]=a[j]; 8 a[j]=t; 9 } 10 void selectsort(int a[],int n) 11 { 12 int i,j,min; 13 for(i=0;i<n;i++) 14 { 15 min=i;//Assume the location of the smallest element 16 for(j=i+1;j<n;j++)//Traverse the element after the smallest element to find the position of the smallest element 17 { 18 if(a[min]>a[j]) 19 { 20 min=j; 21 } 22 } 23 if(min!=i)//exchange 24 { 25 swap(a,min,i); 26 } 27 } 28 } 29 int main() 30 { 31 int i; 32 for(i=0;i<p;i++) 33 { 34 scanf("%d",&a[i]); 35 } 36 selectsort(a,p); 37 for(i=0;i<p;i++) 38 { 39 printf("%d\n",a[i]); 40 } 41 return 0; 42 }
Let's take a look at the heap sorting in the selection sorting:
Heap sort:
Heap sorting depends on the data structure of heap, which is mainly divided into two steps. The first step is to construct the initial heap, and the second is how to adjust the heap after outputting the top elements of the heap
Let's take the large fixed heap as an example: the value of the parent node is always greater than that of the child node
1 #include<stdio.h> 2 #define p 10 3 int a[p]; 4 void swap(int a[],int i,int j) 5 { 6 int t=a[i]; 7 a[i]=a[j]; 8 a[j]=t; 9 } 10 int Adjustment(int a[],int i,int size)//Heap adjustment 11 { 12 int left_child=2*i+1; 13 int right_child=2*i+2;//Determine the position of left and right children 14 int max=i;//If the child is larger than the father, exchange 15 if(left_child<size&&a[left_child]>a[max]) 16 max=left_child; 17 if(right_child<size&&a[right_child]>a[max]) 18 max=right_child; 19 if(max!=i) 20 { 21 swap(a,max,i); 22 Adjustment(a,max,size); 23 } 24 } 25 int BuildHeap(int a,int n) 26 { 27 int size=n; 28 int i; 29 for(i=size/2-1;i>=0;i--)//Build maximum heap 30 { 31 Adjustment(a,i,size); 32 } 33 return size; 34 } 35 void Heapsort(int a,int n)//Heap sorting algorithm 36 { 37 int size=BuildHeap(a,n); 38 while(size>1) 39 { 40 swap(a,0,--size);//Exchange the top elements with the last elements and arrange them in ascending order 41 Adjustment(a,0,size); 42 } 43 } 44 int main() 45 { 46 int i; 47 for(i=0;i<p;i++) 48 { 49 scanf("%d",&a[i]); 50 } 51 Heapsort(a,p); 52 for(i=0;i<p;i++) 53 { 54 printf("%d\n",a[i]); 55 } 56 return 0; 57 }